El Proyecto Euler: Problema 2

22/05/2008

El Proyecto Euler es una serie de problemas de programación, si quieres enterarte de que va esto, lee la introducción.

Problema 2

Cada nuevo termino en la secuencia de Fibonacci es generada agregando los dos términos previos. Comenzando con 1 y 2, los primeros 10 términos serán:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Encuentra la suma de todos los términos pares en una secuencia que no sobrepase los 4 millones.

Para resolverlo de la forma bruta, hay que construir la secuencia de Fibonnaci solamente agregando una condición donde vamos agregando una sumatoria de los números pares, esa verificación es donde muy probablemente se pueda optimizar esto. Mañana salgo de viaje, hasta fines de la siguiente semana revisare que se pudo hacer.

Por cierto, hubiera jurado que el problema antes estaba escrito con el límite de 1 millón, así tenía guardada la solución, me pregunto ¿porque lo habrán cambiado? por lo pronto el siguiente que haga sera completamente nuevo, los dos primeros ya los había resuelto cuando me registre a la página.

#include <stdio.h>
 
main()
{
    int sum = 0, a = 1, b = 1, c = 0;
    while ( c < 4000000 )
    {
        c = a + b;
        a = b;
        b = c;
 
        if ( c % 2 == 0 ) {
            sum += c;
        }
    }
 
    printf("resultado: %d\n", sum);
    return 0;
}

Conclusión

Lo mas costoso de esta solución es la comprobación de que los números sean pares, y revisando otras soluciones hay muchas formas de evitar esta comprobación.

Como bien notaron Michoacano y Xiam, resulta que si revisamos la secuencia, podemos notar que cada tercer número es par y ya sabiéndolo de antemano nos podemos evitar la comprobación y sumar solo cada tercer número.

#include <stdio.h>
 
main()
{
    int sum = 0, a = 1, b = 1, c = a + b;
    while ( c < 4000000 )
    {
        sum += c;
        a = b + c;
        b = c + a;
        c = a + b;
    }
 
    printf("resultado: %d\n", sum);
    return 0;
}

Nuevamente, esto ayudara realmente en rangos mucho mas grandes que el que tenemos.

«Anterior | Siguiente»

Hay 12 comentarios:

22/05/2008Michoacano dice:

MIra para empezar , un consejo: se supone que es programar la manera más óptima, no resolver el problema( o almenos ese es el chiste de estos retos).

Entonces a primera vista, como ves hay un patrón, dos numeros son impares, y dos pares. Esto es lógico.

Numero par+ numero impar=numero impar
numero impar + numero impar= numero par

Entonces no hace falta calcular los numeros impares, puedes solamente calcular los pares y hacer la suma, por lo que te ahorras muchas iteraciones y el if.

Posteo código despues de pensar si hay mas cosas que se pueden hacer.

22/05/2008izaac dice:

import sys
def fibonacci():
    a, b = 1, 2
    while True:
        a, b = b, a + b
        if a%2 == 0:
            yield a
        else:
            continue
 
f = fibonacci()
aux = 0
for x in range(15):
    num = f.next()
    if num < 4000000:
        aux += num
    else:
        print "\nSuma: %i" % aux
        sys.exit()

Saludos

22/05/2008izaac dice:

Mejor un paste:

http://dpaste.com/hold/52192/
23/05/2008pablasso dice:

@Michoacano Gracias por la opinión, yo lo veo mas como que hay cientos de formas de llegar a Roma, me da igual el orden de los factores, resolver, luego optimizar. Al final pongo las conclusiones.

La cosa es solucionar el problema en menos del tiempo que establecen en el proyecto (y si una solución en 1 milésima de segundo con las condiciones del problema, vamos, mala no es), y entonces puedo optimizarlo para situaciones extremas.

En fin, cualquier punto de vista es válido :-)

@izaac Gracias por la versión pythonesca, te lo pongo con las tags correctas para código (pre con atributos lang)

24/05/2008izaac dice:

Usando puros built-ins (más rápido), con ayuda de itertools:

def fibpairs():
    a, b = 1, 2
    while True:
        a, b = b, a + b
        if a%2 == 0:
            yield a
        else:
            continue
 
if __name__ == '__main__':
    import itertools
    l = list(itertools.takewhile(lambda x: x < 4000000, fibpairs()))
    print sum(l)

25/05/2008xiam dice:

Totalmente de acuerdo con pablasso, es mejor pensar y resolver el problema, luego optimizar en caso de que se necesite.

Pero por otro lado:

@Michoacano,
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887

Esos son los números de la secuencia, creo que optimizar 36 condiciones no haría tu programa más rápido de lo que ya es.

Te sugiero que observes 2, 8, 34, 144, 610, 2584, 10946… el patrón es (comenzando con el 2), un número par seguido de dos impares. O lo que es lo mismo, un par cada posición divisible por 3 (comenzando en 1). La forma “óptima” de resolverlo, la forma matemática, sería primero definiendo la función f como:

f(1) = 1, f(2) =1, f(n) = f(n-1) + f(n-2)

Después iterando naturales de la forma 3k, comenzando con 1 y mientras f(3k) < 4000000 que no se cual k corresponda pero debe ser como ~10.

Esa es la solución matemática mas “limpia” que se me ocurre y la baso en que el patrón que observamos en el que cada f(3k) es par, sin embargo, para computación la recursión es cara y sería más lenta en éste caso. La optimización en el programa de pablasso sería cambiar la c%2 por un i%3 donde i es entero, es un módulo a un número más pequeño y practicamente no tendría diferencia en velocidad.

Lo de f(3k) es verdadero y se puede demostrar por inducción. Como es parte de mi carrera y además me gustan mucho esas ñoñerías, lo acabo de demostrar en papel, si alguien está interesado en los detalles de la demostración podría transcribirla ya que no es muy larga.
25/05/2008xiam dice:
Bueno, claro que como el problema tiene solución constante, la solución mas óptima es:
1 2 3 4
#include <stdio.h> int main() { printf("%ld\n", 4613732); }
Sin tantos rodeos >:-)
25/05/2008izaac dice:

Si, las llamadas a función son costosas, sobre todo en Python que no se han optimizado las llamadas recursivas (preferible usar generators); así como también las comparaciones que Michoacano propone para excluír numeros impares.

Además quiero refutar mi propia teoría usando itertools, utilizando profile pude bajar el tiempo bajar a la mitad el tiempo de ejecución:

De 0.018 a 0.009 segundos, usando el primer código del primer post que amablemente Juan Pablo coloreó, pero utilizando xrange(). Principalmente porque se reducen las llamadas a métodos de 28 a 15 (restando las utilizadas para el profiling).

Además utilizando pyrex para generar código para el Python C API se reduce a 0.008 pero el código es idéntico al de Juan Pablo con lo cual sólo hace dos llamadas a métodos.

Aún así la respuesta más simple, casi siempre es la más acertada, por lo tanto el código de Pablo debe ser mucho más rápido por ser ANSI C y no depender de algún intérprete. Pero creo que es el approach adecuado.

25/05/2008Michoacano dice:

Ahi va mi solución

http://pastebin.com/m51e96ae1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
 
main()
{
    int  a = 1, b = 2, c = 0;
    int sum=b;
 
   do 
    {
          sum += c;
          c=3*b+2*a;
          a=2*b +a;
          b=c;
    }while ( c < 4000000 );
 
    printf("resultado: %d\n", sum);
    return 0;
}
Explico:

a=1
b=2
sum=2;

como dije no hace falta calcular los impares, pero no quiere decir que no los ocupemos.
el siguiente numero es el 3 y se calcula c= a+b =3;
pero yo no quiero el 3, quiero el 8, entonces calculo el siguiente del siguiente.

c= (a+b) +((a+b)+b);
…factorizamos;
c=b+b+b+a+a;
c=3b+2a; <—–Siguiente número par;
y al anterior que es a.
a=((a+b)+b);
a=2b+a;<—–Anterior.

Entonces nos ahorramos 2/3 de las iterraciones, y solamente calculamos los pares(aun asi como que tengo una espinita que se puede mejorar mas).

Lo de resolver el problema mas optimo o no, pues en este y en el anterior problema realmente ami manera de ver, cualquier chavo de prepa que estudie programacion los puede hacer, por eso digo que tiene mas merito proponer una solucion optima que la mas obvia y que cuando ves el problema es la primera que se te viene a la mente, que ni siquiera hace falta programarla para saber que estas bien.

Conozco estos restos y conforme avanzas , los problemas son tan dificiles que ahora si encontrar la solución es lo que vale la pena.

Digo, ami no se me hace dificil sumar dos numeros y comprobar si son par.

26/05/2008Yeru dice:

XD ese problema me lo colocaron en el primer año de la carrera! Para ese tiempo la verdad que yo lo vi extremadamente dificil!!!!! Y estoy de acuerdo contigo.. Hay muchas maneras de llegar a Roma realmente jejeje.. Luego optimizas.. Ahora bien… Si puedes hacerlo optimo a la primera entonces bien felicidades… Saludos!
30/05/2008tu papa mamasan dice:

zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
zzzzzz
zzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzz
zzzzz
zzzz

ha si…

pablasso es emo!
31/05/2008pablasso dice:

@Michoacano ¿Que es obvio? ¿Que es facil? Todo es relativo mi querido michoacas. Muchas gracias por el código!

@xiam Relacion recursiva mmm ciertamente el poco matemático que llevo dentro de mi no hubiera llegado a ella.

@izaac Muy interesante tus soluciones de Python, supongo que mientras mas grande el rango mas te beneficias de xrange porque siempre utiliza la misma memoria.

@Yeru Aaaamén.

@mamasan Este emo se va a ver a Radiohead en 10 dias y no llevara a mamasan :D

Escribe tu comentario:

Los mas frikis pueden suscribirse a los comentarios por RSS.