2

Estou fazendo uma questão que e Fibonacci de Novo! os testes dão o resultado esperado só que dá Time limit exceeded, queria se tem uma forma mais rápida de se calcular

Meu código

#include <stdio.h>

int fat(int num);

int main()
{
  int numero, resto;
  while(scanf("%d %d", &numero, &resto) != EOF)
  {
    printf("%d\n", fat(fat(numero))%resto);
  }
}

int fat(int num)
{
  int numero1 = 0, numero2 = 1, soma;

  for(int i = 0; i < num; i++)
  {
    soma = numero1 + numero2;
    numero2 = numero1;
    numero1 = soma;
  }
  return numero1;
}
6
  • 1
    Tempo limite excedido pode indicar que o tempo não está aceitável para grandes entradas. Já tentou com as entradas extremas? Commented 27/04/2018 às 21:38
  • 1
    Já testou também o ctrl+d para simular fim da entrada padrão? Commented 27/04/2018 às 21:40
  • 1
    Aproveitando, o segredo está no módulo, para otimizar o cálculo Commented 27/04/2018 às 21:46
  • Olá Jefferson entradas só testei as que a questão forneceu, como assim o segredo está no módulo, teria outra maneira de fazer sem a utilização do operador de resto ? Commented 27/04/2018 às 23:58
  • "Como assim o segredo está no módulo?" ==> Através da operação de módulo (ou de resto, caso prefira chamá-la assim), você obtém resultados muito interessantes que permitem fazer uma quantidade muito menor de operações e chegar no mesmo resultado. Veja minha resposta para maiores detalhes Commented 29/04/2018 às 21:35

3 Respostas 3

8

Primeiro ponto, precisamos conhecer o comportamento da função para calcular Fibonacci de um número. Temos diversas alternativas. Primeiro, começar pela definição recursiva da função de Fibonacci:

def fib(n):
  if n == 1 or n == 2:
    return 1
  else:
    return fib(n-1) + fib(n-2)

Se você analizar a fundo, vai perceber que a única opção de um valor ser acrescentado ao número de retorno é quando temos na recursão a chamada para fib(1) ou fib(2). Mas, e quantas chamadas de função são feitas ao todo? Para responder a essa pergunta, criei uma função que batizei de meta_fib. Além de contar as mesmas chamadas de função do retorno de Fibonacci, também adiciono um a cada chamada recursiva. Então, meta_fib é descrita como:

def meta_fib(n):
  if n == 1 or n == 2:
    return 1
  else:
    return 1 + meta_fib(n - 1) + meta_fib(n - 2)
        

meta_fib(i), então, vai retornar quantas chamadas de função são feitas. Resolvi comparar o quanto meta_fib crescia em comparação a fib. Então, aparentemente, meta_fib(a) = 2*fib(a) - 1. Só que a função de Fibonacci tem crescimento exponencial. O @Ricardo Ribeiro colocou a fórmula em sua reposta (retornaremos a ela mais tarde):

fórmula de Fibonacci

Então, a quantidade de chamadas à função fib é:

quantas chamadas recursivas são feitas para calcular fib?

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.

[...] Sua tarefa é simples, calcular o valor do resto de Fib( Fib( N ) ) por M.

Entrada

A entrada é composta por vários 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 bilhão... Creio que φ109 é um pouco maior do que meu limite imaginário de alguns milhões de operações...

E se eu fizer com memoização? Bem, com isso eu garanto que eu não desço recursivamente duas vezes pelo mesmo fib(n). Com memoização, calcular fib(n + 2) fica mais ou menos assim (colocar com * os valores memoizados):

fib(n + 2) =
fib(n + 1) + fib(n)* =
fib(n)* + fib(n)* + fib(n - 1)*

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 inteiro 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...

Então, essa alternativa memoizada também está fora de cogitação.

E calcular de forma linear? Como você mesmo, @rafael marques, sugeriu? Bem, é feito de forma linear. Na pior das hipóteses, então, a entrada seria 1 bilhão e, para calcular o Fibonacci só disso, seriam necessárias bilhões de operações. Então, essa alternativa também não é viável...

É necessário uma abordagem mais rápida do que o(n). Talvez uma abordagem o(log n) poderia ser aceita, mas acho que uma abordagem o(1) é melhor.

Peguemos a fórmula novamente:

fórmula de Fibonacci

Preste atenção no termo do lado direito: (1 - φ)^n/sqrt(5). Se você for calcular, verá que o valor absoluto desse número é sempre menor que 0.5. Então, podemos obter o valor de fib(n) através da seguinte fórmula:

nova leitura da fórmula de Fibonacci

Fonte

Assim sendo, consigo calcular fib(n). Mas... será mesmo? Para tal, precisamos garantir que o número calculado caiba dentro do espaço de memória reservado para tal. Uma variável do tipo double só tem 53 bits de mantissa. Isso não é suficiente nem para armazenar a entrada inteira, que pode chegar a 1 bilhão, portanto precisara de uns 62 dígitos para ser armazenado. Então, o tipo double não é adequado. E long double? Bem, ele é garantidamente não menor que um double (fonte), mas em nenhum momento eu vi definição 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 possível usar esse mod m em algum lugar...

loading...

Mas, existe o período de Pisano!!

loaded!!

O período de Pisano é o tamanho do intervalo em que os números da sequência de Fibonacci começam a se repetir, mod m. O interessante desse período é que fib(n) % m = fib(n % π(m)) % m, sendo π(m) o período de Pisano para o módulo m. E o interessante é que π(m) <= 6*m. Daí, calcular fib(n) % m não é mais dependente de n, mas é o(π(m)), e como temos que π(m) = o(m), então o cálculo de uma sequência de Fibonacci módulo m é o(m). E isso está dentro do nosso aceitável.

Então, com isso, revisando aqui o nosso objeto de cálculo:

fib(fib(n))mod m

Que portanto é igual a:

fib(fib(n) % pi(m)) % m

Que portanto é igual a:

fib(fib(n % pi(pi(m))) % pi(m)) % m

Muito bem, com isso, o cálculo iterativo de fib é bom o suficiente. Voltemos a como fazer esse cálculo em breve, pois antes precisamos definir uma outra ponta solta na solução... o valor de π(m).

Diversas outras pessoas já se depararam com a necessidade de fazer o cálculo da função de Fibonacci para números grandes. Como esse rapaz do artigo. E, sim, ele foi uma das referências que encontrei quando buscava sobre o cálculo de π(m). Em resumo, é algo muito próximo de calcular o valor de fib(n), mas a ideia é que ao obter o valor 0 e, em seguida, obter o valor 1, entrou-se em laço. O número n ==> fib(n)%m == 0, fib(n + 1)%m == 1 é o tamanho do período de Pisano; ou seja, n <==> π(m).

Então, para calcular o π(m) é necessário calcular a função de Fibonacci. Para isso, vou usar a adaptação do cálculo iterativo que você fez:

def pisano(m):
    if m == 1:
        return 1
        
    """
    toda sequência tem tamanho par, então posso começar 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 not(f_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 validação é para fib(n - 1) % m == 0, fib(n) % m == 1, então aqui n é π(m) + 1 no final do laço; por isso que o retorno é n - 1, mas claro que isso poderia ser alterado (mas daí os nomes das variável fib_n, fib_n_plus_1 e fib_n_minus_1 não fariam sentido, teria de renomear).

Então, como proceder com a conta? Poderíamos usar memoização para evitar calcular duas vezes o mesmo valor de π(x). Para tal, o vetor de memória deveria ter o tamanho de mais ou menos 6 milhões de inteiros (limite superior para π(m), m <= 1000000, para realizar o cálculo de π(π(m))). Vou deixar essa parte com você. E o cálculo da sequência de Fibonacci módulo m, então? Como ficaria?

Se reparou bem, é necessário passar sempre por todos os valores da sequência de Fibonacci menores do que o período para achar o período. Talvez fosse o caso de armazenar esses valores intermediários em um vetor e acessá-los em o(1). Vou deixar para você pensar em como resolver.

Para resolver a questão, precisamos escrever fib(fib(n))%m, que batizo de fib_fib_mod. Ela seria assim:

def fib_fib_mod(n, m):
  return fib_mod(fib_mod(n, pisano(m)), m)

fib_mod:

def fib_mod(n, m):
  n = n % pisano(m)
  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 código em Python para que você precise adaptá-lo para C. E, na adpatação, fazer as mudanças necessárias para tentar otimizar o cálculo, como memoizar os diversos cálculos no meio do caminho para evitar repetir cálculos prévios. Veja funcionando para algumas entradas no ideone.

Conclusão

  • esse problema é muito mais de matemática do que programação, não seria possível pensar em resolução para ele sem conhecer as sequências de Pisano
  • sempre leia os limites da questão; se a questão disse que o máximo para uma variável é 1 bilhão, então os criadores da prova pensaram em um caso de entrada para 1 bilhão
  • mesmo que você tenha uma solução o(n), ele vai ser inutilmente lenta caso o valor de n seja muito grande, como 1 bilhão
  • teste para casos além dos casos em que o criador da prova mostrou
    aqueles ali são só meros exemplos para você se basear, ter um norte, principalmente no formato de entrada e saída de dados; muito mais do que outra coisa, as pessoas que criam essas provas gostam de mostrar de maneira a não ter dúvidas qual o formato de entrada e o formato esperado de saída
  • as vezes, a melhor otimização em um programa é sair o mais longe possível da programação e usar fórmulas mágicas, como a de cálculo do período de Pisano
1
  • 5
    A famosa frase "primeiro resolva o problema, depois escreva o código" se encaixa perfeitamente nessa solução. Só porque precisa escrever um código, não significa que o problema seja de programação.
    – Woss
    Commented 29/04/2018 às 23:19
3

Não sei se é a mais rápida, mas acredito que essa, se adaptada ao problema, vai ser aceita!!

#include <stdio.h>

int main()
{
    double n, x, y, ans;
    scanf("%lf", &n);
    x = (1 + sqrt(5))/2.0;
    y = (1 - sqrt(5))/2.0;
    ans = (pow(x,n) - pow(y,n))/sqrt(5);
    printf("%.1lf\n", ans);
    return 0;
}
1
  • 1
    Acho que você adaptar para resolver a questão em si (Fibonacci do Fibonacci de n módulo p) deixará melhor a resposta Commented 28/04/2018 às 20:55
-2

Tente este codigo: recursivo

#include <stdio.h>
int fib(int n)                            
{                                         
  if (n == 1) return 1;                   
    else 
      if (n == 2) return 1;                 
      else return fib(n - 1) + fib(n - 2);  
}                                         
int main(void)
{ 
  int n;
  scanf("%d", &n);
  printf("%d\n", fib(n));
  return 0;
}
3
  • O filho, posta seu excelente código , coelho da programação!!! não dá palpite , posta seu código!! Estamos tentando ajudar!!!
    – Casima
    Commented 28/04/2018 às 23:35
  • 1
    Servido? pt.stackoverflow.com/a/294998/64969 Commented 29/04/2018 às 20:53
  • 1
    Nossa Jefferson que resposta ótima, muito obrigado, vou estudar agora seu código Commented 30/04/2018 às 0:44

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .