برنامه محاسبه nامین عدد فیبوناچی — به زبان ساده

1//Fibonacci Series using Recursion 
2#include<bits/stdc++.h> 
3using namespace std; 
4  
5int fib(int n) 
6{ 
7    if (n <= 1) 
8        return n; 
9    return fib(n-1) + fib(n-2); 
10} 
11  
12int main () 
13{ 
14    int n = 9; 
15    cout << fib(n); 
16    getchar(); 
17    return 0; 
18} 
19  
20// This code is contributed 
21// by Akanksha Rai 

1//Fibonacci Series using Recursion 
2#include<stdio.h> 
3int fib(int n) 
4{ 
5   if (n <= 1) 
6      return n; 
7   return fib(n-1) + fib(n-2); 
8} 
9  
10int main () 
11{ 
12  int n = 9; 
13  printf("%d", fib(n)); 
14  getchar(); 
15  return 0; 
16} 

1//Fibonacci Series using Recursion 
2class fibonacci 
3{ 
4    static int fib(int n) 
5    { 
6    if (n <= 1) 
7       return n; 
8    return fib(n-1) + fib(n-2); 
9    } 
10       
11    public static void main (String args[]) 
12    { 
13    int n = 9; 
14    System.out.println(fib(n)); 
15    } 
16} 
17/* This code is contributed by Rajat Mishra */

1# Function for nth Fibonacci number 
2  
3def Fibonacci(n): 
4    if n<0: 
5        print("Incorrect input") 
6    # First Fibonacci number is 0 
7    elif n==0: 
8        return 0
9    # Second Fibonacci number is 1 
10    elif n==1: 
11        return 1
12    else: 
13        return Fibonacci(n-1)+Fibonacci(n-2) 
14  
15# Driver Program 
16  
17print(Fibonacci(9)) 
18  
19#This code is contributed by Saket Modi

1// C# program for Fibonacci Series  
2// using Recursion 
3using System;  
4  
5public class GFG  
6{  
7    public static int Fib(int n)  
8    {  
9        if (n <= 1)  
10        {  
11            return n;  
12        }  
13        else
14        {  
15            return Fib(n - 1) + Fib(n - 2);  
16        }  
17    }  
18          
19    // driver code 
20    public static void Main(string[] args)  
21    {  
22        int n = 9; 
23        Console.Write(Fib(n));  
24    }  
25}  
26  
27// This code is contributed by Sam007

1<?php 
2// Fibonacci Series  
3// using Recursion 
4  
5// function returns  
6// the Fibonacci number 
7function fib($n) 
8{ 
9    if ($n <= 1) 
10        return $n; 
11    return fib($n - 1) +  
12           fib($n - 2); 
13} 
14  
15// Driver Code 
16$n = 9; 
17echo fib($n); 
18  
19// This code is contributed by aj_36 
20?> 

1//Fibonacci Series using Dynamic Programming 
2#include<stdio.h> 
3  
4int fib(int n) 
5{ 
6  /* Declare an array to store Fibonacci numbers. */
7  int f[n+2];   // 1 extra to handle case, n = 0 
8  int i; 
9  
10  /* 0th and 1st number of the series are 0 and 1*/
11  f[0] = 0; 
12  f[1] = 1; 
13  
14  for (i = 2; i <= n; i++) 
15  { 
16      /* Add the previous 2 numbers in the series 
17         and store it */
18      f[i] = f[i-1] + f[i-2]; 
19  } 
20  
21  return f[n]; 
22} 
23  
24int main () 
25{ 
26  int n = 9; 
27  printf("%d", fib(n)); 
28  getchar(); 
29  return 0; 
30}

1// Fibonacci Series using Dynamic Programming 
2class fibonacci 
3{ 
4   static int fib(int n) 
5    { 
6    /* Declare an array to store Fibonacci numbers. */
7    int f[] = new int[n+2]; // 1 extra to handle case, n = 0 
8    int i; 
9       
10    /* 0th and 1st number of the series are 0 and 1*/
11    f[0] = 0; 
12    f[1] = 1; 
13      
14    for (i = 2; i <= n; i++) 
15    { 
16       /* Add the previous 2 numbers in the series 
17         and store it */
18        f[i] = f[i-1] + f[i-2]; 
19    } 
20       
21    return f[n]; 
22    } 
23       
24    public static void main (String args[]) 
25    { 
26        int n = 9; 
27        System.out.println(fib(n)); 
28    } 
29} 
30/* This code is contributed by Rajat Mishra */

1# Fibonacci Series using Dynamic Programming  
2def fibonacci(n):  
3      
4    # Taking 1st two fibonacci nubers as 0 and 1  
5    FibArray = [0, 1]  
6      
7    while len(FibArray) < n + 1:  
8        FibArray.append(0)  
9      
10    if n <= 1:  
11        return n  
12    else:  
13        if FibArray[n - 1] == 0:  
14            FibArray[n - 1] = fibonacci(n - 1)  
15  
16        if FibArray[n - 2] == 0:  
17            FibArray[n - 2] = fibonacci(n - 2)  
18              
19    FibArray[n] = FibArray[n - 2] + FibArray[n - 1]  
20    return FibArray[n]  
21      
22print(fibonacci(9))

1// C# program for Fibonacci Series  
2// using Dynamic Programming 
3using System; 
4class fibonacci { 
5      
6static int fib(int n) 
7    { 
8          
9        // Declare an array to  
10        // store Fibonacci numbers. 
11        // 1 extra to handle  
12        // case, n = 0 
13        int []f = new int[n + 2];  
14        int i; 
15          
16        /* 0th and 1st number of the  
17           series are 0 and 1 */
18        f[0] = 0; 
19        f[1] = 1; 
20          
21        for (i = 2; i <= n; i++) 
22        { 
23            /* Add the previous 2 numbers 
24               in the series and store it */
25            f[i] = f[i - 1] + f[i - 2]; 
26        } 
27          
28        return f[n]; 
29    } 
30      
31    // Driver Code 
32    public static void Main () 
33    { 
34        int n = 9; 
35        Console.WriteLine(fib(n)); 
36    } 
37} 
38  
39// This code is contributed by anuj_67.

1<?php 
2//Fibonacci Series using Dynamic 
3// Programming 
4  
5function fib( $n) 
6{ 
7      
8    /* Declare an array to store 
9    Fibonacci numbers. */
10      
11    // 1 extra to handle case, 
12    // n = 0 
13    $f = array(); 
14    $i; 
15      
16    /* 0th and 1st number of the 
17    series are 0 and 1*/
18    $f[0] = 0; 
19    $f[1] = 1; 
20      
21    for ($i = 2; $i <= $n; $i++) 
22    { 
23          
24        /* Add the previous 2 
25        numbers in the series 
26        and store it */
27        $f[$i] = $f[$i-1] + $f[$i-2]; 
28    } 
29      
30    return $f[$n]; 
31} 
32  
33$n = 9; 
34echo fib($n); 
35  
36// This code is contributed by 
37// anuj_67.  
38?> 

1// Fibonacci Series using Space Optimized Method 
2#include<stdio.h> 
3int fib(int n) 
4{ 
5  int a = 0, b = 1, c, i; 
6  if( n == 0) 
7    return a; 
8  for (i = 2; i <= n; i++) 
9  { 
10     c = a + b; 
11     a = b; 
12     b = c; 
13  } 
14  return b; 
15} 
16  
17int main () 
18{ 
19  int n = 9; 
20  printf("%d", fib(n)); 
21  getchar(); 
22  return 0; 
23}

1// Java program for Fibonacci Series using Space 
2// Optimized Method 
3class fibonacci 
4{ 
5    static int fib(int n) 
6    { 
7        int a = 0, b = 1, c; 
8        if (n == 0) 
9            return a; 
10        for (int i = 2; i <= n; i++) 
11        { 
12            c = a + b; 
13            a = b; 
14            b = c; 
15        } 
16        return b; 
17    } 
18  
19    public static void main (String args[]) 
20    { 
21        int n = 9; 
22        System.out.println(fib(n)); 
23    } 
24} 
25  
26// This code is contributed by Mihir Joshi

1# Function for nth fibonacci number - Space Optimisataion 
2# Taking 1st two fibonacci numbers as 0 and 1 
3  
4def fibonacci(n): 
5    a = 0
6    b = 1
7    if n < 0: 
8        print("Incorrect input") 
9    elif n == 0: 
10        return a 
11    elif n == 1: 
12        return b 
13    else: 
14        for i in range(2,n+1): 
15            c = a + b 
16            a = b 
17            b = c 
18        return b 
19  
20# Driver Program 
21  
22print(fibonacci(9)) 
23  
24#This code is contributed by Saket Modi

1// C# program for Fibonacci Series  
2// using Space Optimized Method 
3using System; 
4  
5namespace Fib  
6{  
7    public class GFG  
8    {  
9        static int Fib(int n)  
10        {  
11            int a = 0, b = 1, c = 0;  
12              
13            // To return the first Fibonacci number  
14            if (n == 0) return a;  
15      
16            for (int i = 2; i <= n; i++)  
17            {  
18                c = a + b;  
19                a = b;  
20                b = c;  
21            }  
22      
23            return b;  
24        }  
25          
26    // Driver function 
27    public static void Main(string[] args)  
28        {  
29              
30            int n = 9; 
31            Console.Write("{0} ", Fib(n));  
32        }  
33    }  
34}  
35  
36// This code is contributed by Sam007.

1<?php 
2// PHP program for Fibonacci Series  
3// using Space Optimized Method 
4  
5function fib( $n) 
6{ 
7    $a = 0;  
8    $b = 1;  
9    $c; 
10    $i; 
11    if( $n == 0) 
12        return $a; 
13    for($i = 2; $i <= $n; $i++) 
14    { 
15        $c = $a + $b; 
16        $a = $b; 
17        $b = $c; 
18    } 
19    return $b; 
20} 
21  
22// Driver Code 
23$n = 9; 
24echo fib($n); 
25  
26// This code is contributed by anuj_67. 
27?>

1#include <stdio.h> 
2  
3/* Helper function that multiplies 2 matrices F and M of size 2*2, and 
4  puts the multiplication result back to F[][] */
5void multiply(int F[2][2], int M[2][2]); 
6  
7/* Helper function that calculates F[][] raise to the power n and puts the 
8  result in F[][] 
9  Note that this function is designed only for fib() and won't work as general 
10  power function */
11void power(int F[2][2], int n); 
12  
13int fib(int n) 
14{ 
15  int F[2][2] = {{1,1},{1,0}}; 
16  if (n == 0) 
17      return 0; 
18  power(F, n-1); 
19  
20  return F[0][0]; 
21} 
22  
23void multiply(int F[2][2], int M[2][2]) 
24{ 
25  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
26  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
27  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
28  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1]; 
29  
30  F[0][0] = x; 
31  F[0][1] = y; 
32  F[1][0] = z; 
33  F[1][1] = w; 
34} 
35  
36void power(int F[2][2], int n) 
37{ 
38  int i; 
39  int M[2][2] = {{1,1},{1,0}}; 
40  
41  // n - 1 times multiply the matrix to {{1,0},{0,1}} 
42  for (i = 2; i <= n; i++) 
43      multiply(F, M); 
44} 
45  
46/* Driver program to test above function */
47int main() 
48{ 
49  int n = 9; 
50  printf("%d", fib(n)); 
51  getchar(); 
52  return 0; 
53}

1class fibonacci 
2{ 
3      
4    static int fib(int n) 
5    { 
6    int F[][] = new int[][]{{1,1},{1,0}}; 
7    if (n == 0) 
8        return 0; 
9    power(F, n-1); 
10      
11       return F[0][0]; 
12    } 
13       
14     /* Helper function that multiplies 2 matrices F and M of size 2*2, and 
15     puts the multiplication result back to F[][] */
16    static void multiply(int F[][], int M[][]) 
17    { 
18    int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
19    int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
20    int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
21    int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1]; 
22       
23    F[0][0] = x; 
24    F[0][1] = y; 
25    F[1][0] = z; 
26    F[1][1] = w; 
27    } 
28  
29    /* Helper function that calculates F[][] raise to the power n and puts the 
30    result in F[][] 
31    Note that this function is designed only for fib() and won't work as general 
32    power function */
33    static void power(int F[][], int n) 
34    { 
35    int i; 
36    int M[][] = new int[][]{{1,1},{1,0}}; 
37      
38    // n - 1 times multiply the matrix to {{1,0},{0,1}} 
39    for (i = 2; i <= n; i++) 
40        multiply(F, M); 
41    } 
42       
43    /* Driver program to test above function */
44    public static void main (String args[]) 
45    { 
46    int n = 9; 
47    System.out.println(fib(n)); 
48    } 
49} 
50/* This code is contributed by Rajat Mishra */

1# Helper function that multiplies  
2# 2 matrices F and M of size 2*2,  
3# and puts the multiplication 
4# result back to F[][]  
5  
6# Helper function that calculates  
7# F[][] raise to the power n and  
8# puts the result in F[][] 
9# Note that this function is  
10# designed only for fib() and  
11# won't work as general 
12# power function  
13def fib(n): 
14    F = [[1, 1], 
15         [1, 0]] 
16    if (n == 0): 
17        return 0
18    power(F, n - 1) 
19      
20    return F[0][0] 
21  
22def multiply(F, M): 
23  
24    x = (F[0][0] * M[0][0] + 
25         F[0][1] * M[1][0]) 
26    y = (F[0][0] * M[0][1] +
27         F[0][1] * M[1][1]) 
28    z = (F[1][0] * M[0][0] + 
29         F[1][1] * M[1][0]) 
30    w = (F[1][0] * M[0][1] + 
31         F[1][1] * M[1][1]) 
32      
33    F[0][0] = x 
34    F[0][1] = y 
35    F[1][0] = z 
36    F[1][1] = w 
37  
38def power(F, n): 
39  
40    M = [[1, 1], 
41         [1, 0]] 
42  
43    # n - 1 times multiply the 
44    # matrix to {{1,0},{0,1}} 
45    for i in range(2, n + 1): 
46        multiply(F, M) 
47  
48# Driver Code 
49if __name__ == "__main__": 
50    n = 9
51    print(fib(n)) 
52  
53# This code is contributed  
54# by ChitraNayal

1// C# program to find fibonacci number. 
2using System; 
3  
4class GFG { 
5      
6    static int fib(int n) 
7    { 
8        int [,]F = new int[,] {{1, 1}, 
9                               {1, 0} }; 
10        if (n == 0) 
11            return 0; 
12        power(F, n-1); 
13          
14        return F[0,0]; 
15    } 
16      
17    /* Helper function that multiplies 2  
18    matrices F and M of size 2*2, and puts 
19    the multiplication result back to F[][] */
20    static void multiply(int [,]F, int [,]M) 
21    { 
22        int x = F[0,0]*M[0,0] + F[0,1]*M[1,0]; 
23        int y = F[0,0]*M[0,1] + F[0,1]*M[1,1]; 
24        int z = F[1,0]*M[0,0] + F[1,1]*M[1,0]; 
25        int w = F[1,0]*M[0,1] + F[1,1]*M[1,1]; 
26          
27        F[0,0] = x; 
28        F[0,1] = y; 
29        F[1,0] = z; 
30        F[1,1] = w; 
31    } 
32  
33    /* Helper function that calculates F[][]  
34    raise to the power n and puts the result 
35    in F[][] Note that this function is designed 
36    only for fib() and won't work as general 
37    power function */
38    static void power(int [,]F, int n) 
39    { 
40        int i; 
41        int [,]M = new int[,]{{1, 1}, 
42                              {1, 0} }; 
43          
44        // n - 1 times multiply the matrix to 
45        // {{1,0},{0,1}} 
46        for (i = 2; i <= n; i++) 
47            multiply(F, M); 
48    } 
49      
50    /* Driver program to test above function */
51    public static void Main () 
52    { 
53        int n = 9; 
54        Console.WriteLine(fib(n)); 
55    } 
56} 
57  
58// This code is contributed by anuj_67.

1<?php  
2// PHP program for above approach 
3function fib($n) 
4{ 
5    $F = array(array(1, 1), 
6               array(1, 0)); 
7    if ($n == 0) 
8        return 0; 
9    power($F, $n - 1); 
10      
11    return $F[0][0]; 
12} 
13  
14function multiply(&$F, &$M) 
15{ 
16$x = $F[0][0] * $M[0][0] +  
17     $F[0][1] * $M[1][0]; 
18$y = $F[0][0] * $M[0][1] +  
19     $F[0][1] * $M[1][1]; 
20$z = $F[1][0] * $M[0][0] +  
21     $F[1][1] * $M[1][0]; 
22$w = $F[1][0] * $M[0][1] + 
23     $F[1][1] * $M[1][1]; 
24  
25$F[0][0] = $x; 
26$F[0][1] = $y; 
27$F[1][0] = $z; 
28$F[1][1] = $w; 
29} 
30  
31function power(&$F, $n) 
32{ 
33    $M = array(array(1, 1), 
34               array(1, 0)); 
35      
36    // n - 1 times multiply the 
37    // matrix to {{1,0},{0,1}} 
38    for ($i = 2; $i <= $n; $i++) 
39        multiply($F, $M); 
40} 
41  
42// Driver Code 
43$n = 9; 
44echo fib($n); 
45  
46// This code is contributed  
47// by ChitraNayal 
48?>

1#include <stdio.h> 
2  
3void multiply(int F[2][2], int M[2][2]); 
4  
5void power(int F[2][2], int n); 
6  
7/* function that returns nth Fibonacci number */
8int fib(int n) 
9{ 
10  int F[2][2] = {{1,1},{1,0}}; 
11  if (n == 0) 
12    return 0; 
13  power(F, n-1); 
14  return F[0][0]; 
15} 
16  
17/* Optimized version of power() in method 4 */
18void power(int F[2][2], int n) 
19{ 
20  if( n == 0 || n == 1) 
21      return; 
22  int M[2][2] = {{1,1},{1,0}}; 
23  
24  power(F, n/2); 
25  multiply(F, F); 
26  
27  if (n%2 != 0) 
28     multiply(F, M); 
29} 
30  
31void multiply(int F[2][2], int M[2][2]) 
32{ 
33  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
34  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
35  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
36  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1]; 
37  
38  F[0][0] = x; 
39  F[0][1] = y; 
40  F[1][0] = z; 
41  F[1][1] = w; 
42} 
43  
44/* Driver program to test above function */
45int main() 
46{ 
47  int n = 9; 
48  printf("%d", fib(9)); 
49  getchar(); 
50  return 0; 
51}

1//Fibonacci Series using  Optimized Method 
2class fibonacci 
3{ 
4    /* function that returns nth Fibonacci number */
5    static int fib(int n) 
6    { 
7    int F[][] = new int[][]{{1,1},{1,0}}; 
8    if (n == 0) 
9        return 0; 
10    power(F, n-1); 
11       
12    return F[0][0]; 
13    } 
14       
15    static void multiply(int F[][], int M[][]) 
16    { 
17    int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
18    int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
19    int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
20    int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1]; 
21      
22    F[0][0] = x; 
23    F[0][1] = y; 
24    F[1][0] = z; 
25    F[1][1] = w; 
26    } 
27       
28    /* Optimized version of power() in method 4 */
29    static void power(int F[][], int n) 
30    { 
31    if( n == 0 || n == 1) 
32      return; 
33    int M[][] = new int[][]{{1,1},{1,0}}; 
34       
35    power(F, n/2); 
36    multiply(F, F); 
37       
38    if (n%2 != 0) 
39       multiply(F, M); 
40    } 
41      
42    /* Driver program to test above function */ 
43    public static void main (String args[]) 
44    { 
45         int n = 9; 
46     System.out.println(fib(n)); 
47    } 
48} 
49/* This code is contributed by Rajat Mishra */

1# Fibonacci Series using  
2# Optimized Method 
3  
4# function that returns nth  
5# Fibonacci number  
6def fib(n): 
7      
8    F = [[1, 1], 
9         [1, 0]] 
10    if (n == 0): 
11        return 0
12    power(F, n - 1) 
13          
14    return F[0][0] 
15      
16def multiply(F, M): 
17      
18    x = (F[0][0] * M[0][0] + 
19         F[0][1] * M[1][0]) 
20    y = (F[0][0] * M[0][1] + 
21         F[0][1] * M[1][1]) 
22    z = (F[1][0] * M[0][0] + 
23         F[1][1] * M[1][0]) 
24    w = (F[1][0] * M[0][1] + 
25         F[1][1] * M[1][1]) 
26      
27    F[0][0] = x 
28    F[0][1] = y 
29    F[1][0] = z 
30    F[1][1] = w 
31          
32# Optimized version of 
33# power() in method 4  
34def power(F, n): 
35  
36    if( n == 0 or n == 1): 
37        return; 
38    M = [[1, 1], 
39         [1, 0]]; 
40          
41    power(F, n // 2) 
42    multiply(F, F) 
43          
44    if (n % 2 != 0): 
45        multiply(F, M) 
46      
47# Driver Code 
48if __name__ == "__main__": 
49    n = 9
50    print(fib(n)) 
51  
52# This code is contributed  
53# by ChitraNayal

1// Fibonacci Series using  
2// Optimized Method 
3using System; 
4  
5class GFG 
6{ 
7/* function that returns  
8nth Fibonacci number */
9static int fib(int n) 
10{ 
11int[,] F = new int[,]{{1, 1},  
12                      {1, 0}}; 
13if (n == 0) 
14    return 0; 
15power(F, n - 1); 
16  
17return F[0, 0]; 
18} 
19  
20static void multiply(int[,] F,  
21                     int[,] M) 
22{ 
23int x = F[0, 0] * M[0, 0] +  
24        F[0, 1] * M[1, 0]; 
25int y = F[0, 0] * M[0, 1] +  
26        F[0, 1] * M[1, 1]; 
27int z = F[1, 0] * M[0, 0] +  
28        F[1, 1] * M[1, 0]; 
29int w = F[1, 0] * M[0, 1] +  
30        F[1, 1] * M[1, 1]; 
31  
32F[0, 0] = x; 
33F[0, 1] = y; 
34F[1, 0] = z; 
35F[1, 1] = w; 
36} 
37  
38/* Optimized version of  
39power() in method 4 */
40static void power(int[,] F, int n) 
41{ 
42if( n == 0 || n == 1) 
43return; 
44int[,] M = new int[,]{{1, 1},  
45                      {1, 0}}; 
46  
47power(F, n / 2); 
48multiply(F, F); 
49  
50if (n % 2 != 0) 
51multiply(F, M); 
52} 
53  
54// Driver Code 
55public static void Main () 
56{ 
57    int n = 9; 
58    Console.Write(fib(n)); 
59} 
60} 
61  
62// This code is contributed 
63// by ChitraNayal