编程实现求第n项Fibonacci数。

来源：百度知道 编辑：UC知道 时间：2024/05/24 13:06:27
无穷数列1, 1, 2, 3, 5, 8,...称为Fibonacci数列，它可以递归地定义为：
F(n)=1（对于n=0,1），=F(n-1) + F(n-2)（对于n>1）

编程实现求第n项Fibonacci数。
Input
输入有多行，每行为一个测试数据n（n为整数）。
Output
对于每个测试数据，输出Fibonacci数列中的第n项（可以认为不会超过32位整数的表示范围）。每个输出1行。
Sample Input
2
4
1
Sample Output
2
5
1
用C++

#include<cstdio>
#define MAX_K 2
void mult(int a[][MAX_K], int b[][MAX_K], int n)
{
int s[MAX_K][MAX_K];
int i,j,k;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
{
s[i][j] = 0;
for(k = 0; k < n; k++)
{
s[i][j] += a[i][k]*b[k][j];
}
}
for(i = 0;i < n; i++)
for(j = 0; j < n; j++)
a[i][j] = s[i][j];
}
void lov(int import[][MAX_K],int time,int n)
{
int i,j;
int temp[MAX_K][MAX_K];
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
temp[i][j] = import[i][j];
for(i = 31; i >=0; i--)
{
if(time&(1<<i))
{
i--;
break;
}
}
while(i>=0)
{
mult(import,import,n);
if(time&(1<<i))
mult(import,temp,n);
i--;
}
}
int main()
{
int a[2][2],b[2][2];
a[0][0] = 1;
a[0][1] =