Рубрики

Программа C для чисел Фибоначчи

Числа Фибоначчи — это числа в следующей последовательности целых чисел.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …… ..

В математических терминах последовательность Fn чисел Фибоначчи определяется рекуррентным соотношением

    Fn = Fn-1 + Fn-2

с начальными значениями

   F0 = 0 and F1 = 1.

С

// Ряд Фибоначчи с использованием рекурсии
#include <stdio.h>

int fib(int n)

{

    if (n <= 1)

        return n;

    return fib(n - 1) + fib(n - 2);

}

  

int main()

{

    int n = 9;

    printf("%d", fib(n));

    getchar();

    return 0;

}

Выход:

34

Сложность времени: T (n) = T (n-1) + T (n-2), которая является экспоненциальной.
Мы можем заметить, что эта реализация выполняет много повторяющихся работ (см. Следующее дерево рекурсии). Так что это плохая реализация для n-го числа Фибоначчи.

                         fib(5)   
                     /                  
               fib(4)                fib(3)   
             /                      /     
         fib(3)      fib(2)         fib(2)    fib(1)
        /             /           /      
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    
fib(1) fib(0)

Extra Space: O (n), если мы рассмотрим размер стека вызова функции, иначе O (1).

Способ 2 (использовать динамическое программирование)
Мы можем избежать повторной работы, проделанной методом 1, сохраняя вычисленные до сих пор числа Фибоначчи.

С

// Ряд Фибоначчи с использованием динамического программирования
#include <stdio.h>

  

int fib(int n)

{

    / * Объявить массив для хранения чисел Фибоначчи. * /

    int f[n + 1];

    int i;

  

    / * 0-й и 1-й номер серии - 0 и 1 * /

    f[0] = 0;

    f[1] = 1;

  

    for (i = 2; i <= n; i++) {

        / * Добавить 2 предыдущих номера в серии

         и сохранить его * /

        f[i] = f[i - 1] + f[i - 2];

    }

  

    return f[n];

}

  

int main()

{

    int n = 9;

    printf("%d", fib(n));

    getchar();

    return 0;

}

Выход:

34

Сложность времени: O (n)
Дополнительное пространство: O (n)

Метод 3 (Пространственно оптимизированный метод 2)
Мы можем оптимизировать пространство, используемое в методе 2, сохраняя два предыдущих числа только потому, что это все, что нам нужно для получения следующего числа Фибоначчи в серии.

C / C ++

// Ряд Фибоначчи, использующий космический оптимизированный метод
#include <stdio.h>

int fib(int n)

{

    int a = 0, b = 1, c, i;

    if (n == 0)

        return a;

    for (i = 2; i <= n; i++) {

        c = a + b;

        a = b;

        b = c;

    }

    return b;

}

  

int main()

{

    int n = 9;

    printf("%d", fib(n));

    getchar();

    return 0;

}

Выход:

34

Пожалуйста, обратитесь к полной статье о программе для чисел Фибоначчи для более подробной информации!

Рекомендуемые посты:

Программа C для чисел Фибоначчи

0.00 (0%) 0 votes