这样才能使对矩阵快速幂有深入的理解!!!
(其余基础的不懂就请看我另一篇简书!!!)
代码如下:
#include<cstdio>
#include<cstring>
#include<iostream>
#define CLR(x) memset(x,0,sizeof(x));
using namespace std;
struct point
{
int a[2][2]; //= {1,1,1,0};
void cclear()
{
CLR(a);
}
point operator * ( const point &b) const { //重载 * 号运算符.
point tmp;
tmp.cclear();
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
tmp.a[i][j] += (a[i][k] * b.a[k][j]);
}
}
}
return tmp;
}
};
point x,res; //res是单位矩阵,用来存结果,相当于数快速幂重中的 数字 1 .
void init()
{
x.cclear(); //清空
res.cclear();
x.a[0][0] = 1; //fibroacci数列矩阵形式,怎么推出来请在网上搜索.
x.a[0][1] = 1;
x.a[1][0] = 1;
x.a[1][1] = 0;
res.a[0][0] = 1; //初始化为单位矩阵.
res.a[0][1] = 0;
res.a[1][0] = 0;
res.a[1][1] = 1;
}
void qpow(int n)
{
while(n){
if(n&1) res = res * x; // 不能写成res *= x ; 因为我们只是重载了,* 号运算符, 而没有重载 *= 运算符!
x = x * x;
n >>= 1;
}
}
int main()
{
int n;
printf("你想知道fibonacci数列的第几项?\n");
while(scanf("%d",&n)!=EOF){
init();
if(n < 3){
printf("1\n");
continue;
}
qpow(n-2); //至于怎么推这个几次方,就是用等比数列来推!!! an = a(n-1) * q ;
printf("%d\n",res.a[0][0]*1+res.a[1][0]*1);
}
}
