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

Secção dedicada à linguagem de programação favorita dos quarkianos: Python!

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

Mensagempor Bruno Oliveira em Quinta Set 06, 2012 2:28 am

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
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

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

Mensagempor francisco_machado em Sábado Out 20, 2012 1:01 am

Boas,

Aqui vai a ideia:


Aqui vai o código:
francisco_machado
gluão
gluão
 
Mensagens: 27
Registado: Sexta Fev 26, 2010 8:28 pm

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

Mensagempor jap em Sábado Out 20, 2012 10:30 pm

:shock:

:hands:
Obrigado, Francisco!
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

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

Mensagempor Bruno Oliveira em Terça Out 23, 2012 1:05 am

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:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

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

Mensagempor francisco_machado em Quarta Out 24, 2012 12:40 am

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.
francisco_machado
gluão
gluão
 
Mensagens: 27
Registado: Sexta Fev 26, 2010 8:28 pm


Voltar para Pitónica

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 2 visitantes