Proyecto Euler - Problema 1

Este es el primero de una serie de 232 problemas (que siguen creciendo) del proyecto Euler que ya presenté hace unos días.

El enunciado de este problema dice lo siguiente:

Si listamos todos los números naturales debajo de 10 que son múltiplos de 3 o 5, tenemos 3, 5, 6 y 9. La suma de estos múltiplos es 23.

Encuentra la suma de todos los múltiplos de 3 o 5 debajo de 1000.

Ahora bien, algo bastante común que podemos hacer, que es lo más lógico que nos sale a todos cuando queremos resolverlo, es recorrer todos los números hasta el 1000 e ir controlando que sean divisibles por alguno de esos numeros. Yendo al código (en C++) sería algo así:

main()
{
    int i,r=0;
    for(i; i < 1000; i++){
       if( (i%3==0) || (i%5==0) ){
              r = r + i;
       }
    }
    printf("%d",r);
}

Eso pedaso de código funciona genial y resuelve el problema, pero yo quiero tratar de buscarle otras formas de resolverlo.

Cuando estaba analizando cada número de los que son multiplos de 3 o 5, me encontre con un patron de distancia entre números. Todos los números estan separados por esta serie que se repite por siempre: {3,2,1,3,1,2,3}.

Teniendo esas distancia entre números no hace falta controlar si es o no divisor, solo sumanos y nada más. Es decir: 0+3=3, 3+2=5, 5+1=6, 6+3=9, 9+1=10, 10+2=12, 12+3=15. Los resultados de cada una de estas pequeñas sumas, son esos multiplos de 3 y 5.Y así sigue.

El resultado, podría ser algo así:

main()
{
    int patron[7] = {3,2,1,3,1,2,3};
    int result=0, x=0;
    for(int i=0; i < 1000; i+=patron[x-1] ){
        result += i;
        x = (x==7)? 1 : x+1;
    }
    printf("%d",result);
}

Seguramente, habra formas mas lindas de escribir ese código, pero como ya dije, lo que me gusta de esto es jugar con los números y las cuentas, no tanto si un for es o no más rapido que un while.

Escucho alternativas con gusto!

Conclusión

main()
{
    int patron[7] = {3,2,1,3,1,2,3};
    int result=0, x=0;
    for(int i=0, x=0; i < 1000; i += patron[x], x = (x==6)? 0 : x+1)
       result += i;
    printf("%d\n",result);
}

Entradas Relacionadas

Acerca de esta entrada

Estás leyendo “Proyecto Euler - Problema 1”, una entrada de vBracco

Publicada:: 19/02/09 a las 1pm

Categorías:: Desafios, Matemática, Programacion

Atajos:

Acerca

Este es el weblog de Victor Bracco, programador PHP freelance y amante de los desarrollos 2.0.

Aquí se escribre sobre proyectos de programación, webapps, lógica matemática y de vez en cuando sobre algunas otras yerbas.

Tordek

19.02.09 a las 10pm

Hay una forma O(1):

Entre 1 y N hay floor(N/k) numeros divisibles por K.

Vos querés la suma de esos números, para K=3 y K=5. Pero si simplemente sumaras los divisores correspondientes, sumarías los múltiplos de 3*5 dos veces. Entonces, querés:
suma_de_divisores(3)+suma_de_divisores(5)+suma_de_divisores(15).

Sabiendo la cantidad de divisores, podemos hacer:
for i in range(1, cantidad + 1): suma += i*3

Pero eso nos da dos pistas. La primera, es que podemos pasar el producto hacia afuera:
for i in range(1, cantidad + 1): suma+=i
suma*=3

La segunda, es que estamos sumando todos los números de 1 a n. Y eso ya aprendimos que es igual a n * (n + 1)/2. Finalmente

def suma_de_divisores(num, div):
cant = math.floor(num / div)
suma = cant * (cant + 1)/2
return suma * num

suma_de_divisores(100, 3)+suma_de_divisores(100, 5)-suma_de_divisores(100, 15)

2148

Sabo

19.02.09 a las 11pm

Efectivamente Tordek, la solución usando progresiones aritmeticas es creo la mejor que resuelve este problema y creo que también es la que más abunda por internet.

Al marge, el problema es con los multiplos hasta 1000 y no hasta 100, pero ese código igual lo resulve en un tiempo cortisimo.

Mi solución simplemente es “no tan común” y que reduce considerablemente el tiempos y los calculos sobre el primer código.

Gracias por participar y espero que comentes los problemas que siguen tambien!

20.02.09 a las 12am

De paso, en tu solución:
for(int i=0; i < 1000; i+=patron[x-1] ){

Me sorprende que siquiera funcione, dado que en el primer paso estás accediendo a patron[-1].

Una vez eliminado el -1 de ahí, podemos evitar el que el índice empiece en 1:
x = (x==7) ? 1 : x+1;
por
x = (x+1)%7

Y, dado que x sólo actua sobre el índice, y no el resultado, me parece más apropiado que sea parte del bucle:

main() { int patron[7] = {3,2,1,3,1,2,3}; int result=0;


    for(int i=0, x=0; i < 1000; i += patron[x], x = (x+1)%7)

        result += i;

printf("%d",result); }

20.02.09 a las 4am

Ahora, dos problemas interesantes (creo) relacionados a ambas soluciones:

1) Dada una lista de números A, generar una lista Restas, tal que sum(flatten(map(hallar_divisores, A))) - sum(flatten(map(hallar_divisores, Restas))) sea la suma de todos los múltiplos de A entre 1 y 1000 (asumiendo que hallar_divisores encuentra los números divisibles por k entre 1 y 1000).

2) Dada una lista de números A, generar una lista que haga la función de tu array patron.

20.02.09 a las 8am

Tordek, a menos que mi lógica me este engañando, en el primer ciclo no entra en la posición [-1]. Esa asignación de i dentro del for se ejecuta cuando finaliza cada bucle, y para el final del bucle x ya tiene un valor 1 y entonces ingresa en la posición [0].

Y por cierto, ese último código me parece mucho más lindo, solo que que demora más en resolverlo. Con números hasta 1.000.000.000 mi código esta demorando 3.5s y el tuyo 7.7s. Mas allá de eso, me parece buenisimo.

Pero poniendolo de esta forma, queda si más amigable que mi último código, y demora practicamente lo mismo

    for(int i=0, x=0; i < 1000; i += patron[x], x = (x==6)? 0 : x+1)
       result += i;
    printf("%d\n",result);

Los problemitas (creo) son bastante locos pero te escribo algunos posts si lo llegas a hacer.

20.02.09 a las 3pm

Ah, buen detalle… Un punto a favor para escribir el bucle de mi forma, supongo ;).

El segundo problema, lo resolví anoche en O(N^2) mientras intentaba dormir:
Haciendo un bucle de 0 a N con un step de k, para cada numero k, sobre un array A, poniendo 1 en A[k]. A tiene que tener suficiente espacio para sostener “una vuelta entera”. “Una vuelta entera” == MCM (conjunto de números). Ahora tenés un array booleano que te dice si los números pertenecen al conjunto (esta parte es la O(N^2), que domina la complejidad). Después, lo único que hay que hacer, es un bucle de 0 a N, calculando la diferencia entre cada par de unos.

El primero todavía está…

17.10.09 a las 7pm

WTF? ¿Por qué tengo sombrerito de Troll?

vBracco

Proyecto Euler - Problema 1

Conclusión

Entradas Relacionadas

Acerca de esta entrada

7 Comentarios

Deja tu comentario

Acerca

Proyectos

Publicidad

Últimas Entradas

Páginas

Categorías

vBracco

Proyecto Euler - Problema 1

Conclusión

Entradas Relacionadas

Acerca de esta entrada

7 Comentarios

Deja tu comentario

Acerca

Blogroll

Proyectos

Publicidad

Últimas Entradas

Páginas

Categorías