Нахождение наибольшего палиндрома произведения из двух трехзначных чисел

Question

Итак, в Project Euler проблема 4 гласит следующее:

Палиндромное число читается одинаково в обоих направлениях.Самый большой палиндром, полученный из произведения двух двузначных чисел, равен 9009 = 91 99.

Найдите самый большой палиндром, полученный из произведения двух трехзначных чисел.

Iпробовал следующее:

    #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. Прежде всего, так как это два трехзначных числа, умножающиеся вместе, чтобы определитьразмер, который должен был бы иметь символ для хранения этого значения, я пошел в калькулятор и умножил на 999 * 999, и в итоге получилось 6, тогда мне нужно добавить один, потому что я обнаружил из одного из вопросов, которые я разместил ранее, что sprintf ставит\0 символ в конце.
2. Хорошо, теперь, когда у меня есть символ и все, я скопировал result (который i*g в int main) и поместил его в char b[7].
3. Тогда ятолько что проверил b, чтобы увидеть, равно ли он самому себе путем жесткого кодирования каждого слота, который мне нужно проверить.
4. Затем я вернул соответственно, 1 для истины и 2 для ложной.

Мне это кажется совершенно логичным, но по какой-то странной причине это не работает.Есть намеки?

Answer 1

Это предположение неверно:

Первый палиндром должен быть максимально возможным, поскольку я веду обратный отсчет сверху.

Вы будете проверять 999*100 = 99900 до 998*101 = 100798, так что вы явно не можете рассчитывать на это.

Answer 2

Я думаю, что вы решаете эту проблему задом наперед. Было бы более эффективно генерировать палиндромы от высшего к низшему, а затем проверять их факторизацией. Первый ответ, имеющий два трехзначных коэффициента, является ответом.

, например

  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 3

Проблема в том, что первый найденный вами палиндром не самый большой.

Просто пример:

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

Первый меньше, но поскольку вы выполняете итерациюсначала на i, затем на g он будет обнаружен первым.

Хорошо, это не палиндром, но концепция та же самая.

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

     }

}

Answer 5

Первый палиндром должен быть максимально возможным, так как я веду обратный отсчет сверху

Проблема в том, что вы могли найти палиндром для большого i ималенький g.Возможно, существует более крупный палиндром, который является продуктом j и k, где:

i > j and
g < k

(надеюсь, это имеет смысл).

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 как самое большое число палиндрома

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

}

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<<max<<"\n";

Answer 9

Я нашел эту статью , которая может вам помочь.Улучшен подход грубой силы.

Answer 10

Слово о производительности.У вас есть возможность дублировать многие продукты, потому что вы используете довольно простой подход с вложенными циклами.Например, вы начинаете с 999 * 999, а затем с 999 * 998 и т. Д. Когда внутренний цикл завершится, вы уменьшите внешний цикл и начнете снова с 998 * 999, что аналогично 999 * 998.

Действительно, вы хотите запустить внутренний цикл с тем же значением, что и текущее значение внешнего цикла.Это исключит ваши дублирующие операции.Примерно так ...

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

Однако, как указал Эмилио, ваше предположение, что первым найденным вами палиндромом будет ответ, неверно.Очевидно, вам нужно сначала вычислить самые большие числа.Поэтому вы должны попробовать их в этом порядке;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
  }
}