¿Es esta solución Project Euler # 5 más eficiente que una conocida?

aquí está mi solución a Project Euler problem #5:¿Es esta solución Project Euler # 5 más eficiente que una conocida?

#include <stdio.h> 
#include <stdint.h> 

#define N 20 

int main(int argc, char* argv[]) 
{ 
    uint64_t r = 1; 
    uint64_t i, j; 

    for(i = 2; i <= N; ++i) 
     if((j = r%i)) 
     r *= ((i%j) ? i : (i/j)); 

    printf("\n%llu\n", r); 

    return 0; 
}

Es de O eficiencia (n). He revisado algunas páginas del hilo oficial que contiene varias soluciones, pero no anoté ninguna con una eficacia de O (n) o menos. No me sorprendería si simplemente estoy implementando alguna solución conocida, pero si lo estoy, no puedo encontrarla. ¿Pensamientos?

Fuente

2010-09-03 Matt Tardiff

El problema es, el algoritmo no es del todo correcta. Por ejemplo, para 27 devuelve 722820898800, mientras que 80313433200 es más pequeño y también válido (divisible por 2..27).

En su cuerpo de bucle, parece que hace los primeros dos pasos de Euclid's algorithm para encontrar el mayor divisor común. Mientras que para números pequeños, dos pasos son suficientes, los números más grandes requieren más operaciones (por eso se usa la recursividad).

Por lo tanto, su solución puede ser fijado como esto ('mcd' significa máximo común divisor)

for(i = 2; i <= N; ++i) 
    r *= i/gcd(i, r);

Fuente

2010-09-03 03:27:27

¡Ah, ya veo! Mi algoritmo parece funcionar para los enteros 1-26, pero no 27 y superiores. ¿Sabes por qué es eso? –

@Matt ¿por qué 27 y no 24 o 29? Simplemente suerte :) En cuanto a por qué sucede en general, escribí un poco en mi respuesta. Para algunos (especialmente pequeños) números, su forma de encontrar GCD funcionará. Pero en 'i == 27' falla, atornillando la respuesta para n == 27 y superior (porque construyes la respuesta para _n + 1_ usando una respuesta para _n_). –

@Nikita Simplemente curioso, ¿qué tiempo de ejecución tomó su programa para calcular 27? –

Lo hice con papel/lápiz.

Encuentra lcm(1, 2, ..., 20) (Mínimo común múltiplo) de los números en el rango especificado. Desde aquí se puede probar que se puede reducir la solución anterior a:

lcm(11, 12, ..., 20)

que se deja como ejercicio para el readre;)

Fuente

2010-09-03 03:03:59 AraK

Esa es una observación interesante, pero ¿cómo responde eso a la pregunta? –

@NikitaRybak 'lcm' explica la respuesta de una manera más directa. Tu respuesta es implementar 'lcm', como' lcm (i, r) == i * r/gcd (i, r) '. –

Mi enfoque inicial fue muy similar a la suya y se tardaba muchísimo para producir los resultados. Éste lo hizo en unos pocos segundos Multiplicaba todos los números primos en el rango de 1 a 20 (2, 3, 5, 7, 11, 13, 17, 19) La idea era que los números primos no tienen GCD y el número elegible más pequeño tendría que ser de su producto.

acnum=0.0 
testnum=9699690 
divisor=20.0 
while acnum==0.0:  

    if testnum%divisor==0.0: 
     divisor-=1.0 

     print testnum, divisor 
    else: 
     testnum+=9699690 
     divisor=20.0 


    if divisor==1.0: 
     acnum=testnum

Huelga decir que está lejos de ser el código perfecto, pero hizo su trabajo.

Fuente

2011-09-19 10:08:08

¿Es esta solución Project Euler # 5 más eficiente que una conocida?

Respuesta

Cuestiones relacionadas