找到两个三位数字产品的最大回文问题

所以在Project Euler上， 问题4陈述如下：

回文数字读取两种方式相同。 由两个2位数字的乘积制成的最大回文是9009 = 91 99。

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

我尝试过以下方法：

#include  #include  int check(int result) { char b[7]; sprintf(b, "%d", result); if (b[0] == b[5] && b[1] == b[4] && b[2] == b[3]) { return 1; } else { return 0; } } int main () { int i; int g; int final; for (i = 999; i > 99; i--) { for (g = 999; g > 99; g--) { if (check(g*i) == 1) { final = g*i; goto here; } } } here: printf("%d", final); } 

但是，这不起作用。 而不是正确的答案，我得到580085，我认为至少是回文，但仍然不是正确的答案。

让我从int main开始解释我的程序：

1. int i和int g是我的乘数。 它们是两个三位数字。
2. int final是存储最大回文数的数字。
3. 我开始两个for循环，以获得每个数字的可能性。
4. 当达到第一个回文时，我使用goto离开循环（可能不应该，但它不会影响像这样的小程序）。
5. 第一个回文应该是最大的回归，因为我从顶部开始倒计时。

现在让我解释一下我的检查：

1. 首先，因为这是两个三位数相乘，以确定一个char需要保持该值的大小我去了一个计算器并乘以999 * 999然后它最终为6然后我需要添加一个因为我发现从我之前发布的一个问题出来， sprintf在结尾处放置一个\0字符。
2. 好吧，现在我有一个char和all，我复制了result （ i*g在int main i*g ）并把它放在char b[7] 。
3. 然后我只是通过硬编码我需要检查的每个插槽来检查b以查看它是否与自身相等。
4. 然后我相应地返回，1为真，2为假。

这对我来说似乎是完全合乎逻辑的，但它并不适用于一些奇怪的原因。 任何提示？

Answer 1

这个假设是错误的：

第一个回文应该是最大的回归，因为我从顶部开始倒计时。

您将在998*101 = 100798之前检查999*100 = 99900 ，所以很明显您不能指望它。

Answer 2

问题是你找到的第一个回文肯定不是更大的回文。

举个例子：

 i = 900, g = 850 -> 765000 i = 880, g = 960 -> 844800 

第一个是较小的，但是因为你首先在i上迭代，然后在g它将首先被发现。

好吧，他们不是回文，但概念是一样的..

Answer 3

我想你正在解决这个问题。 从最高到最低生成回文更有效，然后通过分解来检查。 第一个有两个三位数因子就是答案。

例如

  bool found = false; for (int i = 998; i >= 100; i--) { char j[7]; sprintf(j,"%d",i); j[3]= j[2]; j[4]= j[1]; j[5]= j[0]; int x =atoi(j); int limit = sqrt((float) x); for (int z = 999; z >= limit; z--) { if (x%z==0){ printf("%d",x); found = true; break; } } if (found) break; } 

Answer 4

第一个回文应该是最大的回归，因为我从顶部开始倒计时

问题是你可能找到了一个大的i和一个小g的回文。 有可能是一个更大的回文，它是j和k的乘积，其中：

 i > j and g < k 

（我希望这是有道理的）。

Answer 5

Java实现：

 public class Palindrome { public static void main(String[] args) { int i, j; int m = 1; int k =11; boolean flag = false; while (true) {; if (flag) j = m + 1; else j = m; for (i = k; i > 0; i--) { j++; int number, temp, remainder, sum = 0; number = temp = (1000 - i) * (1000 - j); while (number > 0) { remainder = number % 10; number /= 10; sum = sum * 10 + remainder; } if (sum == temp) { System.out.println("Max value:"+temp); return; } } if (flag) m++; k=k+11; flag = !flag; } } } 

Answer 6

关于表现的一个词。 您可以复制许多产品，因为您使用的是非常简单的嵌套循环方法。 例如，你从999 * 999开始，然后是999 * 998等。当内循环结束时，你将减少外循环并再次以998 * 999开始，这与999 * 998相同。

实际上，您要做的是使用与当前外部循环值相同的值启动内部循环。 这将消除您的重复操作。 这样的东西……

 for (i = 999; i > 99; i--) { for (g = i; g > 99; g--) { ... 

然而，正如Emilio指出的那样，你认为你找到的第一个回文将是答案是不正确的。 显然，你需要先计算出最大的数字。 所以你应该按照这个顺序尝试它们; 999 * 999,999 * 998,998 * 998,999 * 997,998 * 997等…

没有测试过，但我认为你想要这样的东西（伪代码）：

 x = 999; n = 0; while (++n <= x) { j = x; k = j - n; while (j >= k) { y = j-- * k; if (check(y)) stop looking } } 

Answer 7

我发现这篇文章可能会对你有帮助。 它改进了蛮力方法。

Answer 8

以上提供的所有答案都非常出色，但我仍然无法限制自己编写代码。 @thyrgle发布的代码绝对完美。 他需要做的只是略微纠正，只需检查哪个产品是最大的。 代码可以是

 int i,j,max=0,temp; for(i=999;i>=100;i--){ for(j=i;j>=100;j--){ temp=i*j; if(isPalin(temp) && temp>max){ max=temp; } } } cout< 

Answer 9

 #include #include #include int a[6]; void convertToString(int xy){ int i,t=100000; for(i=0;i<6;i++){ a[i]=xy/t; xy = xy % t; t=t/10; } } int check(){ int i; for(i=0;i<3;i++){ if(a[i]!=a[6-i]){ return 0; } } return 1; } void main(){ int x,y,xy,status=0; int i=0,j=0,p=0; for(x=999;x>99;x--){ for(y=x;y>99;y--){ xy=x*y; convertToString(xy); status = check(); if(status==1){ if(xy>p){ p=xy; i=x; j=y; } } } } printf("\nTwo numbers are %d & %d and their product is %d",i,j,p); } 

Answer 10

 x,y=999,999 k=0 pal=[] while (y>99): while (x>=100): m=x*y n=x*y while (n!=0): k=k*10+(n%10) n=int(n/10) if(m==k): if k not in pal: pal.append(k) x=x-1 k=0 else: y,x=y-1,999 pal.sort() print(pal) 

它给出906609作为最大的回文数