Как быстрее генерировать Fibonacci

Ответ 1

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

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

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

Ответ 2

Вероятно, вам стоит заглянуть в memoization.

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

В нем есть объяснение и пример фима прямо там.

Ответ 3

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

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

Ответ 4

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

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

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

Ответ 5

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

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

#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);
}

Ответ 6

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

Ответ 7

Вы также можете использовать метод быстрого удвоения генерации ряда фибоначчи Link- http://vinayakgarg.wordpress.com/2012/11/07/fastest-way-to-compute-fibonacci-number/

Он фактически получен из результатов метода экспоненциальной матрицы.

Ответ 8

Используйте золотой коэффициент

Ответ 9

Никто не упоминал версию массива стека значений 2, поэтому я просто сделаю это для полноты.

// do not call with i == 0
uint64_t Fibonacci(uint64_t i)
{
  // we'll only use two values on stack,
  // initialized with F(1) and F(2)
  uint64_t a[2] = {1, 1};

  // We do not enter loop if initial i was 1 or 2 
  while (i-- > 2)
    // A bitwise AND allows switching the storing of the new value
    // from index 0 to index 1.
    a[i & 1] = a[0] + a[1];

    // since the last value of i was 0 (decrementing i),
    // the return value is always in a[0 & 1] => a[0].
  return a[0];
}                                                                

Это постоянное пространство стека O (n), которое будет немного отличаться от memoization при компиляции с оптимизацией.

// Calc of fibonacci f(99), gcc -O2
Benchmark            Time(ns)    CPU(ns) Iterations
BM_2stack/99                2          2  416666667
BM_memoization/99           2          2  318181818

Используемая здесь BM_memoization инициализирует массив только один раз и повторно использует его для каждого другого вызова.

Версия массива стека 2 значения выполняет идентичную версию с временной переменной при оптимизации.

Ответ 10

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

Ответ 11

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

Ответ 12

Гарантировано ли вам, что, как и в вашем примере, ввод будет предоставлен вам в порядке возрастания? Если это так, вам даже не нужна заметка; просто отслеживайте последние два результата, начинайте генерировать последовательность, но только показывайте 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
}

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

Ответ 13

Матричное умножение, нет арифметики с плавающей запятой, O (log N) временная сложность, предполагающая целочисленное умножение/добавление выполняется в постоянное время.

Здесь приведен код python

def fib(n):
    x,y = 1,1
    mat = [1,1,1,0]
    n -= 1
    while n>0:
        if n&1==1:
            x,y = x*mat[0]+y*mat[1], x*mat[2]+y*mat[3]
        n >>= 1
        mat[0], mat[1], mat[2], mat[3] = mat[0]*mat[0]+mat[1]*mat[2], mat[0]*mat[1]+mat[1]*mat[3], mat[0]*mat[2]+mat[2]*mat[3], mat[1]*mat[2]+mat[3]*mat[3]
    return x

Ответ 14

В С#:

        static int fib(int n)
        {
            if (n < 2) return n;
            if (n == 2) return 1;
            int k = n / 2;
            int a = fib(k + 1);
            int b = fib(k);
            if (n % 2 == 1)
                return a * a + b * b;
            else
                return b * (2 * a - b);
        }

Ответ 15

Google - ваш друг:

http://www.chaos.org.uk/~eddy/craft/Fibonacci.html

Ответ 16

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

Ответ 17

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

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

Фибоначчи (n) называет фибоначчи (n-1) и фибоначчи (n-2)
Фибоначчи (n-1) называет фибоначчи (n-2) и fibonacci(n-3)
Фибоначчи (n-2) вызывает fibonacci(n-3) и фибоначчи (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, а затем просто напечатайте правильный номер за одну операцию, напечатав элемент вашего массива. Таким образом, вы не вызываете функцию для каждого запроса.

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

Ответ 18

#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;
   }

Ответ 19

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

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);
}

Ответ 20

используйте любой из них: два примера рекурсии: одно с циклом O (n) и одно с золотым отношением O (1) время:

private static long fibonacciWithLoop(int input) {
    long prev = 0, curr = 1, next = 0;      
    for(int i = 1; i < input; i++){
        next = curr + prev;
        prev = curr;
        curr = next;
    }
    return curr;
}

public static long fibonacciGoldenRatio(int input) {
    double termA = Math.pow(((1 + Math.sqrt(5))/2), input);
    double termB = Math.pow(((1 - Math.sqrt(5))/2), input);
    double factor = 1/Math.sqrt(5);
    return Math.round(factor * (termA - termB));
}

public static long fibonacciRecursive(int input) {
    if (input <= 1) return input;
    return fibonacciRecursive(input - 1) + fibonacciRecursive(input - 2);
}

public static long fibonacciRecursiveImproved(int input) {
    if (input == 0) return 0;
    if (input == 1) return 1;
    if (input == 2) return 1;
    if (input >= 93) throw new RuntimeException("Input out of bounds");
    // n is odd
    if (input % 2 != 0) {
        long a = fibonacciRecursiveImproved((input+1)/2);
        long b = fibonacciRecursiveImproved((input-1)/2);
        return a*a + b*b;
    }

    // n is even
    long a = fibonacciRecursiveImproved(input/2 + 1);
    long b = fibonacciRecursiveImproved(input/2 - 1);
    return a*a - b*b;
}

Ответ 21

using namespace std;

void mult(LL A[ 3 ][ 3 ], LL B[ 3 ][ 3 ]) {

     int i,

         j,

         z;

     LL C[ 3 ][ 3 ];

     memset(C, 0, sizeof( C ));

     for(i = 1; i <= N; i++)

         for(j = 1; j <= N; j++) {

             for(z = 1; z <= N; z++)

                 C[ i ][ j ] = (C[ i ][ j ] + A[ i ][ z ] * B[ z ][ j ] % mod ) % mod;
         }

     memcpy(A, C, sizeof(C));
};

void readAndsolve() {

    int i;

    LL k;

    ifstream I(FIN);
    ofstream O(FOUT);

    I>>k;

    LL A[3][3];
    LL B[3][3];

    A[1][1] = 1; A[1][2] = 0;
    A[2][1] = 0; A[2][2] = 1;

    B[1][1] = 0; B[1][2] = 1;
    B[2][1] = 1; B[2][2] = 1;

    for(i = 0; ((1<<i) <= k); i++) {

          if( k & (1<<i) ) mult(A, B);

          mult(B, B);
    }

    O<<A[2][1];
}

//1,1,2,3,5,8,13,21,33,...

int main() {

    readAndsolve();

    return(0);
}

Ответ 22

public static int GetNthFibonacci(int n)
    {
        var previous = -1;
        var current = 1;
        int element = 0;

        while (1 <= n--)
        {
            element = previous + current;
            previous = current;
            current = element;
        }

        return element;
    }

Ответ 23

Это похоже на ответы, приведенные ранее, но с некоторыми изменениями. Запоминание, как указано в других ответах, - это еще один способ сделать это, но мне не нравится код, который не масштабируется по мере изменения технологии (размер unsigned int варьируется в зависимости от платформы), поэтому максимальное значение в последовательности, которая может быть достигнутое может также меняться, и запоминание уродливо, на мой взгляд.

#include <iostream>

using namespace std;

void fibonacci(unsigned int count) {
   unsigned int x=0,y=1,z=0;
   while(count--!=0) {
      cout << x << endl;  // you can put x in an array or whatever
      z = x;
      x = y;
      y += z;
   }
}

int main() {
   fibonacci(48);// 48 values in the sequence is the maximum for a 32-bit unsigend int
   return 0;
}

Кроме того, если вы используете <limits>, его можно написать выражение константы времени компиляции, которое даст вам самый большой индекс в последовательности, которая может быть достигнута для любого целого типа данных.

Ответ 24

#include<stdio.h>
main()
{
 int a,b=2,c=5,d;
   printf("%d %d ");
do
{
   d=b+c;
     b=c;
    c=d;
   rintf("%d ");
  }