有什么算法可以找到双麻烦号吗？

Question

我正在尝试编写双故障数问题的代码，但在此之前无法最终确定算法。有人知道吗？

Problem Statement -

The numbers has the following property -

Whenever you would right-rotate the number (that is, take away the last digit and put it in front of the number), you would end up with double the original number. Numbers possessing this property were called double-trouble numbers. For example, X = 421052631578947368 is a double-trouble number, since 2X = 842105263157894736 which is a right rotation of X.

The number X is a double-trouble number in the number system with base 10. Any number system with base p >= 2 , however, has many such double-trouble numbers. In the binary number system (base p = 2), for example, we have the double-trouble numbers 01 and 0101. Notice that the leading zeros are necessary here in order to obtain the proper number after right rotation.

In the binary number system the smallest double-trouble number is 01. In > the decimal (p = 10) number system, the smallest double-trouble number is 052631578947368421. I need to write a program that computes for a given base p of a number system the smallest double-trouble number in that system.

Answer 1

这是 JavaScript 中的暴力解决方案。它以一个数字开头，然后加上前一个数字的两倍（加上进位）。每次迭代后，它都会测试数字是否是双重故障数（它还会尝试在前面加上“0”corner/ambiguous 大小写）

此实现仅适用于基数 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"));

编辑这是 jsfiddle http://jsfiddle.net/avbfae0w/

有什么算法可以找到双麻烦号吗？

Any algorithm to find the double trouble number?

algorithm

numbers

puzzle