寻找两个三位数乘积的最大回文数问题

Question

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

回文数是指从左到右和从右到左读取都一样的数字。由两个二位数相乘得到的最大回文数是9009 = 91 x 99。

请找出由两个三位数相乘得到的最大回文数。

我尝试了以下方法：

    #include <stdio.h>
    #include <stdlib.h>

    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. 我开始两个循环，以获得每个数字的可能性。
4. 当第一个回文出现时，我使用goto退出循环（可能不应该，但对于这样一个小程序没有太大影响）。
5. 第一个回文应该是可能的最大值，因为我从顶部向下计数。

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

1. 首先，由于这是两个三位数相乘，为了确定一个char需要容纳那个值的大小，我去了一个计算器并将999 * 999相乘，结果是6，然后我需要再加上一个，因为我从之前发布的问题中发现sprintf在末尾放置了一个\0字符。
2. 好的，现在我有了一个char，我复制了result（即int main中的i*g），并将其放入char b[7]中。
3. 然后，我只是检查了b是否与我需要检查的每个插槽硬编码相等。
4. 然后我根据情况返回1表示true，2表示false。

这对我来说似乎完全合理，但出于某种奇怪的原因它不起作用。有什么提示吗？

- thyrgle

---

你的“g”将会倒计时得太快了——你可能会发现基于回文数的解法，比如999 * 101，但真正的答案更像是997 * 867，这个更大。 - bstpierre

一个提示：乘法是可交换的，所以你可以使用 for (g = i; g > 99; g--) 来避免测试 999*100 和 100*999 两种情况。 - Emilio Silva

顺便说一下，这是goto的合法用途。 - user216441

另一种解决方法是从999999迭代到100100，然后对于每个回文数测试是否是两个三位数的乘积。 - Gabe Moothart

Answer 1

这个假设是错误的:

第一个回文数应该尽可能大，因为我是从最高位开始倒序计数。

在检查998*101 = 100798之前，你会先检查999*100 = 99900，所以显然不能依赖这一点。

- Emilio Silva

Answer 2

问题在于您找到的第一个回文数一定不是最大的。

举个例子:

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

第一个较小，但由于首先对 i 进行迭代，然后对 g 进行迭代，因此它将首先被发现。

好的，它们不是回文，但概念是相同的。

- Jack

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;
  }

- fivebob

Answer 4

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;
            }

     }

}

- Abhishek Shet

Answer 5

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

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

i > j and
g < k

（我希望这样说得通）。

- Michael Burr

Answer 6

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作为最大的回文数返回

- SURAJ

Answer 7

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

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);

}

- Anant Sharma

Answer 8

关于性能的问题。您可以使用相当简单的嵌套循环方法来复制许多产品。例如，您从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
  }
}

- JediPotPie

Answer 9

所有提供的答案都非常好，但我还是忍不住要写代码。@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<<max<<"\n";

- Taranjeet

---

尽量不要拼错用户名（例如thyrgle）。尽量添加一些提示，例如不要使用已知过小的产品：maxPalin = 100001 ... for (int lowerBound = maxPalin/i, j = i ; lowerBound <= j ; j--) - greybeard

Answer 10

我找到了这篇文章，可能会对你有所帮助。它改进了暴力破解的方法。

- Swapnil Tailor