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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #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.
