找到由两个3位数字的乘积制成的最大回文 [英] Find the largest palindrome made from the product of two 3-digit numbers
问题描述
package testing.project;
公共类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 = 111111是回文。
如其他地方所述，一个6位数的基数10回文abccba是一个倍数这是正确的，因为* 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
for（n = nHi; n> nLo; n - = nDel）{
++ inner;
//检查p = product是否为回文
p = m * n;
if（p％T == p / A&&（p / B）％T ==（p / b）％T&&（p / C）％T ==（p / c）％T）{
q = p; R =米; S = N;
printf（％d at％d *％d \ n，q，r，s）;
休息; //我们已完成m
的这个值}
}
}
printf（最终结果：％d at％d *％d inner =％d \ n，q，r，s，inner）;
返回0;
}
注意，程序在C中，但相同的技术在Java中有效。 / p>
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);
}
}
This is the code that I wrote in Java... Is there any efficient way other than this.. And can we optimize this code more??
We suppose the largest such palindrome will have six digits rather than five, because 143*777 = 111111 is a palindrome.
As noted elsewhere, a 6-digit base-10 palindrome abccba is a multiple of 11. This is true because a*100001 + b*010010 + c*001100 is equal to 11*a*9091 + 11*b*910 + 11*c*100. So, in our inner loop we can decrease n by steps of 11 if m is not a multiple of 11.
We are trying to find the largest palindrome under a million that is a product of two 3-digit numbers. To find a large result, we try large divisors first:
- We step m downwards from 999, by 1's;
- Run n down from 999 by 1's (if 11 divides m, or 9% of the time) or from 990 by 11's (if 11 doesn't divide m, or 91% of the time).
We keep track of the largest palindrome found so far in variable q. Suppose q = r·s with r <= s. We usually have m < r <= s. We require m·n > q or n >= q/m. As larger palindromes are found, the range of n gets more restricted, for two reasons: q gets larger, m gets smaller.
The inner loop of attached program executes only 506 times, vs the ~ 810000 times the naive program used.
#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;
}
Note, the program is in C but same techniques will work in Java.
这篇关于找到由两个3位数字的乘积制成的最大回文的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
