Qual a forma mais rápida de se calcular a sequencia de fibonacci

Qual a forma mais rápida de se calcular a sequencia de fibonacci

Estou fazendo uma questo que e Fibonacci de Novo os testes do o resultado esperado s que d Time limit exceeded, queria se tem uma forma mais rpida de se calcular Meu cdigo include stdio.h int fatint num; int main int numero, resto; whilescanfd d, numero, resto EOF printfdn, fatfatnumeroresto; int fatint num int numero1 0, numero2 1, soma; forint i 0; i num; i soma numero1 numero2; numero2 numero1; numero1 soma; return numero1;

No sei se a mais rpida, mas acredito que essa, se adaptada ao problema, vai ser aceita include stdio.h int main double n, x, y, ans; scanflf, n; x 1 sqrt52.0; y 1 - sqrt52.0; ans powx,n - powy,nsqrt5; printf.1lfn, ans; return 0;

Primeiro ponto, precisamos conhecer o comportamento da funo para calcular Fibonacci de um nmero. Temos diversas alternativas. Primeiro, comear pela definio recursiva da funo de Fibonacci: def fibn: if n 1 or n 2: return 1 else: return fibn-1 fibn-2 Se voc analizar a fundo, vai perceber que a nica opo de um valor ser acrescentado ao nmero de retorno quando temos na recurso a chamada para fib1 ou fib2. Mas, e quantas chamadas de funo so feitas ao todo Para responder a essa pergunta, criei uma funo que batizei de meta_fib. Alm de contar as mesmas chamadas de funo do retorno de Fibonacci, tambm adiciono um a cada chamada recursiva. Ento, meta_fib descrita como: def meta_fibn: if n 1 or n 2: return 1 else: return 1 meta_fibn - 1 meta_fibn - 2 meta_fibi, ento, vai retornar quantas chamadas de funo so feitas. Resolvi comparar o quanto meta_fib crescia em comparao a fib. Ento, aparentemente, meta_fiba 2fiba - 1. S que a funo de Fibonacci tem crescimento exponencial. O Ricardo Ribeiro colocou a frmula em sua reposta retornaremos a ela mais tarde: Ento, a quantidade de chamadas funo fib : Ok, temos uma estratgia. Olhemos o enunciado para saber se a estratgia pode ser minimamente vivel. Talvez com algumas dezenas de milhes de operaes eu consiga fazer o clculo com sucesso... note que 1 - um valor entre 0 e 1, portanto elevar ele a um nmero deixar ele mais prximo de zero. ... Sua tarefa simples, calcular o valor do resto de Fib Fib N por M. Entrada A entrada composta por vrios casos de teste e termina com EOF. Cada caso de teste consiste de uma linha com dois inteiros N e M 1 N 109, 2 M 106. ... eles pedem para calcular at 1 bilho... Creio que 109 um pouco maior do que meu limite imaginrio de alguns milhes de operaes... E se eu fizer com memoizao Bem, com isso eu garanto que eu no deso recursivamente duas vezes pelo mesmo fibn. Com memoizao, calcular fibn 2 fica mais ou menos assim colocar com os valores memoizados: fibn 2 fibn 1 fibn fibn fibn fibn - 1 E, nesse clculo, os valores e fibn 1 e fibn 2 so memoizados ao serem calculados. E o quanto de memria eu precisaria para memoizar tudo um inteiro para cada ndice... ou seja, precisaria de 109 inteiros para tentar memoizar todas as entradas para fibn. Mas a questo que no estamos calculando fibn, mas fibfibn, o que exigiria um tanto mais de memria... de toda sorte, 1 bilho de inteiros j exigiria para um intiero de 32 bits 4GB de RAM s para o vetor de memoizao. Bem, eu no sei quanto o URI disponibiliza, mas com certeza menos do que isso... Ento, essa alternativa memoizada tambm est fora de cogitao. E calcular de forma linear Como voc mesmo, rafael marques, sugeriu Bem, feito de forma linear. Na pior das hipteses, ento, a entrada seria 1 bilho e, para calcular o Fibonacci s disso, seriam necessrias bilhes de operaes. Ento, essa alternativa tambm no vivel... necessrio uma abordagem mais rpida do que on. Talvez uma abordagem olog n poderia ser aceita, mas acho que uma abordagem o1 melhor. Peguemos a frmula novamente: Preste ateno no termo do lado direito: 1 - nsqrt5. Se voc for calcular, ver que o valor absoluto desse nmero sempre menor que 0.5. Ento, podemos obter o valor de fibn atravs da seguinte frmula: Fonte Assim sendo, consigo calcular fibn. Mas... ser mesmo Para tal, precisamos garantir que o nmero calculado caiba dentro do espao de memria reservado para tal. Uma varivel do tipo double s tem 53 bits de mantissa. Isso no suficiente nem para armazenar a entrada inteira, que pode chegar a 1 bilho, portanto precisara de uns 62 dgitos para ser armazenado. Ento, o tipo double no adequado. E long double Bem, ele garantidamente no menor que um double fonte, mas em nenhum momento eu vi definio garantida dele. Talvez seja um ponto flutuante extendido do x86, que usa 64 bits de mantissa veja mais. Ou seja, nada feito ainda. Se pelo menos fosse possvel usar esse mod m em algum lugar... Mas, existe o perodo de Pisano O perodo de Pisano o tamanho do intervalo em que os nmeros da sequncia de Fibonacci comeam a se repetir, mod m. O interessante desse perodo que fibn m fibn m m, sendo m o perodo de Pisano para o mdulom. E o interessante quem 6m. Da, calcularfibn mno mais dependente den, mas om, e como temos quem om, ento o clculo de uma sequncia de Fibonacci mdulomom. E isso est dentro do nosso aceitvel. Ento, com isso, revisando aqui o nosso objeto de clculo: Que portanto igual a: Que portanto igual a: Muito bem, com isso, o clculo iterativo de fib bom o suficiente. Voltemos a como fazer esse clculo em breve, pois antes precisamos definir uma outra ponta solta na soluo... o valor de m. Diversas outras pessoas j se depararam com a necessidade de fazer o clculo da funo de Fibonacci para nmeros grandes. Como esse rapaz do artigo. E, sim, ele foi uma das referncias que encontrei quando buscava sobre o clculo de m. Em resumo, algo muito prximo de calcular o valor de fibn, mas a ideia que ao obter o valor 0 e, em seguida, obter o valor 1, entrou-se em lao. O nmero n fibnm 0, fibn 1m 1 o tamanho do perodo de Pisano; ou seja, n m. Ento, para calcular o m necessrio calcular a funo de Fibonacci. Para isso, vou usar a adaptao do clculo iterativo que voc fez: def pisanom: if m 1: return 1 toda sequncia tem tamanho par, ento posso comear de n 2 e terminar quando obter: f_n_minus_1 0 f_n 1 f_n_minus_1 1 f_n 1 n 2 while notf_n_minus_1 0 and f_n 1: f_n_plus_1 f_n f_n_minus_1 m f_n_minus_1 f_n f_n f_n_plus_1 n 1 return n - 1 Veja funcionando no ideone. Note que, aqui, minha validao para fibn - 1 m 0, fibn m 1, ento aqui n m 1 no final do lao; por isso que o retorno n - 1, mas claro que isso poderia ser alterado mas da os nomes das varivel fib_n, fib_n_plus_1 e fib_n_minus_1 no fariam sentido, teria de renomear. Ento, como proceder com a conta Poderamos usar memoizao para evitar calcular duas vezes o mesmo valor de x. Para tal, o vetor de memria deveria ter o tamanho de mais ou menos 6 milhes de inteiros limite superior para m, m 1000000, para realizar o clculo de m. Vou deixar essa parte com voc. E o clculo da sequncia de Fibonacci mdulo m, ento Como ficaria Se reparou bem, necessrio passar sempre por todos os valores da sequncia de Fibonacci menores do que o perodo para achar o perodo. Talvez fosse o caso de armazenar esses valores intermedirios em um vetor e acess-los em o1. Vou deixar para voc pensar em como resolver. Para resolver a questo, precisamos escrever fibfibnm, que batizo de fib_fib_mod. Ela seria assim: def fib_fib_modn, m: return fib_modfib_modn, pisanom, m J fib_mod: def fib_modn, m: n n pisanom if n 0: return 0 f_x_minus_1 0 f_x 1 x 1 while x n: f_x_plus_1 f_x f_x_minus_1 m f_x_minus_1 f_x f_x f_x_plus_1 x 1 return f_x Deixei o cdigo em Python para que voc precise adapt-lo para C. E, na adpatao, fazer as mudanas necessrias para tentar otimizar o clculo, como memoizar os diversos clculos no meio do caminho para evitar repetir clculos prvios. Veja funcionando para algumas entradas no ideone. Concluso esse problema muito mais de matemtica do que programao, no seria possvel pensar em resoluo para ele sem conhecer as sequncias de Pisano sempre leia os limites da questo; se a questo disse que o mximo para uma varivel 1 bilho, ento os criadores da prova pensaram em um caso de entrada para 1 bilho mesmo que voc tenha uma soluo on, ele vai ser inutilmente lenta caso o valor de n seja muito grande, como 1 bilho teste para casos alm dos casos em que o criador da prova mostrou aqueles ali so s meros exemplos para voc se basear, ter um norte, principalmente no formato de entrada e sada de dados; muito mais do que outra coisa, as pessoas que criam essas provas gostam de mostrar de maneira a no ter dvidas qual o formato de entrada e o formato esperado de sada as vezes, a melhor otimizao em um programa sair o mais longe possvel da programao e usar frmulas mgicas, como a de clculo do perodo de Pisano

Tente este codigo: recursivo include stdio.h int fibint n if n 1 return 1; else if n 2 return 1; else return fibn - 1 fibn - 2; int mainvoid int n; scanfd, n; printfdn, fibn; return 0;