Proyecto Euler # 14

Question

Yo soy la solución Actualmente, Project Euler problem 14:

La siguiente secuencia iterativa se define para el conjunto de enteros positivos:

n → n/2 (n is even) 
n → 3n + 1 (n is odd) 

Using the rule above and starting with 13, we generate the following sequence: 
       13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 

Which starting number, under one million, produces the longest chain? 

que ideó el siguiente algoritmo para resolver el problema:

• En lugar de encontrar series para ea ch número por separado, que contendrá muchos cálculos redundantes, intento desarrollar la serie hacia atrás desde 1. Es decir, empiezo desde el número y predigo el elemento anterior.
• Dado que se pueden generar series múltiples, almacene el número reciente de todas las series usando una lista vinculada. (La idea es almacenar solo aquellos elementos que tienen series más largas.)
• Haré un ciclo de esto, hasta que encuentre todos los números debajo del límite dado; el último número debajo del límite tendrá la serie más larga.

Aquí está mi código:

void series_generate(long num) 
{ 
    long n = 1; 
    addhead(n);    //add 1 to list. 
    while (n < num) 
    { 
      series *p; 
      for (p = head; p != NULL; p = p->next) 
      { 
        long bf = p->num - 1; 
        if (p->num%2 == 0 && bf != 0 && bf%3 == 0) { 
          bf /= 3; 
          if (bf != 1) 
            addhead(bf); 
          if (bf < num) 
            n++; 
        } 
        p->num *= 2; 
        if (p->num < num) 
          n++; 

      }  
    }  
} 

Here is the link to complete code. Sin embargo, no recibo las respuestas como lo esperaba. ¿Alguien puede explicar por qué este algoritmo no funcionará?

Answer 1

Está intentando construir el árbol Collatz hacia atrás, nivel por nivel. Por lo tanto, después de la k -ésima iteración del bucle interno, la lista contiene (aunque no se produjo ningún desbordamiento) todos los números que necesitan exactamente k para alcanzar 1 en su secuencia de Collatz.

Ese enfoque tiene dos problemas graves.

1. El tamaño de los niveles aumenta exponencialmente, el tamaño se duplica aproximadamente cada tres niveles. No tiene suficiente memoria para almacenar niveles pasados ​​no mucho más de 100.
2. El miembro más grande en el nivel k es 2 ^k. Dependiendo del tipo usado para el miembro num, obtienes un desbordamiento en el nivel 31, 32, 63 o 64. Luego, si usas un tipo firmado, tienes un comportamiento indefinido, probablemente números negativos en la lista, y todo se vuelve loco. Si usa tipos sin firmar, su lista contiene un 0, y todo se vuelve loco.

Como 27 necesita 111 pasos para llegar a 1, tiene un desbordamiento cada vez que num > 27, por lo tanto obtiene resultados incorrectos.