Question

C语言编程输出斐波那契数列第n项的值。多组，第一行输入一个n(n大于等于0小于等于10的10次方)

C语言编程输出斐波那契数列第n项的值。多组，第一行输入一个n(n大于等于0小于等于10的10次方)，输出一对应项的值(是过输出的值太大则输出mod66666). 样例输入5 8 9
样例 C语言编程输出斐波那契数列第n项的值。多组，第一行输入一个n(n大于等于0小于等于10的10次方)，输出一对应项的值(是过输出的值太大则输出mod66666). 样例输入5 8 9
样例输出5 21 34 提示:这里是10的10次方
急急急，求代码

Answer 1

斐波那契数列中

F[x]=F[x-1]+F[x-2];

对于n不大，可以直接用递推来解决

#include<stdio.h>
int main(){
    int n,f1,f2,f3,i;
    while(~scanf("%d",&n)){
        f1=1,f2=1;
        if(n<2){
            printf("1\n");
            continue;
        }
        for(i=3;i<=n;i++){
            f3=(f1+f2)%66666;
            f1=f2;
            f2=f3;
        }
        printf("%d\n",f3);
    }
    return 0;
}

就可以了。

但是这道题目n比较大，是10^10

直接这么跑的话，时间有点接受不了

那么就要高一点手段了。。

可以写出一下两个等式：

F[n]   =1*F[n-1]+1*F[n-2]

F[n-1]=1*F[n-1]+0*F[n-2]

这样就乐意用F[n-1] F[n-2] 表示 F[n] F[n-1]了

这么表示的意义在于，可以写成一个转移矩阵：

那么就可以递推一下：

现在我们只需要能快速地处理中间那个矩阵的n-2次方

就可以快速求出数列的第n项了

假如要求a的b次方（这里写成a^b）：

比如a的11次方：

11表示成二进制为1011

容易知道：

所以，只需将a不断平方，在二进制那一位是1的乘到结果里就可以了

这段的C代码是这样的（为了不溢出，中间mod66666）

int quickpower(int a,int b){
    int ret=1;
    while(b){
        if(b&1)
            ret=ret*a%66666;
        a=a*a%66666;
        b>>=1;
    }
    return ret;
}//只需要把上面的a改成矩阵就可以了

追问

虽然考完了，但还是谢谢这么仔细解释