java - 找出由两个 3 位数字的乘积组成的最大回文

Question

package testing.project;

public class PalindromeThreeDigits {

    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;
                StringBuilder sb1 = new StringBuilder(""+value1);
                String sb2 = ""+value1;
                sb1.reverse();
                if(sb2.equals(sb1.toString()) && value<value1) {
                    value = value1;

                }

            }
        }

        System.out.println(value);
    }
}

这是我用 Java 写的代码...除了这个还有其他有效的方法吗...我们可以进一步优化这段代码吗？？

Answer 1

我们假设最大的回文数是六位数而不是五位数，因为 143*777 = 111111 是回文数。

如其他地方所述，以 10 为底的 6 位回文 abccba 是 11 的倍数。这是真的，因为 a*100001 + b*010010 + c*001100 等于 11*a*9091 + 11*b* 910 + 11*c*100。因此，在我们的内部循环中，如果 m 不是 11 的倍数，我们可以将 n 递减 11。

我们正在尝试找到百万以下的最大回文，它是两个 3 位数的乘积。为了找到一个大的结果，我们首先尝试大除数:

• 我们将 m 从 999 递减 1；
• 将 n 从 999 减 1(如果 11 整除 m，或 9% 的时间)或从 990 减 11(如果 11 不整除 m，或 91% 的时间)。

我们跟踪迄今为止在变量 q 中发现的最大回文。假设 q = r·s 其中 r <= s。我们通常有 m < r <= s。我们要求 m·n > q 或 n >= q/m。随着发现更大的回文，n 的范围变得更受限制，原因有两个:q 变大，m 变小。

附加程序的内部循环仅执行了 506 次，而使用的原始程序执行了约 810000 次。

#include <stdlib.h>
#include <stdio.h>
int main(void) {
  enum { A=100000, B=10000, C=1000, c=100, b=10, a=1, T=10 };
  int m, n, p, q=111111, r=143, s=777;
  int nDel, nLo, nHi, inner=0, n11=(999/11)*11;

  for (m=999; m>99; --m) {
    nHi = n11;  nDel = 11;
    if (m%11==0) {
      nHi = 999;  nDel = 1;
    }
    nLo = q/m-1;
    if (nLo < m) nLo = m-1;

    for (n=nHi; n>nLo; n -= nDel) {
      ++inner;
      // Check if p = product is a palindrome
      p = m * n;
      if (p%T==p/A && (p/B)%T==(p/b)%T && (p/C)%T==(p/c)%T) {
        q=p; r=m; s=n;
        printf ("%d at %d * %d\n", q, r, s);
        break;      // We're done with this value of m
      }
    }
  }
  printf ("Final result:  %d at %d * %d   inner=%d\n", q, r, s, inner);
  return 0;
}

请注意，该程序是用 C 编写的，但相同的技术也适用于 Java。