欧拉计划 #36 更好的解决方案？

Question

欧拉项目 问题 36 指出：

十进制数 585 = 1001001001（二进制）在两个基数中都是回文。

求所有小于 100 万、以 10 为底和以 2 为底的回文数的总和。

（请注意，任一基数的回文数都不能包含前导零。）

已经有一个 堆栈溢出的解决方案，但我想要一个更有效的解决方案。

例如，由于回文数不能有前导 0，因此不需要检查偶数，只需检查二进制中最后一位为 1 的奇数。这个简单的观察已经加快了“检查范围内的每个数字”的暴力破解速度。两倍。

但我想比这更聪明。理想情况下，我想要一个运行时间与总和中的数字数量成正比的算法。我认为不可能做得更好。但也许这是不可能的。例如，我们能否在与满足该属性的十进制数的数量成正比的时间内生成所有小于一百万的回文十进制数？ （我认为答案是肯定的）。

解决这个回文和问题的最有效算法是什么？我想考虑由 N 参数化的运行时间：数字范围的大小（在本例中为 100 万），D：范围内的十进制回文集，B：范围内的二进制回文集。我希望运行时间为 o(N) + O( |D intersect B| )，否则，O(min(|D|, |B|))

注意： 二进制 和 十进制回文是众所周知的。

例如二进制回文< 100：0、1、3、5、7、9、15、17、21、27、31、33、45、51、63、65、73、85、93、99

。 。 .十进制回文< 100:0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99，

两个碱基的回文：0, 1, 3 , 5, 7, 9, 33, 99

33 和 的二进制表示99 分别是 10001 和 1100011。 下一个数字是 585 = 1001001001，两者都是回文。

Answer 1

长度为 2*k 的基数 b 中的回文数为 (b-1)*b^(k-1)，如下长度 2*k-1 的回文数。因此，任何基数中不超过 N 的回文数都是 O(sqrt(N))1。因此，如果您在一个基中生成所有回文（不超过 N），并检查它们在另一个基中是否也是回文，则您将获得 O(sqrt(N)*log(N)) 算法（对数因子来自回文检查）。这是o(N)，但我还不知道它是否也是O(|D intersect B|)。

这不是 O(|D intersect B|) :( 最多 10¹⁰ 中只有 32 个数字在两个基数中都是回文。我没有看到任何允许仅构造这些数字的模式

。如果N有d位（以b为基数），则回文数不超过N介于最多有 d-1 位的回文数和最多有 d 位的回文数（两者都包含在内）之间有 (b)。 -1)*b^(k-1) 正好有 k 位数字（以 b 为基数），其中(b-1)*b^(floor((k-1)/2))) 是回文。求和给出最多 k 位的基 b 回文数，为 2*(b^(k/2)-1) （如果k是偶数）或(b-1)*b^((k-1)/2) + 2*(b^((k-1)/2)- 1)（如果k 是奇数）。因此，给定或取一个因子 2*b，最多包含 d 位数字的回文数为 b^(d/2)。因此，不超过 N 的回文数大约为 N^0.5，其中因子以基数的倍数为界。

Answer 2

考虑到 1 到 1000000 之间只有大约 2000 个十进制回文。从 1 到 999，您可以将数字及其逆序串在一起，无论是否重复“中间”数字（左侧部分的最后一个数字）。对于其中的每一个，您检查它是否也是二进制回文，如果是，则它是总和的一部分。

Answer 3

（不是您问题的答案，而是 Project Euler 36 的一个可爱的递归位解决方案）

这可能不是最有效的算法，但我喜欢它的样子。我在阅读了 Daniel Fischer 的答案后写了这篇文章，建议在一个基数中生成所有回文，然后检查另一个基数是否也是回文。

在 18 行代码（包括括号）中，它生成所有以 2 为基数的回文，然后检查它们是否也是以 10 为基数的回文

。在我的系统上大约需要 6 毫秒。

这可能可以优化（根据我的口味，移位操作太多，这里可能有一些不必要的垃圾），并且可能有更好的算法，但我“喜欢”（+）我的代码的外观； ）

@Test
public void testProjectEuler36() {
    final int v = rec(1, 1);
    assertEquals( 872187, v );
}

public static int rec( final int n, final int z ) {
    if ( n > 1000000 )
        return 0;
    if ( z % 2 == 0 ) {
        final int l = n << 1 & -1 << z / 2 + 1;
        final int r = n & -1 >>> 32 - z / 2;
        return v(n) + rec( l | 1 << z / 2 | r, z + 1 ) + rec( l | r, z + 1 );
    } else
        return v(n) + rec( n << 1 & -1 << z / 2 + 1 | n & -1 >>> 31 - z / 2, z + 1 );
}

public static int v( final int n ) {
    final String s = "" + n;
    boolean ok = true;
    for ( int j = s.length(), i = j / 2 - 1; i >= 0 && ok; i--)
        ok = s.charAt(i) == s.charAt(j-(i+1));
    return ok ? n : 0;
}

Answer 4

我最初的假设是完全错误的，所以我已经修正了它们。我提供了两种算法，一种是迭代算法，一种是递归算法。它们显然远不如 user988052 那样令人印象深刻和高效，但它们绝对更容易阅读！第一个算法是迭代的，运行时间为 9 毫秒。第二种算法是递归的，运行时间为 16 毫秒。尽管第二种解决方案更干净，但递归调用可能会减慢速度。

第一个算法（9ms）：

/** Given half a palindrome, construct the rest of the palindrome with
 * an optional string inserted in the middle. The returned string is
 * only guaranteed to be a palindrome if 'mid' is empty or a palindrome. */
public static String getPalindrome(String bin_part, String mid) {
    return bin_part + mid + (new StringBuilder(bin_part)).reverse();
}

/** Check if the specified string is a palindrome. */
public static boolean isPalindrome(String p) {
    for (int i=0; i<p.length()/2; i++)
        if (p.charAt(i) != p.charAt(p.length()-1-i))
            return false;
    return true;
}

public static void main(String[] args) {

    String[] mids = {"0","1"};
    long total = 0;
    boolean longDone = false; // have the numbers with extra digits been tested

    long start = System.currentTimeMillis();
    for (long i=0; i<1000; i++) {
        String bin_part = Long.toBinaryString(i);

        String bin = getPalindrome(bin_part, "");
        long dec = Long.valueOf(bin, 2);
        if (dec >= 1000000) break; // totally done

        if (isPalindrome(Long.toString(dec)))
            total += dec;

        if (!longDone) {
            for (int m=0; m<mids.length; m++)  {
                bin = getPalindrome(bin_part, mids[m]);
                dec = Long.valueOf(bin, 2);
                if (dec >= 1000000) {
                    longDone = true;
                    break;
                }
                if (isPalindrome(Long.toString(dec)))
                    total += dec;
            }
        }
    }
    long end = System.currentTimeMillis();
    System.out.println("Total: " + total + " in " + (end-start) + " ms");
}

第二个算法（16ms）

public long total = 0;
public long max_value = 1000000;
public long runtime = -1;

public static boolean isPalindrome(String s) {
    for (int i=0; i<s.length()/2; i++)
        if (s.charAt(i) != s.charAt(s.length()-1-i))
            return false;
    return true;
}

public void gen(String bin, boolean done) {
    if (done) { // generated a valid binary number
        // check current value and add to total if possible
        long val = Long.valueOf(bin, 2);
        if (val >= max_value)
            return;
        if (isPalindrome(Long.toString(val))) {
            total += val;
        }

        // generate next value
        gen('1' + bin + '1', true);
        gen('0' + bin + '0', false);
    } else { // generated invalid binary number (contains leading and trailing zero)
        if (Long.valueOf('1' + bin + '1', 2) < max_value) {
            gen('1' + bin + '1', true);
            gen('0' + bin + '0', false);
        }
    }
}

public void start() {
    total = 0;
    runtime = -1;
    long start = System.currentTimeMillis();
    gen("",false);
    gen("1",true);
    gen("0",false);
    long end = System.currentTimeMillis();
    runtime = end - start;
}

public static void main(String[] args) {
    Palindromes2 p = new Palindromes2();
    p.start();
    System.out.println("Total: " + p.total + " in " + p.runtime + " ms.");
}

Answer 5

这是解决这个问题的最佳 Python 实现：

sum = 0
for i in range(1000000):
    bina = int(str(bin(i)).replace('0b',''))
    if(i==int(str(i)[::-1]))or(bina==int(str(bina)[::-1])):
        #print("i : "+str(i))
        #print("bina : "+str(bina))
        sum+=i
print("Sum of numbers : ",sum)