Project Euler: Problema 2
Explicação e solução em Java do Problema 2 do Project Euler.
Link do problema: http://projecteuler.net/problem=2
Descrição do Problema:
Cada novo termo da sequência de Fibonacci é gerado somando os dois termos anteriores. Començando por 1 e 2, os primeiros 10 termos são:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Considerandos os termos da sequência de Fibonacci cujos valores não excedem 4 milhões encontre a soma dos valores pares.
Solução:
Outro problema de força bruta, só precisamos somar os números pares.
Mas vamos tentar otimizar um pouco. Repare nos números destacados abaixo da sequência:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Temos um número par a cada 3 números da sequência. Ao invés de calcular todos os números da sequência e testar se o valor é par, podemos calcular de 3 em 3 e obter diretamente o resultado que queremos.
Código:
[code lang="java" firstline="1" toolbar="true" collapse="false" wraplines="false"]
package com.loiane.projecteuler;
public class Problem2 {
public static void main(String[] args) {
long sum = 0;
long prev = 1;
long current = 2;
long n;
while (current < 4000000){
sum = sum + current;
n = current;
current += 2 * (current + prev);
prev += 2 * n;
}
System.out.println(sum);
}
}
[/code]
Para ver a solução, basta executar o código acima.
Mais sugestões?
Lista de mais problemas do Project Euler resolvidos: http://www.loiane.com/projetos/project-euler/
Meu repositório no GitHub: https://github.com/loiane/project-euler