扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
C++课程设计-- Fibonacci 数列输出系统
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口斐波那契数列算法分析
假定你有一雄一雌一对刚出生的兔子，它们在长到一个月大小时开始交配，在第二月结束时，雌兔子产下另一对兔子，过了一个月后它们也开始繁殖，如此这般持续下去。每只雌兔在开始繁殖时每月都产下一对兔子，假定没有兔子死亡，在一年后总共会有多少对兔子？
在一月底，最初的一对兔子交配，但是还只有1对兔子；在二月底，雌兔产下一对兔子，共有2对兔子；在三月底，最老的雌兔产下第二对兔子，共有3对兔子；在四月底，最老的雌兔产下第三对兔子，两个月前生的雌兔产下一对兔子，共有5对兔子；……如此这般计算下去，兔子对数分别是：1, 1, 2, 3, 5, 8, 13, 21, 34, 55,89, 144, ...看出规律了吗？从第3个数目开始，每个数目都是前面两个数目之和。这就是著名的斐波那契（Fibonacci）数列。
有趣问题：
1，有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?
答：这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种方法……所以，1，2，3，5，8，13……登上十级，有89种。
2，数列中相邻两项的前项比后项的极限是多少，就是问，当n趋于无穷大时，F(n)/F(n+1)的极限是多少？
答：这个可由它的通项公式直接得到，极限是(-1+√5)/2，这个就是所谓的黄金分割点，也是代表大自然的和谐的一个数字。
数学表示：
Fibonacci数列的数学表达式就是：
F(n) = F(n-1) + F(n-2)
递归程序1：
Fibonacci数列可以用很直观的二叉递归程序来写，用C++语言的描述如下：
long fib1(int n)
&&&& &&&& if (n &= 2)
&&&& &&&& return 1;
&&&& &&&& return fib1(n-1) + fib1(n-2);
看上去程序的递归使用很恰当，可是在用VC2005的环境下测试n=37的时候用了大约3s，而n=45的时候基本下楼打完饭也看不到结果……显然这种递归的效率太低了！！
递归效率分析：
例如，用下面一个测试函数：
long fib1(int n, int* arr)
&&&&&&&& arr[n]++;
&&&&&&&& if (n &= 2)
&&&&&&&& {
&&&&&&&&&&&&& return 1;
&&&&&&&& }
&&&&&&&& else
&&&&&&&& {
&&&&&&&&&&&&& return fib1(n-1, arr) + fib1(n-2, arr);
&&&&&&&& }
这时，可以得到每个fib(i)被计算的次数：
fib(10) = 1&&&& fib(9) = 1&&&&& fib(8) = 2&&&&& fib(7) = 3
fib(6) = 5&&&&& fib(5) = 8&&&&& fib(4) = 13&&& fib(3) = 21
fib(2) = 34&& fib(1) = 55&&& fib(0) = 34
可见，计算次数呈反向的Fibonacci数列，这显然造成了大量重复计算。
我们令T(N)为函数fib(n)的运行时间，当N&=2的时候我们分析可知：
T(N) = T(N-1) + T(N-2) + 2
而fib(n) = fib(n-1) + fib(n-2)，所以有T(N) &= fib(n)，归纳法证明可得：
fib(N) & (5/3)^N
当N&4时，fib（N）&= (3/2)^N
标准写法：
显然这个O（(3/2)^N） 是以指数增长的算法，基本上是最坏的情况。
其实，这违反了递归的一个规则：合成效益法则。
合成效益法则（Compound interest rule）：在求解一个问题的同一实例的时候，切勿在不同的递归调用中做重复性的工作。
所以在上面的代码中调用fib(N-1)的时候实际上同时计算了fib(N-2)。这种小的重复计算在递归过程中就会产生巨大的运行时间。
递归程序2：
用一叉递归程序就可以得到近似线性的效率，用C++语言的描述如下：
long fib(int n, long a, long b, int count)
&&&& if (count == n)
&&&& return fib(n, b, a+b, ++count);
long fib2(int n)
&&&& return fib(n, 0, 1, 1);
这种方法虽然是递归了，但是并不直观，而且效率上相比下面的迭代循环并没有优势。
迭代解法：
Fibonacci数列用迭代程序来写也很容易，用C++语言的描述如下：
//也可以用数组将每次计算的f(n)存储下来，用来下次计算用（空间换时间）
long fib3 (int n)
&&&& long x = 0, y = 1;
&&&& for (int j = 1; j & j++)
&&&&&&&& y = x +
&&&&&&&& x = y -
这时程序的效率显然为O（N），N = 45的时候&1s就能得到结果。
矩阵乘法：
我们将数列写成：
Fibonacci[0] = 0，Fibonacci[1] = 1
Fibonacci[n] = Fibonacci[n-1] + Fibonacci[n-2] (n &= 2)
可以将它写成矩阵乘法形式：
将右边连续的展开就得到：
下面就是要用O(log(n))的算法计算：
显然用二分法来求，结合一些面向对象的概念，C++代码如下：
class Matrix
&&&&&& long matr[2][2];
&&&&&& Matrix(const Matrix&rhs);
&&&&&& Matrix(long a, long b, long c, long d);
&&&&&& Matrix& operator=(const Matrix&);
&&&&&& friend Matrix operator*(const Matrix& lhs, const Matrix& rhs)
&&&&&&&&&&&&& Matrix ret(0,0,0,0);
&&&&&&&&&&&&& ret.matr[0][0] = lhs.matr[0][0]*rhs.matr[0][0] + lhs.matr[0][1]*rhs.matr[1][0];
&&&&&&&&&&&&& ret.matr[0][1] = lhs.matr[0][0]*rhs.matr[0][1] + lhs.matr[0][1]*rhs.matr[1][1];
&&&&&&&&&&&&& ret.matr[1][0] = lhs.matr[1][0]*rhs.matr[0][0] + lhs.matr[1][1]*rhs.matr[1][0];
&&&&&&&&&&&&& ret.matr[1][1] = lhs.matr[1][0]*rhs.matr[0][1] + lhs.matr[1][1]*rhs.matr[1][1];
&&&&&&&&&&&&& return
Matrix::Matrix(long a, long b, long c, long d)
&&&&&& this-&matr[0][0] =
&&&&&& this-&matr[0][1] =
&&&&&& this-&matr[1][0] =
&&&&&& this-&matr[1][1] =
Matrix::Matrix(const Matrix &rhs)
&&&&&& this-&matr[0][0] = rhs.matr[0][0];
&&&&&& this-&matr[0][1] = rhs.matr[0][1];
&&&&&& this-&matr[1][0] = rhs.matr[1][0];
&&&&&& this-&matr[1][1] = rhs.matr[1][1];
Matrix& Matrix::operator =(const Matrix &rhs)
&&&&&& this-&matr[0][0] = rhs.matr[0][0];
&&&&&& this-&matr[0][1] = rhs.matr[0][1];
&&&&&& this-&matr[1][0] = rhs.matr[1][0];
&&&&&& this-&matr[1][1] = rhs.matr[1][1];
&&&&&& return *this;
Matrix power(const Matrix& m, int n)
&&&&&& if (n == 1)
&&&&&&&&&&&&& return
&&&&&& if (n%2 == 0)
&&&&&&&&&&&&& return power(m*m, n/2);
&&&&&& else
&&&&&&&&&&&&& return power(m*m, n/2) *
long fib4 (int n)
&&&&&& Matrix matrix0(1, 1, 1, 0);
&&&&&& matrix0 = power(matrix0, n-1);
&&&&&& return matrix0.matr[0][0];
这时程序的效率为O（log(N)） 。
公式解法：
在O（1）的时间就能求得到F(n)了：
注意：其中[x]表示取距离x最近的整数。
用C++写的代码如下：
long fib5(int n)
&&&& double z = sqrt(5.0);
&&&& double x = (1 + z)/2;
&&&& double y = (1 - z)/2;
&&&& return (pow(x, n) - pow(y, n))/z + 0.5;
这个与数学库实现开方和乘方本身效率有关的，我想应该还是在O(log(n))的效率。
上面给出了5中求解斐波那契数列的方法，用测试程序主函数如下：
int main()
&&&& cout && fib1(45) &&
&&&& cout && fib2(45) &&
&&&& cout && fib3(45) &&
&&&& cout && fib4(45) &&
cout && fib5(45) &&
&&&& return 0;
函数fib1会等待好久，其它的都能很快得出结果，并且相同为：。
而后面两种只有在n = 的时候会显示出优势。由于我的程序都没有涉及到高精度，所以要是求大数据的话，可以通过取模来获得结果的后4位来测试效率与正确性。
另外斐波那契数列在实际工作中应该用的很少，尤其是当数据n很大的时候（例如：），所以综合考虑基本普通的非递归O(n)方法就很好了，没有必要用矩阵乘法。
程序全部源码：
#include &iostream&
#include &vector&
#include &string&
#include &cmath&
#include &fstream&
using namespace
class Matrix
&&&&&& long matr[2][2];
&&&&&& Matrix(const Matrix&rhs);
&&&&&& Matrix(long a, long b, long c, long d);
&&&&&& Matrix& operator=(const Matrix&);
&&&&&& friend Matrix operator*(const Matrix& lhs, const Matrix& rhs)
&&&&&&&&&&&&& Matrix ret(0,0,0,0);
&&&&&&&&&&&&& ret.matr[0][0] = lhs.matr[0][0]*rhs.matr[0][0] + lhs.matr[0][1]*rhs.matr[1][0];
&&&&&&&&&&&&& ret.matr[0][1] = lhs.matr[0][0]*rhs.matr[0][1] + lhs.matr[0][1]*rhs.matr[1][1];
&&&&&&&&&&&&& ret.matr[1][0] = lhs.matr[1][0]*rhs.matr[0][0] + lhs.matr[1][1]*rhs.matr[1][0];
&&&&&&&&&&&&& ret.matr[1][1] = lhs.matr[1][0]*rhs.matr[0][1] + lhs.matr[1][1]*rhs.matr[1][1];
&&&&&&&&&&&&& return
Matrix::Matrix(long a, long b, long c, long d)
&&&&&& this-&matr[0][0] =
&&&&&& this-&matr[0][1] =
&&&&&& this-&matr[1][0] =
&&&&&& this-&matr[1][1] =
Matrix::Matrix(const Matrix &rhs)
&&&&&& this-&matr[0][0] = rhs.matr[0][0];
&&&&&& this-&matr[0][1] = rhs.matr[0][1];
&&&&&& this-&matr[1][0] = rhs.matr[1][0];
&&&&&& this-&matr[1][1] = rhs.matr[1][1];
Matrix& Matrix::operator =(const Matrix &rhs)
&&&&&& this-&matr[0][0] = rhs.matr[0][0];
&&&&&& this-&matr[0][1] = rhs.matr[0][1];
&&&&&& this-&matr[1][0] = rhs.matr[1][0];
&&&&&& this-&matr[1][1] = rhs.matr[1][1];
&&&&&& return *this;
Matrix power(const Matrix& m, int n)
&&&&&& if (n == 1)
&&&&&&&&&&&&& return
&&&&&& if (n%2 == 0)
&&&&&&&&&&&&& return power(m*m, n/2);
&&&&&& else
&&&&&&&&&&&&& return power(m*m, n/2) *
//普通递归
long fib1(int n)
&&&&&&&&&&&&& if (n &= 2)
&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&& return 1;
&&&&&&&&&&&&& }
&&&&&&&&&&&&& else
&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&& return fib1(n-1) + fib1(n-2);
&&&&&&&&&&&&& }
/*上面的效率分析代码
long fib1(int n, int* arr)
&&&&&&&&&&&&& arr[n]++;
&&&&&&&&&&&&& if (n &= 1)
&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&& return 1;
&&&&&&&&&&&&& }
&&&&&&&&&&&&& else
&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&& return fib1(n-1, arr) + fib1(n-2, arr);
&&&&&&&&&&&&& }
long fib(int n, long a, long b, int count)
&&&&&& if (count == n)
&&&&&&&&&&&&& return
&&&&&& return fib(n, b, a+b, ++count);
//一叉递归
long fib2(int n)
&&&&&& return fib(n, 0, 1, 1);
//非递归方法O(n)
long fib3 (int n)
&&&&&& long x = 0, y = 1;
&&&&&& for (int j = 1; j & j++)
&&&&&&&&&&&&& y = x +
&&&&&&&&&&&&& x = y -
&&&&&& return
//矩阵乘法O(log(n))
long fib4 (int n)
&&&&&& Matrix matrix0(1, 1, 1, 0);
&&&&&& matrix0 = power(matrix0, n-1);
&&&&&& return matrix0.matr[0][0];
//公式法O(1)
long fib5(int n)
&&&&&& double z = sqrt(5.0);
&&&&&& double x = (1 + z)/2;
&&&&&& double y = (1 - z)/2;
&&&&&& return (pow(x, n) - pow(y, n))/z + 0.5;
int main()
&&&&&& //n = 45时候fib1()很慢
&&&&&& int n = 10;
&&&&&& cout && fib1(n) &&
&&&&&& cout && fib2(n) &&
&&&&&& cout && fib3(n) &&
&&&&&& cout && fib4(n) &&
&&&&&& cout && fib5(n) &&
&&&&&& return 0;
阅读(...) 评论()九度oj1387求Fibonacci数列第n项 - CSDN博客
题目1387：斐波那契数列
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：1656
题目描述：
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。斐波那契数列的定义如下：
输入可能包含多个测试样例，对于每个测试案例，
输入包括一个整数n(1&=n&=70)。
对应每个测试案例，
输出第n项斐波那契数列的值。
样例输入：
样例输出：
//用矩阵乘法解决Fibonacci,这个题直接将Fibonacci数列存在数组里，用for循环赋值也可以解决，要注意的是数据类型也要是long long#include&iostream&
using std::
using std::
using std::
int main()
long long t1,t2,t3,t4;
long long M00,M01,M10,M11;
long long temprow1,row1,row2;
while(cin&&k)
cout && 1 &&
M00=1,M01=1,M10=1,M11=0;
row1=1,row2=0;
while(kk&=1)
if(kk%2==0)
//临时矩阵存当前分割时的矩阵,分割矩阵次数递增
t1=M00*M00+M01*M10;
t2=M00*M01+M01*M11;
t3=M10*M00+M11*M10;
t4=M10*M01+M11*M11;
temprow1=row1;//没有temprow1就eggs broken吧
row1=M00*row1+M01*row2;
row2=M10*temprow1+M11*row2;
cout && row1 &&
/**************************************************************
Problem: 1387
User: true14fans
Language: C++
Result: Accepted
Time:10 ms
Memory:1520 kb
****************************************************************/C++用数组来解决求Fabonacci数列问题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
C++用数组来解决求Fabonacci数列问题
C​+​+​用​数​组​来​解​决​求​F​a​b​o​n​a​c​c​i​数​列​问​题
阅读已结束，如果下载本文需要使用
想免费下载本文？
你可能喜欢斐波那契数列c++编程_百度知道
斐波那契数列c++编程
编写c++程序求斐波那契数列的第n项和前n项和斐波那契数列也没给出最后不用递归 效率太低 高手帮忙！！
提问者采纳
} fib(N); } for(j=i;2); cin&gt,c[10001], 21，F[0]=0;&lt，F[1]=1，就直接取的是斐波那契数列的后四位;
a[1][1]=b[1][1];&j--) {
if(c[j]==1)
b[0][1]=a[0][0]%10000,j;
} }}int main(){ int N; return 0,0}};0&quot，F[n]=F[n-1]+F[n-2](n&i++。你看看。#include&i&trial(n-1).。我以前写了一个程序.|1 1|;N, 34.;#include&lt, 2，因为为了避免高精度的麻烦;
a[1][1]=b[1][1]：在Fibonacci数列中;
} }}void fib(int n){ int i，把它改成高精度就可以了,{1;j&gt, 1:|F[n+1] F[n]
= |1 1|;a[0][1]。举例来说,0;memory& cout&&int a[2][2]={{1;
b[0][0]=(a[0][0]+a[0][1])%10000;cmath&& memset(c;
b[0][1]=(a[0][0]*a[0][1]+a[0][1]*a[1][1])%10000, 13;return 0;
b[1][1]=(a[1][1]*a[1][1]+a[0][1]*a[0][1])%10000，Fibonacci数列的前十个数是 0; for(i=10000, 1;trial(n/
a[0][1]=b[0][1];void trial(int n){ if(n==1)
return.共n个|F[n]
|1 0| |1 0| |1 0|用这个方法就可以避免递归了,sizeof(c)), 3;
if(c[j]==2)
b[0][0]=(a[0][0]*a[0][0]+a[0][1]*a[0][1])%1|;, 5; if(N==0){cout&lt!=0)=0, 8;=0;&#47, … 我们可以用利用矩阵乘法来计算Fibonacci的第n项 ;
a[0][1]=b[0][1];iostream& trial(n);
a[0][0]=b[0][0];
a[0][0]=b[0][0],1};i++; else{
if(n%2==1)
b[1][1]=a[0][1]%10000;/i--) {
if(c[i];#include&
if(n%2==0)
c[i]=2;int b[2][2];=2)我给你讲一下思路
提问者评价
其他类似问题
为您推荐：
其他4条回答
波那契数列就是 0 1 1 2 3 5 8 13 21 . 除了最开始的0和1，后面每一个数都是前面两个数相加之和..。不用递归就用循环啊
#include&cmath&#include&cstdio&double f,n;int main(){ scanf(&%lf&,&n); printf(&%.0lf\n&,1/sqrt(5)*(pow(((sqrt(5)+1)/2),n)+pow(((sqrt(5)-1)/2),n))); printf(&%.0lf\n&,1/sqrt(5)*(pow(((sqrt(5)+1)/2),n+2)+pow(((sqrt(5)-1)/2),n+2))-1); return 0;}
真服了你，递归也做得到n的时间复杂度的啊很多东西用递归解决容易，用其他方法麻烦
去百度一下啊！
斐波那契数列的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁}