Encontrar el mayor palíndromo del producto del problema de dos números de tres dígitos

Question

Así que el Proyecto Euler las Problem 4 indica lo siguiente:

Un capicúa lee los mismos en ambos sentidos. El mayor palíndromo hizo partir del producto de dos números de 2 dígitos es 9009 = 91 99.

encuentra la mayor palíndromo hecha de el producto de dos números de 3 dígitos.

He intentado lo siguiente:

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

embargo, esto no funciona. En lugar de la respuesta correcta, obtengo 580085, que supongo que es un palíndromo al menos, pero todavía no es la respuesta correcta.

Voy a explicar mi programa a partir de int main:

1. int i y int g son mis multiplicadores. Son esos dos números de tres dígitos.
2. int final es el número que almacenará el palíndromo más grande.
3. Comienzo dos veces para que los bucles vayan hacia abajo para obtener todas las posibilidades numéricas.
4. Salgo del ciclo usando un goto cuando se alcanza el primer palíndromo (probablemente no debería, pero no afecta demasiado a un pequeño programa como este).
5. El primer palíndromo debería ser el más grande posible ya que estoy contando hacia abajo desde la parte superior.

Permítanme ahora explicar mi cheque:

1. En primer lugar, ya que estos son dos números de tres dígitos que se multiplican entre sí para determinar el tamaño de un char tendría que ser para mantener ese valor Fui a una calculadora y multipliqué 999 * 999 y terminó siendo 6, entonces necesito agregar uno porque descubrí a partir de una de las preguntas que publiqué anteriormente que sprintf pone un carácter \0 al final.
2. Bien, ahora que tengo un char y todo, copié result (que i*g en int main) y lo puse en char b[7].
3. Luego, acabo de verificar b para ver si se igualaba con la codificación de cada ranura que necesitaba verificar.
4. Luego regresé en consecuencia, 1 para verdadero y 2 para falso.

Esto me parece perfectamente lógico, pero no funciona por algún motivo extraño. ¿Algún consejo?

Answer 1

Esta suposición es incorrecta:

El primer palíndromo debe ser el más grande posible, ya que estoy contando hacia abajo desde la parte superior.

Se registrará 999*100 = 99900 antes 998*101 = 100798, por lo que claramente no puedes contar con eso.

Answer 2

El primer palíndromo debe ser el más grande posible, ya que estoy contando hacia abajo desde la parte superior

El problema es que es posible que haya encontrado un palíndromo para un gran i y una pequeña g. Es posible que haya un palíndromo más grande que es el producto de j y k donde:

i > j and 
g < k 

(espero que esto tenga sentido).

Answer 3

El problema es que el primer palíndromo que encuentras no es el más grande con certeza.

Sólo un ejemplo:

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

El primero de ellos es más pequeño, pero ya que iterar por primera vez en i, a continuación, en g que se descubrió por primera vez.

Ok, no son palíndromo pero el concepto es el mismo ..

Answer 4

Palabras en el rendimiento. Tiene la posibilidad de duplicar muchos de los productos porque está utilizando un enfoque de bucle anidado bastante simple. Por ejemplo, comienza con 999 * 999 y luego 999 * 998, etc. Cuando el bucle interno finaliza, disminuirá el bucle externo y comenzará de nuevo con 998 * 999, que es lo mismo que 999 * 998.

Realmente, lo que quiere hacer es iniciar el bucle interno con el mismo valor que el valor del bucle externo actual. Esto eliminará tus operaciones duplicadas. Algo como esto ...

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

Sin embargo, como se señaló Emilio, el supuesto de que el primer palíndromo que encuentre será la respuesta es incorrecta. Primero debes calcular los números más grandes, obviamente. Entonces debes probarlos en este orden; 999 * 999, 999 * 998, 998 * 998, 999 * 997, 998 * 997, etc ...

no lo he probado, pero creo que quiere algo como esto (pseudo código):

x = 999; 
n = 0; 

while (++n <= x) 
{ 
    j = x; 
    k = j - n; 

    while (j >= k) 
    { 
    y = j-- * k; 
    if (check(y)) 
     stop looking 
    } 
} 

Answer 5

Creo que está abordando este problema de vuelta al frente. Sería más eficiente generar los palíndromos desde el más alto hasta el más bajo y luego controlarlos factorizándolos. El primero que tiene dos factores de tres dígitos es la respuesta.

p. Ej. Implementación

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 6

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 7

yo encontramos este article que podría ayudarle. Ha mejorado el enfoque de la fuerza bruta.

Answer 8

Todas las respuestas proporcionadas anteriormente son excelentes, pero aun así no pude evitar escribir el código. El código publicado por @thyrgle es absolutamente perfecto.Solo una pequeña corrección que debe hacer es simplemente verificar qué producto es el máximo. El código puede ser tan

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

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

Da a 906.609 el número palíndromo más grande