Как генерировать Fibonacci, быстрее [дубликат]

В функциональном программировании есть специальный алгоритм подсчета Фибоначчи. Алгоритм использует накопительную рекурсию. Накопительная рекурсия используется для минимизации размера стека, используемого алгоритмами. Думаю, это поможет вам сократить время. Вы можете попробовать, если хотите.

int ackFib (int n, int m, int count){
    if (count == 0)
        return m;
    else
        return ackFib(n+m, n, count-1);
}



int fib(int n)
{
 return ackFib (0, 1, n+1);
}

Вы можете уменьшить накладные расходы оператора if: Рекурсивное вычисление чисел Фибоначчи в C

Создайте массив Answer [100], в котором вы кэшируете результаты функции fibonacci (n). Проверьте свой код Фибоначчи, чтобы узнать, вычислили ли вы ответ заранее, и используйте этот результат. Результаты вас удивят.

Используйте золотое сечение

Используйте мемоизацию . То есть вы кешируете ответы, чтобы избежать ненужных рекурсивных вызовов.

Вот пример кода:

#include <stdio.h>

int memo[10000]; // adjust to however big you need, but the result must fit in an int
                 // and keep in mind that fibonacci values grow rapidly :)

int fibonacci(int n) {
  if (memo[n] != -1)
    return memo[n];

  if (n==1 || n==2)
    return 1;
  else
    return memo[n] = fibonacci(n-1) +fibonacci(n-2);
}
int main() {
  for(int i = 0; i < 10000; ++i)
    memo[i] = -1;
  fibonacci(50);
}

Посмотрите в Википедии, есть формула , которая дает число в последовательности Фибоначчи без какой-либо рекурсии

. Гарантировано ли вам, что, как в вашем примере, ввод будет предоставлен вам в порядке возрастания? Если это так, вам даже не нужна мемоизация; просто отслеживайте последние два результата, начинайте генерировать последовательность, но отображайте только N-е число в последовательности, если N - это следующий индекс в вашем вводе. Остановитесь при достижении индекса 0.

Примерно так:

int i = 0;
while ( true ) {
    i++; //increment index
    fib_at_i = generate_next_fib()
    while ( next_input_index() == i ) {
        println fib_at_i
}

Я оставляю условия выхода и фактически генерирую вам последовательность.

Ваш алгоритм рекурсивен и имеет примерно O (2 ^ N) сложность.

Эта проблема уже обсуждалась в stackoverflow раньше: Вычислительная сложность последовательности Фибоначчи

В этом конкретном обсуждении также опубликована более быстрая реализация.

Вы можете просто использовать хвостовую рекурсивную версию функции, которая возвращает два последних числа Фибоначчи, если у вас есть ограничение на память.

int fib(int n)
{
    int a = 0;
    int b = 1;
    while (n-- > 1) {
        int t = a;
        a = b;
        b += t;
    }
    return b;
}

Это O(n) и требует постоянного пространства.

Прежде всего, вы можете использовать мемоизацию или итеративную реализацию того же алгоритма.

Рассмотрим количество рекурсивных вызовов, которые делает ваш алгоритм:

fibonacci(n) вызывает fibonacci(n-1) и fibonacci(n-2)
fibonacci(n-1) вызывает fibonacci(n-2) и fibonacci(n-3)
fibonacci(n-2) вызывает fibonacci(n-3) и fibonacci(n-4)

Заметили закономерность? Вы вычисляете одну и ту же функцию гораздо большее количество раз, чем нужно.

Итеративная реализация будет использовать массив:

int fibonacci(int n) {
    int arr[maxSize + 1]; 
    arr[1] = arr[2] = 1; // ideally you would use 0-indexing, but I'm just trying to get a point across
    for ( int i = 3; i <= n; ++i )
        arr[i] = arr[i - 1] + arr[i - 2]; 

    return arr[n];
}

Это уже намного быстрее, чем ваш подход. Вы можете сделать это быстрее по тому же принципу, построив массив только один раз до максимального значения n, а затем просто вывести правильное число за одну операцию, печатая элемент вашего массива. Таким образом, вы не будете вызывать функцию для каждого запроса.

Если вы не можете позволить себе начальное время предварительного вычисления (но это обычно происходит только в том случае, если вас просят вывести результат по модулю, иначе, вероятно, не ожидают, что вы реализуете арифметику больших чисел, и предварительное вычисление - лучшее решение), прочитайте вики-страницу fibonacci о других методах. Сосредоточьтесь на матричном подходе, его очень полезно знать в конкурсе.

#include<stdio.h>

 int g(int n,int x,int y)
   {
   return n==0 ? x : g(n-1,y,x+y);}

 int f(int n)
   {
   return g(n,0,1);}

 int main (void)
   {  
   int i;
   for(i=1; i<=10 ; i++)
     printf("%d\n",f(i)
   return 0;
   }

Это можно сделать с помощью умножения матрицы, возводя матрицу в степень n, а затем умножая ее на вектор. Вы можете возвести его в степень за логарифмическое время.

Я думаю, вы можете найти задачу здесь. Она на румынском языке, но вы можете перевести ее с помощью google translate. Это именно то, что вам нужно, и решение приведено там.

Вам, вероятно, следует заняться мемоизацией.

http://en.wikipedia.org/wiki/Memoization

Здесь есть объяснение и пример выдумки

Можете ли вы опубликовать файл input.txt и ограничения по времени? Кстати: Эта задача хорошо известна. Вы читали следующее http://www.ics.uci.edu/~eppstein/161/960109.html ?