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次方
急急急，求代码
斐波那契数列中
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改成矩阵就可以了追问
虽然考完了，但还是谢谢这么仔细解释
...多组,第一行输入一个n(n大于等于0小于等于10的10次方)
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次方...
斐波那契数列c语言
} } int main { int n = 10; \/\/ 假设需要计算第10项的斐波那契数列值 printf); \/\/ 输出结果 return 0;} 解释如下：斐波那契数列定义：斐波那契数列是一个序列，其中每个数字是前两个数字的和。序列通常以这种方式开始：0、1，之后的每个数字都是前两个数字的和。例如，接下来的数字是0+1=1，...
用C语言求斐波那契数列第n项?
include<stdio.h>\/\/求斐波那契数列第n项int fib(int n){if(n == 0 || n == 1)return 1;elsereturn (fib(n-1)+fib(n-2));}int main(){int i,n;printf("---输入一个斐波那契数---\\n");scanf("%d",&n);for(i=0;i<n;i++)printf("%d\\t",fib(i));printf("\\n");re...
怎样用C语言求斐波那契数列第n项的值?
用C语言输出斐波那契数列的前n项步骤：1、首先，打开vc。2、点击文件、新建 3、选择win32 console application 并在右侧输入工程的名字和地址，确定 4、选择一个空的工程，完成。5、再次点击文件、新建，6、选择c++ source file 并输入文件名字，确定，7、输入如图所示的代码，这里以前十个斐波那契数列数...
求用C语言表达斐波那契数列
以下是用C语言实现斐波那契数列的代码片段：include int main(){ long f1 = 0, f2 = 1, f = 0; \/\/ 初始化前两项 int n, i;scanf("%d", &n);if (n <= 1) { \/\/ 特殊情况处理 f = n;} else if (n > 1) { \/\/ 一般情况，使用循环计算 for (i = 2; i <= n; i++)...
C语言,利用递归调用,编程输出斐波那契数列 ,这个怎么编啊,求指教啊
){int Fibonacci(int n);int n,i,c=0; printf("请输入n的值:");scanf("%d",&n);for(i=1; i<=n; i++){c = Fibonacci(i);printf("%12ld",c);if(i%4==0) \/\/用于换行 4个一行；printf("\\n");}} int Fibonacci(int n)\/\/函数部分；{long int f; if(n==1 || n=...
斐波那契数列c语言编程如何限定输入范围
double x1,x2,x; x1=1; x2=1;printf
C++编程:用递归法计算斐波那契数列第n项的值(同时输出前n项)-请修 ...
include<iostream>using namespace std;int fibonacci(int n){int fibo;static int temp;if (n == 1 || n == 2)fibo = 1;else{fibo = fibonacci(n-1) + fibonacci(n-2);if (temp < fibo){cout << " " << fibo;temp = fibo;}}return fibo;}int main(){int n, fibon;cout ...
编写一个C程序,用于打印斐波那契数列的前10个数
return n<3?1:(fib(n-1)+fib(n-2));} 【迭代版】\/\/打印斐波那契数列的前10项 include <stdio.h> define MAX 9 int main(){ int fib[MAX],i=2;fib[0]=fib[1]=1;printf("斐波那契数列的前10项是：\\n%d\\t%d\\t",fib[0],fib[1]);while(i<10){ fib[i]=fib[i-1]+fib[i...
用递归法计算斐波那契数列的第n项
用递归方法计算斐波那契数列的第n项的代码如下：include <stdio.h> int Fibonacci(int n){ if( n == 1 || n == 2) \/\/ 递归结束的条件，求前两项 return 1;else return Fibonacci(n-1)+Fibonacci(n-2); \/\/ 如果是求其它项，先要求出它前面两项，然后做和。} int main(){ int n;p...
