优化两个三位数乘积的最大回文数？

Question

我正在处理一道面试题，要求我编写一个程序来查找两个三位数的乘积中最大的回文数。

这是问题的描述。

我想到了从下往上的暴力方法。

public class LargestPalindromeQuestion {

    public static void main(String[] args) {
        int value = 0;
        for (int i = 100; i <= 999; i++) {
            for (int j = i; j <= 999; j++) {
                int value1 = i * j;
                if (isPalindrome(value1) && value < value1) {
                    value = value1;
                }
            }
        }
        System.out.println(value);
    }

    private static boolean isPalindrome(final int product) {
        int p = product;
        int reverse = 0;
        while (p != 0) {
            reverse *= 10;
            reverse += p % 10;
            p /= 10;
        }
        return reverse == product;
    }
}

他们问我在这个程序中可以做哪些优化？我提到我们可以尝试剪枝搜索空间并优化每个搜索空间中项目的检查步骤，但我现在不确定如何在上面的解决方案中实现这一点。

在这个程序中我们可以做哪些优化？目前它需要执行810000步才能找到最大的回文数。

我们可以执行的最少步骤是多少，才能找到两个三位数中最大的回文数？

- john

---

这可能会有帮助（我正在处理相同的问题，所以我还没有阅读它）http://www.mathblog.dk/project-euler-problem-4/ - user4668606

假设前导零不允许成为回文的一部分，任何以零结尾的数字都不能是回文。因此，您可以跳过所有 i 和 j 的值，其中 i % 10 == 0 或 j % 10 == 0，因为乘以以 0 结尾的值会得到以 0 结尾的结果。 - samgak

Answer 1

该程序看起来非常不错。我会让循环变量从999递减到100，并且只检查实际能够产生比当前最大值更大乘积的值。 这个程序能够出人意料地快速完成，确切地说是在 i == 952 时。数学原因是，一旦找到解决方案906609(993 * 913)，就不再可能找到一个更大的回文数，其中较大的因子小于906609的平方根，即952.160...。

public static void main(String[] args) {
    int value = 0;
    for (int i = 999; i >= 100; i--) {
        int r = value / i;
        if (r >= i) {
            System.out.println("We broke at i = " + i);
            break;
        }
        for (int j = i; j > r; j--) {
            int value1 = i * j;
            if (isPalindrome(value1)) {
                value = value1;
                break;
            }
        }
    }
    System.out.println(value);
}

- Paul Boddington

---

你能解释一下这行代码吗？“找到解决方案906609（993 * 913）后，数学原因是再也无法找到更大的回文数了。”？我不明白为什么在那之后我们就不能找到更大的回文数了？ - john

@david 在这段代码中，i 表示两个三位数中较大的那个。如果 i <= 952，那么 j 也会 <= 952（因为它小于或等于 i），所以 i * j 将小于 906609，这意味着继续执行没有意义。 - Paul Boddington

Answer 2

一个有用的剪枝搜索树的机制是注意到乘积 a * b 的最高位数并不经常改变。例如：

a = 111;   b = 112   a*b = 12432
       ;   b = 113   a*b = 12543
       ;   b = 114   a*b = 12654
       ;   ...
       ;   b = 180   a*b = 19980
       ;   b = 181   a*b = 20091 = (19980 + a)

因此，在所有值之间（a = 111，a＜b＜181），人们已经知道了MSB，它必须等于LSB或者（a％10）*（b％10）％10 == MSB。

 e.g.
 LSB = 1    --> a % 10 == 1, b % 10 == 1
            OR  a % 10 == 3, b % 10 == 7
            OR  a % 10 == 7, b % 10 == 3
            OR  a % 10 == 9, b % 10 == 9

大多数情况下，集合'b'中要么没有候选项，要么只有一个候选项被检查是否存在任何一对MSB，即a % 10。

- Aki Suihkonen

Answer 3

优化的一个简单方法是从最高的三位数开始而不是最小的。因为解决方案很可能更接近于一对(999, 999)而不是(100, 100)。

- user4668606

---

这很好。如果你在找到第一个回文数时使用 break; 语句，这将减少步骤的数量。你无法得到一个好的估计，但它会减少检查低于500的数字的不必要步骤。 - MLavrentyev

如果你从999倒数到100，当你找到一个回文数并且i * 999小于你找到的最高回文数时，可以停止。因为在这之后，不可能再找到更高的回文数。如果j倒数时i * j小于迄今为止找到的最高值，那么也可以在内部循环中（但不是外部循环）中断。 - samgak

这个陈述没有证据支持，也有可能最大回文出现在<500，所以这种方法会花费更长的时间。这个答案是通过逆向工程得出的，可能对于n*n回文的一般情况会失败。 - Vikram Bhat

@Vikram Bhat 我已经尝试过了。它比 (100, 100) 更接近于 (999, 999)。除此之外，还有很多数对 (n, n) 可以生成回文数。你说的没错，这只是一个猜测，但是通过观察这些数字，你可能会发现这是合理的。 - user4668606

@VikramBhat 如果你沿着向上的方向计数，那么你永远不会失败，因为你永远不知道是否会找到更高的数字。所以即使它小于500，这种方法仍然更快。 - samgak

@samgak同意该陈述，但并不赞同答案中所提到的原因。 - Vikram Bhat

Answer 4

我能得到的最少步骤是375。考虑将三位数a1a2a3乘以三位数b1b2b3：

JavaScript代码：

var modHash = new Array(10);
var iterations = 0;

for (var i=1; i<10; i++){
  modHash[i] = {0: [0]}
  for (var j=1; j<10; j++){
    iterations ++;
    var r = i * j % 10;
    if (modHash[i][r])
      modHash[i][r].push(j);
    else 
      modHash[i][r] = [j];
  }
}

var highest = 0;

function multiples(x,y,carry,mod){

  for (var i in modHash[x]){
    var m = (10 + mod - i - carry) % 10;

    if (modHash[y][m]){
      for (var j in modHash[x][i]){
        for (var k in modHash[y][m]){
          iterations ++;
          var palindrome = num(9,modHash[y][m][k],x,9,modHash[x][i][k],y);

          if (x == 3 && mod == 0){
            console.log(x + " * " + modHash[x][i][j] + " + " 
                        + y + " * " + modHash[y][m][k] + ": " + palindrome);
          }

          var str = String(palindrome);

          if (str == str.split("").reverse().join("") && palindrome > highest){
            highest = palindrome;
          }
        }
      }
    }
  }
}

function num(a1,a2,a3,b1,b2,b3){
  return (100*a1 + 10*a2 + a3)
       * (100*b1 + 10*b2 + b3);
}

var a3b3s = [[7,7,4],[9,1,0],[3,3,0]];

for (var i in a3b3s){
  for (var mod=0; mod<10; mod++){
    var x = a3b3s[i][0],
        y = a3b3s[i][1],
        carry = a3b3s[i][2];
    multiples(x,y,carry,mod);
  }
}

console.log(highest);
console.log("iterations: " + iterations);

输出：

3 * 0 + 3 * 0: 815409 
3 * 7 + 3 * 3: 907809 
3 * 4 + 3 * 6: 908109 
3 * 1 + 3 * 9: 906609 
3 * 8 + 3 * 2: 907309 
3 * 5 + 3 * 5: 908209 
3 * 2 + 3 * 8: 907309 
3 * 9 + 3 * 1: 906609 
3 * 6 + 3 * 4: 908109 
3 * 3 + 3 * 7: 907809
906609
iterations: 375

- גלעד ברקן

Answer 5

首先，通过将6位数字分为3位数字来优化isPalindrome。即N = ABCDEF => a = ABC = N/1000，b = DEF = N%1000；然后反转b并返回a == reversed_b;

其次，在生成回文数时，循环直到max_palindrome_so_far/999，这是您将使用的最小值。max_palindrome_so_far最初等于N。

public class Solution {

    public static boolean isPalindrome(int n){
        int a = n/1000;
        int b = n%1000;
        int d, r = 0, i = 3;
        while(i-- > 0){
            d = b%10;
            r = r*10 + d;
            b = b/10;
        }
        if (a == r)
            return true;
        return false;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            int n = in.nextInt();
            int r=0, m=n;
            int i,j;
            for(i = 999;i>=100;i--){
                for(j = 999;j>=m/999;j--){
                    if (i*j < n && i*j > 100000 && isPalindrome(i*j)){
                        r = Math.max(i*j, r);
                        m = r;
                    }
                }
            }

           // System.out.println(i + " * " + j + " = " + i*j);

            System.out.println(r);
        }
    }
}

- ugur