Рубрики

C / C ++ Программа для n-го числа Фибоначчи

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

    Fn = Fn-1 + Fn-2

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

   F0 = 0 and F1 = 1.

Метод 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;

}

Метод 2 (динамическое программирование)

// Ряд Фибоначчи с использованием динамического программирования
#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;

}

Метод 3 (Динамическое программирование с оптимизацией пространства)

// Ряд Фибоначчи, использующий космический оптимизированный метод
#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;

}

Метод 4 (Разделяй и властвуй)

#include <stdio.h>

  
/ * Вспомогательная функция, которая умножает 2 матрицы F и M размера 2 * 2, и

  возвращает результат умножения в F [] [] * /

void multiply(int F[2][2], int M[2][2]);

  
/ * Вспомогательная функция, которая вычисляет повышение F [] [] до степени n и помещает

  результат в F [] []

  Обратите внимание, что эта функция предназначена только для fib () и не будет работать в целом

  Степенная функция * /

void power(int F[2][2], int n);

  

int fib(int n)

{

  int F[2][2] = {{1,1},{1,0}};

  if (n == 0)

      return 0;

  power(F, n-1);

  

  return F[0][0];

}

  

void multiply(int F[2][2], int M[2][2])

{

  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];

  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];

  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];

  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];

  

  F[0][0] = x;

  F[0][1] = y;

  F[1][0] = z;

  F[1][1] = w;

}

  

void power(int F[2][2], int n)

{

  int i;

  int M[2][2] = {{1,1},{1,0}};

  

  // n - 1 раз умножить матрицу на {{1,0}, {0,1}}

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

      multiply(F, M);

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

  int n = 9;

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

  getchar();

  return 0;

}

Метод 5 (Разделяй и властвуй)

#include <stdio.h>

  

void multiply(int F[2][2], int M[2][2]);

  

void power(int F[2][2], int n);

  
/ * функция, которая возвращает n-е число Фибоначчи * /

int fib(int n)

{

  int F[2][2] = {{1,1},{1,0}};

  if (n == 0)

    return 0;

  power(F, n-1);

  return F[0][0];

}

  
/ * Оптимизированная версия power () в методе 4 * /

void power(int F[2][2], int n)

{

  if( n == 0 || n == 1)

      return;

  int M[2][2] = {{1,1},{1,0}};

  

  power(F, n/2);

  multiply(F, F);

  

  if (n%2 != 0)

     multiply(F, M);

}

  

void multiply(int F[2][2], int M[2][2])

{

  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];

  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];

  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];

  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];

  

  F[0][0] = x;

  F[0][1] = y;

  F[1][0] = z;

  F[1][1] = w;

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

  int n = 9;

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

  getchar();

  return 0;

}

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

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

C / C ++ Программа для n-го числа Фибоначчи

0.00 (0%) 0 votes