描述(C++) 菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。 给出一个正整数a,要求菲波那契数列中第a个数对1000取模的结果是多少。 输入描述 第1行是测试数据的组数n,后面跟着n (小于 10000000)行输入。每组测试数据占1行,包括一个正整数a(1 ≤ a ≤ 1000000)。 输出描述 n行,每行输出对应一个输入。输出应是一个正整数,为菲波那契数列中第a个数对1000取模得到的结果。 用例输入 1 4 5 2 19 1 用例输出 1 5 1 181 1
时间: 2024-04-15 17:29:46 浏览: 37
您可以使用以下C++代码来解决这个问题:
```cpp
#include <iostream>
#include <vector>
int fibonacciModulo(int n) {
std::vector<int> fib(n + 1);
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = (fib[i - 1] + fib[i - 2]) % 1000;
}
return fib[n];
}
int main() {
int n;
std::cin >> n;
for (int i = 0; i < n; i++) {
int a;
std::cin >> a;
std::cout << fibonacciModulo(a) << std::endl;
}
return 0;
}
```
在上面的代码中,我们首先定义了一个名为`fibonacciModulo`的函数,它接受一个整数参数`n`,并返回第`n`个斐波那契数对1000取模的结果。我们使用一个向量`fib`来存储前`n`个斐波那契数列的值,并通过迭代计算每个数的值(使用动态规划的思想)。最后,我们在`main`函数中读取输入的测试数据组数`n`,然后循环读取每组测试数据的值`a`并输出对应的结果。
对于您提供的示例输入,代码将输出:
```
5
1
181
1
```
这是菲波那契数列中第5、第2、第19和第1个数对1000取模的结果。
希望这可以帮助到您!