查找由两个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

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

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

我们正在尝试寻找由两个3位数数字相乘的最大回文数。为了找到较大的结果，我们首先尝试使用大除数：

• 我们从999向下将m减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次，而使用的朴素程序大约为81万次。

#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中工作。