C++实现斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）

[cpp] view plain copy
#include <iostream>
using namespace std;

int main()
{
int a[4] = {1,1,1,0};//前面讨论过
int b[4] = {1,0,0,1};//单位阵
int n,a1,a2,a3,a0;

cin >> n;

if (n == 0)
{
cout << "0";
return 0;
}
if (n == 1)
{
cout << "1";
return 1;
}
n = n-1;
while ( n > 0 )
{
if ( n%2 == 1 )
{
n = n - 1;
a0 = b[0]*a[0] + b[1]*a[2];
a1 = b[0]*a[1] + b[1]*a[3];
a2 = b[2]*a[0] + b[3]*a[2];//此处实际上不用更新b[2],b[3]
a3 = b[2]*a[1] + b[3]*a[3];
b[0] = a0;b[1] = a1;b[2] = a2;b[3] = a3;
}
n = n/2;
a0 = a[0]*a[0] + a[1]*a[2];
a1 = a[0]*a[1] + a[1]*a[3];
a2 = a[2]*a[0] + a[3]*a[2];
a3 = a[2]*a[1] + a[3]*a[3];
a[0] = a0;a[1] = a1;a[2] = a2;a[3] = a3;
}

cout << b[0];
return 0;
}

版权声明：本文为博主-姜兴琪原创文章，未经博主允许不得转载。 http://www.ylsjwang.com/mingxing/40.html