Рубрики

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

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

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

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

    Fn = Fn-1 + Fn-2

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

   F0 = 0 and F1 = 1.

Учитывая число n, выведите n-е число Фибоначчи.
Примеры:

Input  : n = 2
Output : 1

Input  : n = 9
Output : 34

Напишите функцию int fib (int n), которая возвращает F n . Например, если n = 0, то fib () должна возвращать 0. Если n = 1, то она должна возвращать 1. При n> 1 она должна возвращать F n-1 + F n-2.

For n = 9
Output:34

Ниже приведены различные способы получения n-го числа Фибоначчи.

Метод 1 (Использовать рекурсию)
Простой метод, который является прямой рекурсивной реализацией математического рекуррентного отношения, приведенного выше.

C ++

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

using namespace std;

  

int fib(int n)

{

    if (n <= 1)

        return n;

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

}

  

int main ()

{

    int n = 9;

    cout << fib(n);

    getchar();

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

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

}

Джава

// Ряд Фибоначчи с использованием рекурсии

class fibonacci

{

    static int fib(int n)

    {

    if (n <= 1)

       return n;

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

    }

       

    public static void main (String args[])

    {

    int n = 9;

    System.out.println(fib(n));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Функция для n-го числа Фибоначчи

  

def Fibonacci(n):

    if n<0:

        print("Incorrect input")

    # Первое число Фибоначчи равно 0

    elif n==0:

        return 0

    # Второе число Фибоначчи равно 1

    elif n==1:

        return 1

    else:

        return Fibonacci(n-1)+Fibonacci(n-2)

  
# Драйверная программа

  

print(Fibonacci(9))

  
# Этот код предоставлен Сакет Моди

C #

// C # программа для серии Фибоначчи
// используя рекурсию

using System; 

  

public class GFG 

    public static int Fib(int n) 

    

        if (n <= 1) 

        

            return n; 

        

        else

        

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

        

    

          

    // код драйвера

    public static void Main(string[] args) 

    

        int n = 9;

        Console.Write(Fib(n)); 

    

  
// Этот код предоставлен Sam007

PHP

<?php
// Серия Фибоначчи
// используя рекурсию

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

function fib($n)

{

    if ($n <= 1)

        return $n;

    return fib($n - 1) + 

           fib($n - 2);

}

  
// Код драйвера

$n = 9;

echo fib($n);

  
// Этот код предоставлен aj_36
?>


Выход

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+2];   // 1 дополнительный для обработки регистра, n = 0

  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;

}

Джава

// Ряд Фибоначчи с использованием динамического программирования

class fibonacci

{

   static int fib(int n)

    {

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

    int f[] = new int[n+2]; // 1 дополнительный для обработки регистра, n = 0

    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];

    }

       

    public static void main (String args[])

    {

        int n = 9;

        System.out.println(fib(n));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

Серия Фибоначчи с использованием динамического программирования

def fibonacci(n): 

      

    # Принимая первые два нубера Фибоначчи за 0 и 1

    FibArray = [0, 1

      

    while len(FibArray) < n + 1

        FibArray.append(0

      

    if n <= 1

        return

    else

        if FibArray[n - 1] == 0

            FibArray[n - 1] = fibonacci(n - 1

  

        if FibArray[n - 2] == 0

            FibArray[n - 2] = fibonacci(n - 2

              

    FibArray[n] = FibArray[n - 2] + FibArray[n - 1

    return FibArray[n] 

      

print(fibonacci(9)) 

C #

// C # программа для серии Фибоначчи
// используя динамическое программирование

using System;

class fibonacci {

      

static int fib(int n)

    {

          

        // Объявляем массив в

        // сохранить числа Фибоначчи.

        // 1 дополнительный для обработки

        // case, n = 0

        int []f = new int[n + 2]; 

        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];

    }

      

    // Код драйвера

    public static void Main ()

    {

        int n = 9;

        Console.WriteLine(fib(n));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// Ряд Фибоначчи с использованием динамического
// Программирование

  

function fib( $n)

{

      

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

    Числа Фибоначчи. * /

      

    // 1 дополнительный для обработки кейса,

    // n = 0

    $f = array();

    $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];

}

  

$n = 9;

echo fib($n);

  
// Этот код предоставлен
// anuj_67.
?>


Выход:

34

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

}

Джава

// Java-программа для ряда Фибоначчи, использующая Space
// Оптимизированный метод

class fibonacci

{

    static int fib(int n)

    {

        int a = 0, b = 1, c;

        if (n == 0)

            return a;

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

        {

            c = a + b;

            a = b;

            b = c;

        }

        return b;

    }

  

    public static void main (String args[])

    {

        int n = 9;

        System.out.println(fib(n));

    }

}

  
// Этот код предоставлен Михиром Джоши

питон

# Функция для n-го числа Фибоначчи - Оптимизация пространства
# Принятие первых двух чисел Фибоначчи за 0 и 1

  

def fibonacci(n):

    a = 0

    b = 1

    if n < 0:

        print("Incorrect input")

    elif n == 0:

        return a

    elif n == 1:

        return b

    else:

        for i in range(2,n+1):

            c = a + b

            a = b

            b = c

        return b

  
# Драйверная программа

  

print(fibonacci(9))

  
# Этот код предоставлен Сакет Моди

C #

// C # программа для серии Фибоначчи
// используя метод Space Optimized

using System;

  

namespace Fib 

    public class GFG 

    

        static int Fib(int n) 

        

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

              

            // Вернуть первое число Фибоначчи

            if (n == 0) return a; 

      

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

            

                c = a + b; 

                a = b; 

                b = c; 

            

      

            return b; 

        

          

    // Функция драйвера

    public static void Main(string[] args) 

        

              

            int n = 9;

            Console.Write("{0} ", Fib(n)); 

        

    

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP программа для серии Фибоначчи
// используя метод Space Optimized

  

function fib( $n)

{

    $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;

}

  
// Код драйвера

$n = 9;

echo fib($n);

  
// Этот код предоставлен anuj_67.
?>


Выход :

34

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

Метод 4 (Использование мощности матрицы {{1,1}, {1,0}})
Это еще один O (n), который основан на том факте, что если мы n раз умножим матрицу M = {{1,1}, {1,0}} на себя (другими словами, вычислим мощность (M, n)), то мы получаем (n + 1) -ое число Фибоначчи как элемент в строке и столбце (0, 0) в результирующей матрице.

Матричное представление дает следующее замкнутое выражение для чисел Фибоначчи:

С

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

}

Джава

class fibonacci

{

      

    static int fib(int n)

    {

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

    if (n == 0)

        return 0;

    power(F, n-1);

      

       return F[0][0];

    }

       

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

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

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

    {

    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;

    }

  

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

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

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

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

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

    {

    int i;

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

      

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

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

        multiply(F, M);

    }

       

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

    public static void main (String args[])

    {

    int n = 9;

    System.out.println(fib(n));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Python 3

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

  
# Вспомогательная функция, которая вычисляет
# F [] [] возвести в степень n и
# помещает результат в F [] []
# Обратите внимание, что эта функция
# предназначен только для fib () и
# не будет работать как правило
# силовая функция

def fib(n):

    F = [[1, 1],

         [1, 0]]

    if (n == 0):

        return 0

    power(F, n - 1)

      

    return F[0][0]

  

def multiply(F, M):

  

    x = (F[0][0] * M[0][0] + 

         F[0][1] * M[1][0])

    y = (F[0][0] * M[0][1] +

         F[0][1] * M[1][1])

    z = (F[1][0] * M[0][0] + 

         F[1][1] * M[1][0])

    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

  

def power(F, n):

  

    M = [[1, 1],

         [1, 0]]

  

    # n - 1 раз умножить

    # матрица в {{1,0}, {0,1}}

    for i in range(2, n + 1):

        multiply(F, M)

  
Код водителя

if __name__ == "__main__":

    n = 9

    print(fib(n))

  
# Этот код добавлен
# by ChitraNayal

C #

// C # программа для поиска числа Фибоначчи.

using System;

  

class GFG {

      

    static int fib(int n)

    {

        int [,]F = new int[,] {{1, 1},

                               {1, 0} };

        if (n == 0)

            return 0;

        power(F, n-1);

          

        return F[0,0];

    }

      

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

    матрицы F и M размера 2 * 2, и помещает

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

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

    {

        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;

    }

  

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

    возвести в степень n и поставить результат

    в F [] [] Обратите внимание, что эта функция предназначена

    только для fib () и не будет работать как правило

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

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

    {

        int i;

        int [,]M = new int[,]{{1, 1},

                              {1, 0} };

          

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

        // {{1,0}, {0,1}}

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

            multiply(F, M);

    }

      

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

    public static void Main ()

    {

        int n = 9;

        Console.WriteLine(fib(n));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php 
// PHP программа для вышеуказанного подхода

function fib($n)

{

    $F = array(array(1, 1),

               array(1, 0));

    if ($n == 0)

        return 0;

    power($F, $n - 1);

      

    return $F[0][0];

}

  

function multiply(&$F, &$M)

{

$x = $F[0][0] * $M[0][0] + 

     $F[0][1] * $M[1][0];

$y = $F[0][0] * $M[0][1] + 

     $F[0][1] * $M[1][1];

$z = $F[1][0] * $M[0][0] + 

     $F[1][1] * $M[1][0];

$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;

}

  

function power(&$F, $n)

{

    $M = array(array(1, 1),

               array(1, 0));

      

    // n - 1 раз умножить

    // матрица в {{1,0}, {0,1}}

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

        multiply($F, $M);

}

  
// Код драйвера

$n = 9;

echo fib($n);

  
// Этот код добавлен
// ChitraNayal
?>



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

Метод 5 (Оптимизированный метод 4)
Способ 4 может быть оптимизирован для работы в O (Logn) временной сложности. Мы можем сделать рекурсивное умножение, чтобы получить мощность (M, n) в преобладающем методе (аналогично оптимизации, сделанной в этом посте)

С

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

}

Джава

// Ряд Фибоначчи с использованием оптимизированного метода

class fibonacci

{

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

    static int fib(int n)

    {

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

    if (n == 0)

        return 0;

    power(F, n-1);

       

    return F[0][0];

    }

       

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

    {

    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;

    }

       

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

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

    {

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

      return;

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

       

    power(F, n/2);

    multiply(F, F);

       

    if (n%2 != 0)

       multiply(F, M);

    }

      

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

    public static void main (String args[])

    {

         int n = 9;

     System.out.println(fib(n));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Python 3

# Серия Фибоначчи, использующая
# Оптимизированный метод

  
# функция, которая возвращает nth
Число Фибоначчи

def fib(n):

      

    F = [[1, 1],

         [1, 0]]

    if (n == 0):

        return 0

    power(F, n - 1)

          

    return F[0][0]

      

def multiply(F, M):

      

    x = (F[0][0] * M[0][0] + 

         F[0][1] * M[1][0])

    y = (F[0][0] * M[0][1] + 

         F[0][1] * M[1][1])

    z = (F[1][0] * M[0][0] + 

         F[1][1] * M[1][0])

    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

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

def power(F, n):

  

    if( n == 0 or n == 1):

        return;

    M = [[1, 1],

         [1, 0]];

          

    power(F, n // 2)

    multiply(F, F)

          

    if (n % 2 != 0):

        multiply(F, M)

      
Код водителя

if __name__ == "__main__":

    n = 9

    print(fib(n))

  
# Этот код добавлен
# by ChitraNayal

C #

// Серия Фибоначчи, использующая
// Оптимизированный метод

using System;

  

class GFG

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

static int fib(int n)

{

int[,] F = new int[,]{{1, 1}, 

                      {1, 0}};

if (n == 0)

    return 0;

power(F, n - 1);

  

return F[0, 0];

}

  

static void multiply(int[,] F, 

                     int[,] M)

{

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

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

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

{

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

return;

int[,] M = new int[,]{{1, 1}, 

                      {1, 0}};

  
power(F, n / 2);
multiply(F, F);

  

if (n % 2 != 0)

multiply(F, M);
}

  
// Код драйвера

public static void Main ()

{

    int n = 9;

    Console.Write(fib(n));

}
}

  
// Этот код добавлен
// ChitraNayal

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

Метод 6 (O (Log n) Время)
Ниже приведена еще одна интересная формула повторения, которую можно использовать для нахождения n-го числа Фибоначчи за O (Log n) времени.

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

Как работает эта формула?
Формула может быть получена из приведенного выше матричного уравнения.

Взяв определитель с обеих сторон, получим
(-1) n = F n + 1 F n-1 — F n 2
Более того, поскольку A n A m = A n + m для любой квадратной матрицы A, могут быть получены следующие тождества (они получены из двух разных коэффициентов матричного произведения)

F m F n + F m-1 F n-1 = F m + n-1

Положив n = n + 1,

F m F n + 1 + F m-1 F n = F m + n

Положить m = n

F 2n-1 = F n 2 + F n-1 2

F 2n = (F n-1 + F n + 1 ) F n = (2F n-1 + F n ) F n (Источник: Wiki )

Чтобы получить формулу, которую нужно доказать, нам просто нужно сделать следующее
Если n четное, мы можем положить k = n / 2
Если n нечетно, мы можем положить k = (n + 1) / 2

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ Программа для поиска n-го числа Фибоначчи в
// с O (Log n) арифметическими операциями
#include <bits/stdc++.h>

using namespace std;

  

const int MAX = 1000;

  
// Создать массив для запоминания

int f[MAX] = {0};

  
// Возвращает n-ое число Фуибоначчи, используя таблицу f []

int fib(int n)

{

    // Базовые случаи

    if (n == 0)

        return 0;

    if (n == 1 || n == 2)

        return (f[n] = 1);

  

    // Если fib (n) уже вычислен

    if (f[n])

        return f[n];

  

    int k = (n & 1)? (n+1)/2 : n/2;

  

    // Применяем вышеприведенную формулу [Примечание: значение n & 1 равно 1

    // если n нечетно, иначе 0.

    f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1))

           : (2*fib(k-1) + fib(k))*fib(k);

  

    return f[n];

}

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

int main()

{

    int n = 9;

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

    return 0;

}

Джава

// Java-программа для поиска n-го Фибоначчи
// Число с O (Log n) арифметических операций

import java.util.*;

  

class GFG {

      

    static int MAX = 1000;

    static int f[];

      

    // Возвращает n-ое число Фибоначчи, используя

    // таблица f []

    public static int fib(int n)

    {

        // Базовые случаи

        if (n == 0)

            return 0;

              

        if (n == 1 || n == 2)

            return (f[n] = 1);

       

        // Если fib (n) уже вычислен

        if (f[n] != 0)

            return f[n];

       

        int k = (n & 1) == 1? (n + 1) / 2 

                            : n / 2;

       

        // Применяем вышеприведенную формулу [Примечание значение

        // n & 1 равно 1, если n нечетно, иначе 0.

        f[n] = (n & 1) == 1? (fib(k) * fib(k) + 

                        fib(k - 1) * fib(k - 1))

                       : (2 * fib(k - 1) + fib(k)) 

                       * fib(k);

       

        return f[n];

    }

      

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

    public static void main(String[] args) 

    {

        int n = 9;

        f= new int[MAX];

        System.out.println(fib(n));

    }

}

      
// Этот код предоставлен Арнавом Кр. Мандал.

питон

# Программа Python 3 для поиска n-го числа Фибоначчи в
# с O (Log n) арифметических операций

MAX = 1000

  
# Создать массив для запоминания

f = [0] * MAX

  
# Возвращает n-е число фуйбоначи, используя таблицу f []

def fib(n) :

    # Базовые случаи

    if (n == 0) :

        return 0

    if (n == 1 or n == 2) :

        f[n] = 1

        return (f[n])

  

    # Если fib (n) уже вычислен

    if (f[n]) :

        return f[n]

  

    if( n & 1) :

        k = (n + 1) // 2

    else

        k = n // 2

  

    # Применяя приведенную выше формулу [Примечание, значение n & 1 равно 1

    # если n нечетно, иначе 0.

    if((n & 1) ) :

        f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1))

    else :

        f[n] = (2*fib(k-1) + fib(k))*fib(k)

  

    return f[n]

  

  
# Код драйвера

n = 9

print(fib(n))

  

  
# Этот код предоставлен Никитой Тивари.

C #

// C # Программа для поиска n'th
// число Фибоначчи с
// O (Log n) арифметические операции

using System;

  

class GFG

{

  

static int MAX = 1000;

static int[] f;

  
// Возвращает n-й Фибоначчи
// номер с использованием таблицы f []

public static int fib(int n)

{

    // Базовые случаи

    if (n == 0)

        return 0;

          

    if (n == 1 || n == 2)

        return (f[n] = 1);

  

    // Если fib (n) уже

    // вычисляется

    if (f[n] != 0)

        return f[n];

  

    int k = (n & 1) == 1 ? (n + 1) / 2

                         : n / 2;

  

    // Применяем вышеприведенную формулу

    // [Примечание значение n & 1 равно 1, если

    // n нечетно, иначе 0.

    f[n] = (n & 1) == 1 ? (fib(k) * fib(k) + 

                           fib(k - 1) * fib(k - 1))

                        : (2 * fib(k - 1) + fib(k)) * 

                                            fib(k);

  

    return f[n];

}

  
// Код драйвера

static void Main() 

{

    int n = 9;

    f = new int[MAX];

    Console.WriteLine(fib(n));

}
}

  
// Этот код предоставлен mits

PHP

<?php 
// PHP программа для поиска
// число Фибоначчи в с
// O (Log n) арифметические операции

  

$MAX = 1000;

  
// Возвращает n'th fuibonacci
// номер с использованием таблицы f []

function fib($n)

{

    global $MAX;

      

    // Создать массив для запоминания

    $f = array_fill(0, $MAX, NULL);

      

    // Базовые случаи

    if ($n == 0)

        return 0;

    if ($n == 1 || $n == 2)

        return ($f[$n] = 1);

  

    // Если fib (n) уже вычислен

    if ($f[$n])

        return $f[$n];

  

    $k = ($n & 1) ? ($n + 1) / 2 : $n / 2;

  

    // Применяем вышеприведенную формулу

    // [Примечание значение n & 1 равно 1, если

    // n нечетно, иначе 0.

    $f[$n] = ($n & 1) ? (fib($k) * fib($k) + 

                         fib($k - 1) * fib($k - 1)) : 

                    (2 * fib($k - 1) + fib($k)) * fib($k);

  

    return $f[$n];

}

  
// Код драйвера

$n = 9;

echo fib($n);

  
// Этот код добавлен
// ChitraNayal
?>


Выход :

34

Временная сложность этого решения составляет O (Log n), поскольку мы делим задачу на половину в каждом рекурсивном вызове.

Способ 7
Другой подход: (используя формулу)
В этом методе мы непосредственно реализуем формулу для n-го члена ряда Фибоначчи.
F n = {[( 5 + 1) / 2] ^ n} / 5
Ссылка: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html

C ++

// C ++ Программа для поиска n-го числа Фибоначчи
#include<iostream>
#include<cmath>

  

int fib(int n) {

  double phi = (1 + sqrt(5)) / 2;

  return round(pow(phi, n) / sqrt(5));

}

  
// Код драйвера

int main ()

{

  int n = 9;

  std::cout << fib(n) << std::endl;

  return 0;

}
// Этот код предоставлен Lokesh Mohanty.

С

// C Программа для поиска n-го числа Фибоначчи
#include<stdio.h>
#include<math.h>

int fib(int n) {

  double phi = (1 + sqrt(5)) / 2;

  return round(pow(phi, n) / sqrt(5));

}

int main ()

{

  int n = 9;

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

  return 0;

}

Джава

// Java-программа для поиска n-го числа Фибоначчи

import java.util.*;

  

class GFG {

  

static int fib(int n) {

double phi = (1 + Math.sqrt(5)) / 2;

return (int) Math.round(Math.pow(phi, n) 

                        / Math.sqrt(5));

}

  
// Код драйвера

public static void main(String[] args) {

        int n = 9;

    System.out.println(fib(n));

    }

}
// Этот код предоставлен PrinciRaj1992

C #

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

using System;

  

public class GFG 

{

    static int fib(int n) 

    {

    double phi = (1 + Math.Sqrt(5)) / 2;

    return (int) Math.Round(Math.Pow(phi, n) 

                            / Math.Sqrt(5)); 

    }

      

    // Код драйвера

    public static void Main() 

    {

        int n = 9;

        Console.WriteLine(fib(n));

    }

}

  
// Этот код предоставлен 29AjayKumar

PHP

<?php
// PHP программа для поиска
// число Фибоначчи

  

function fib($n

    $phi = (1 + sqrt(5)) / 2; 

    return round(pow($phi, $n) / sqrt(5)); 

  
// Код драйвера

$n = 9; 

echo fib($n) ; 

  
// Этот код предоставлен Ryuga
?>


Выход:

34

Сложность времени: O (1)
Космическая сложность: O (1)

Этот метод предоставлен Чирагом Агарвалом.

Статьи по Теме:
Большие числа Фибоначчи на Яве

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенные выше коды / алгоритмы неверны, или найдете другие способы решения той же проблемы.

Ссылки:
http://en.wikipedia.org/wiki/Fibonacci_number
http://www.ics.uci.edu/~eppstein/161/960109.html

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

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

0.00 (0%) 0 votes