java – 找到由两个3位数字的乘积制成的最大回文

发布时间：2020-12-15 02:00:07 所属栏目：Java 来源：网络整理

导读：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(""+val

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编写的代码……除此之外还有什么有效的方法..我们可以更优化这些代码吗？

解决方法

我们假设最大的这样的回文将有六位而不是五位,因为143 * 777 = 222221是回文.

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

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

>我们从999开始向下迈进1,然后是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=222221,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 * %dn",q,r,s);
        break;      // We're done with this value of m
      }
    }
  }
  printf ("Final result:  %d at %d * %d   inner=%dn",s,inner);
  return 0;
}

注意,程序是在C中,但相同的技术将在Java中工作.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!