实现斐波那契数列的三种方法
本帖最后由 ktpd 于 2016-11-12 18:33 编辑斐波那契数列又称黄金分割数列。它的特点是从第3个数开始，每一个数都等于前面两个数相加。例：0 1 1 2 3 5 8 13 21.。。。。。从上我们可以总结出以下规律: http://img.blog.csdn.net/20160906170209769?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center当n =0时； F(n) = 0;当n = 1时； F(n) = 1;当n > 1时；F(n) = F(n-1)+F(n-2);
那我们如何求出这个数列中第n个数是多少呢？
（一）以指针实现斐波那契数列
#include<iostream>
#include<cassert>
using namespace std;
/*
时间复杂度：O(N)
空间复杂度：0(N)
*/
long long Fib(long longn)//当n = 30时，斐波那契数已经很大了，所以我们把类型定义为long long
{
assert(n >= 0);//n必须大于0
if(n==0||n==1)
{
return n;
}
// 建立一个指针，并为该指针开辟空间
//因为数列最开始有一个0，所以当我们求第n个数的时候，需要多开劈一个空间
long long *p = new long long;
p = 0;
p = 1;
for(int i = 2;i < n+1; i++)
{
//从下标为2的数开始，每个数都等于它前面两个数相加
p = p+p;
}
//返回要找的第n个数
return p;
}
（二）交替相加法（我自己起的名字）建立一个first变量，一个second变量，一个third变量。third = first + second。每加完一次，都把first的值置成second，把second置成third。得到新的两个变量，然后求取新的third。
/*
时间复杂度：O(N)
空间复杂度：0(1)
*/
//省略了头文件，全局命名空间
long long Fib(long longn)
{
assert(n >= 0);
if(n==0||n==1)
{
return n;
}
long long first = 0;
long long second = 1;
long long third = 0;
for(int i = 2;i<=n;i++)
{
third = first+second;
first = second;//将second的值赋给first
second = third;//将third的值赋给second
}
return third;
}
（三）递归算法
这三个算法中，递归可谓是最简单的也是最难理解的。我们先看代码：
/*
时间复杂度：O(2^N)
空间复杂度：O(N)
*/
//省略了头文件，全局命名空间
long long Fib(long longn)
{
assert(n>=0);
if(n == 1||n == 0)
{
return n;
}
return Fib(n-1)+Fib(n-2);
}
这个递归的终止条件是 n==1 或 n == 2 。
当我们传进去的n大于这两个数的时候，这个程序对执行
[*]
return Fib(n-1)+Fib(n-2);
递归进入下一层，直到满足终止条件。再一层一层返回。最后返回我们想要的值。
挺复杂的东西呢 这个我上竞赛培优的时候算过，特征根方程就ok了 楼主学c++的？一起交流学习啊，感觉第二种方法最好，递归最差
页:
[1]