Página 1 de 1

Para voltar à acção... com Fibonacci

MensagemEnviado: Quinta Set 06, 2012 2:28 am
por Bruno Oliveira
Olá a todos!!! :)

Decidi aqui dar um saltinho, e para compensar a minha ausência deixo-lhes uma variante de um problema engraçado que encontrei há uns tempos:

Sabendo que os números de Fibonacci são definidos pela relação recursiva:

F(n) = F(n-1) + F(n-2)

com F(0) = 1 e F(1) = 1

o objectivo consiste apenas em achar o N-ésimo número de Fibonacci reportado mod 10^9 + 7, visto que será um número muito grande... :wink:

O valor máximo de N para o qual têm de obter a resposta correcta está dado em baixo:

N = 10^{200}

Formatem o vosso input da seguinte forma:
A primeira linha contém o número de casos de teste, T. Seguem-se T linhas com os valores de N.

Output: Numa única linha, o valor do N-ésimo número de Fibonacci reportado mod 10^9 + 7.

Input:
7
1
3
4
7
34
1000
1234

Output:
1
2
3
13
5702887
517691607
460530751



Have fun!!

Bruno

Re: Para voltar à acção... com Fibonacci

MensagemEnviado: Sábado Out 20, 2012 1:01 am
por francisco_machado
Boas,

Aqui vai a ideia:


Aqui vai o código:

Re: Para voltar à acção... com Fibonacci

MensagemEnviado: Sábado Out 20, 2012 10:30 pm
por jap
:shock:

:hands:
Obrigado, Francisco!

Re: Para voltar à acção... com Fibonacci

MensagemEnviado: Terça Out 23, 2012 1:05 am
por Bruno Oliveira
Sempre a surpreender!!! :D

Um espectáculo Francisco!! Congrats!!

Eu tinha usado o algoritmo clássico de exponenciação rápida, mas esta ideia é simplesmente genial!! :hands:

Re: Para voltar à acção... com Fibonacci

MensagemEnviado: Quarta Out 24, 2012 12:40 am
por francisco_machado
Muito obrigado.
Para ser honesto, pensava que a exponenciação rápida se fazia assim, agora é que uma visita rápida ao google é que me lembrou que não tinha que fazer o pre-processamento e podia ter feito apenas recursivo. Mas com este método já fico com os valores para todos os casos, tem essa vantagem.
No entanto em ambos os casos a complexidade é igual, portanto são ambos bons.