Есть какой-нибудь алгоритм, чтобы найти двойное число проблем?


Я пытался закодировать проблему двойного номера проблемы, но до этого не смог завершить алгоритм. Кто-нибудь имеет какие-либо идеи?

Постановка Задачи -

Числа обладают следующим свойством -

Всякий раз, когда вы поворачиваете число вправо (то есть убираете последнюю цифру и поставьте ее перед цифрой), вы бы в итоге получили удвоить исходное число. Числами, обладающими этим свойством, были звонил по двузначным номерам. Для например, X = 421052631578947368-это номер двойной проблемы, так как 2X = 842105263157894736, который является правое вращение X.

Число X-это число двойной проблемы в системе счисления с основанием 10. Любая система счисления с основанием p >= 2, однако, имеет много таких двойных проблемных чисел. В двоичной системе счисления (основание p = 2), для например, у нас есть двойные номера проблем 01 и 0101. Заметить это ведущие нули необходимы здесь для того, чтобы получить правильный число после поворота направо.

В двоичной системе счисления наименьшее число двойной ошибки равно 01. В десятичной системе счисления (p = 10) наименьшее число двойных проблем это 052631578947368421. Мне нужно написать программу, которая вычисляет для заданное основание p системы счисления наименьшее число двойных проблем в эта система.

1   2  

1 ответ:

Вот решение грубой силы в JavaScript. Он начинается с цифры, затем предшествует двойнику предыдущей цифры (плюс перенос). После каждой итерации он проверяет, являются ли цифры двойным номером проблемы (он также пытается добавить " 0 " угловой / неоднозначный случай)

Эта реализация предназначена только для базы 10; вам нужно понять алгоритм и изменить код, чтобы создать произвольную базовую абстракцию.

Двойной решатель проблем для базы 10

// (digits * 2) == digits[n]:digits[1..n-1]
function isDT(digits) {
    var times2 = "";
    var carry = false;
    for(var i = digits.length-1; i >= 0; i--) {
        var d = parseInt(digits.charAt(i));
        var d2 = "" + (d * 2 + (carry ? 1 : 0));
        carry = d2.length > 1;
        times2 = d2.charAt(d2.length > 1 ? 1 : 0) + times2;
    }
    if(carry) { times2 = "1" + times2; }
    return times2 == (digits.charAt(digits.length -1) + digits.substring(0, digits.length -1));
}
// generate a doule trouble number from a starting digit
function makeDT(digits, carry) {
    var carry = carry || false;
    var digits = "" + digits;
    if(carry && isDT("1" + digits)) {
        return "1" + digits;
    } else if(isDT(digits)) {
        return digits;
    } else if(isDT("0" + digits)) {
        return "0" + digits;
    }
    var d = digits.charAt(0);
    var d2 = "" + (d * 2 + (carry ? 1 : 0));
    carry = d2.length > 1;
    digits = d2.charAt(d2.length > 1 ? 1 : 0) + digits;
    return makeDT(digits, carry);
}
//
alert(makeDT("9"));
alert(makeDT("8"));
alert(makeDT("7"));
alert(makeDT("6"));
alert(makeDT("5"));
alert(makeDT("4"));
alert(makeDT("3"));
alert(makeDT("2"));
alert(makeDT("1"));

EDIT Вот jsfiddle http://jsfiddle.net/avbfae0w/