找到由两个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是回文.

如其他地方所述,6位数的10-palindrome abccba是11的倍数.这是正确的,因为*100001 + b*010010 + c*001100等于11*a*9091 + 11*b*910 + 11*C*100.因此,在我们的内循环中,如果m不是11的倍数,我们可以将n减少11步.

我们正试图找到百万以下最大的回文,这是两个3位数字的乘积.为了找到一个大的结果,我们首先尝试大的除数:

• 我们从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中工作.