Boa tarde pessoal,
Gostaria de um auxílio para resolver este problema(tentarei explicá-lo aseguir):
Terei que trabalhar com os numeros Fibonacci, que todos sabemos que cada numero seguinte é a soma dos dois anteriores(ex. 1, 2, 3 ,5, 8, 13, 21, 34, 55, 89…) .
Meu problema: Todo nº inteiro positivo pode ser escrito com a soma de algusn nºs Fibonacci(ex. o 100 é = 3 + 8 + 89), onde na soma não podem haver numeros usados mais de uma vez e os nºs(Fibonacci) usados não podem ser consecutivos(ex. se usou o 5, o 8 e o 3 não devem ser usados).
Como mostrei no exemplo acima, para gerar o 100 usamos 3 nºs(3 + 8 + 89), o z é a quantidade de termos usados para formar o nº, neste caso z(100) = 3, assim como o z(3) = 1(pois não pode-se usar o 1 e o 2, pois embora nºs Fibonacci os mesmos são sequenciais, que não pode-se usar aqui).
Agora que “acho” que expliquei como funciona, minha “Missão i[/i]Impossível” é: Achar a soma destes nºs “z” dos inteiros naturais de 1 a 10 milhões .
Ex. se fosse de 1 a 5, seria { z(1)=1 + z(2)=1 + z(3)=1 + z(4)=2 + z(5)=1 --> = 6 (1 + 1 + 1 + 2 + 1)}
*** Não pode-se usar tipos Inteiros Longos, usar portanto nºs com até 32 bits.
O programa deve ser o mais rápido possível
Se alguém puder me auxiliar nesta missão eu agradeço muito…
Grato,
Jeferson Neves
