请用C语言编写以下问题Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。 当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。
时间: 2024-09-29 17:15:48 浏览: 40
Java实现Fibonacci取余
在C语言中,我们可以利用模运算(取余运算符%)来解决这个问题,因为我们需要找到Fibonacci数列的某一项对10007取余的结果。由于直接计算大的Fibonacci数会非常慢,所以我们通常采用“滚动数组”或“动态规划”的策略,避免重复计算。这里是一个简单的递归版本,但是为了效率考虑,我们会优化为循环版本:
```c
#include <stdio.h>
// 使用变量mod来存储10007,加快计算速度
#define MOD 10007
int fibonacci(int n) {
if (n <= 1) {
return n; // F1 和 F2 直接返回1
}
int prev = 1, curr = 1, next;
for (int i = 2; i <= n; ++i) {
next = (prev + curr) % MOD; // 用模运算更新下一个值
prev = curr; // 更新前两个值
curr = next; // 当前值成为下一次迭代的prev
}
return curr;
}
int main() {
int n = 10; // 示例,替换为你实际想要查询的项
printf("Fibonacci of %d divided by 10007 gives a remainder of %d\n", n, fibonacci(n));
return 0;
}
```
在这个程序里,`fibonacci` 函数计算 Fibonacci 数列的第 `n` 项对 10007 取余的结果。当你需要查询更大的数值时,只需更改 `main` 中的 `n` 的值即可。
阅读全文