Ok, temos uma estratégia. Olhemos o enunciado para saber se a estratégia pode ser minimamente viável. Talvez com algumas dezenas de milhões de operações eu consiga fazer o cálculo com sucesso... note que (1 - φ) é um valor entre 0 e 1, portanto elevar ele a um número maior que 1 deixará ele mais próximo de zero.
E, nesse cálculo, os valores e fib(n + 1)
e fib(n + 2)
são memoizados ao serem calculados. E o quanto de memória eu precisaria para memoizar tudo? É um inteiro para cada índice... ou seja, precisaria de 109 inteiros para tentar memoizar todas as entradas para fib(n)
. Mas a questão é que não estamos calculando fib(n)
, mas fib(fib(n))
, o que exigiria um tanto mais de memória... de toda sorte, 1 bilhão de inteiros já exigiria (para um intierointeiro de 32 bits) 4GB de RAM só para o vetor de memoização. Bem, eu não sei quanto o URI disponibiliza, mas com certeza é menos do que isso...