斐波拉契数列

澳门威尼斯人手机版 ,斐波拉契数列,斐波契数列

写一个函数,输入n,其斐波那契数列的第n项。

威尼斯官方网站 ,  斐波这契数列的定义如下:

  • 威尼斯官方网站 1
  • 威尼斯官方网站 2
  • 威尼斯官方网站 3

 1 #include "stdafx.h"
 2 #include<iostream>
 3 using namespace std;
 4 
 5 
 6 //方法1 递归  缺点:效率低 
 7 long long Fibonacci_Solution1(unsigned int n )
 8  {
 9      if(n <= 0)
10          return 0;
11 
12      if( n == 1)
13          return 1;
14 
15      return Fibonacci_Solution1(n-1) + Fibonacci_Solution1(n-2);
16  }
17 
18 //方法2 循环 
19  long long Fibonacci_Solution2(unsigned int n)
20  {
21      int result[2] = {0,1};
22      if(n < 2)
23          return result[n];
24 
25      long long fibNMinusOne = 1;
26      long long fibNMinusTwo = 0;
27      long long fibN = 0;
28 
29      for(unsigned int i = 2 ; i <= n ; ++i)
30      {
31          fibN = fibNMinusOne + fibNMinusTwo;
32 
33          fibNMinusTwo = fibNMinusOne;
34          fibNMinusOne = fibN;
35      }
36 
37      return fibN;
38  }
39  
40  //方法3 循环 其实和方法2差不多 
41  long long Fibonacci_Solution3(unsigned int n)
42  {
43      if(n <= 0)
44          return 0;
45      else if(n == 1)
46          return 1;
47      else
48      {
49          int *array = new int[n+1];
50          array[0] = 0;
51          array[1] = 1;
52          for(int i = 2; i<= n; i++)
53              array[i] = array[i-1] + array[i-2];
54 
55          int result = array[n];
56          delete[] array;
57 
58          return result;
59       }
60  }
61 
62 //方法4 数学归纳法 略
63 
64  
65  int main()
66  {
67      int num1 = Fibonacci_Solution1(30);
68      int num2 = Fibonacci_Solution2(30);
69      int num3 = Fibonacci_Solution3(30);
70      
71      cout << num1 <<endl;
72      cout << num2 <<endl;
73      cout << num3 <<endl;
74     
75     return 0;
76  }

 运行结果如下:

威尼斯官方网站 4

写三个函数,输入n,其斐波这契数列的第n项。 斐波那契数列的定义如下: 1
#include ” stdafx.h ” 2 #includeiostream…

递归写法:

#include<stdio.h>

int main()
{
    int n,i,j;
    long long a[46];
    a[0]=0;
    a[1]=1;
    for(i=2;i<46;i++)
        a[i]=a[i-1]+a[i-2];
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&j);
            printf("%ld\n",a[j]);

    }
}

威尼斯官方网站 5

 

相关文章