作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我有以下问题:我应该计算一个斐波那契数模另一个给定的数字。我知道皮萨诺时期,我正试图在这里实现它。这是代码:
#include <iostream>
#include <cstdlib>
long long get_fibonaccihuge(long long n, long long m) {
long long period = 0;
if (m % 2 == 0) {
if(m / 2 > 1)
period = 8 * (m / 2) + 4;
else
period = 3;
}
else{
if(((m + 1) / 2) > 1)
period = 4 * ((m + 1) / 2);
else
period = 1;
}
long long final_period = n % period;
long long array_fib[final_period];
array_fib[0] = 1;
array_fib[1] = 1;
for (long long i = 2; i < final_period; ++i) {
array_fib[i] = (array_fib[i-1] + array_fib[i-2]) % m;
}
return array_fib[final_period - 1];
}
int main() {
long long n, m;
std::cin >> n >> m;
std::cout << get_fibonaccihuge(n, m) << '\n';
}
它适用于小型测试,但问题是它无法通过以下测试:
281621358815590 30524
我不知道为什么。关于算法的任何建议,我引用了this页。当我构建它时。
我收到的错误是:错误的结果。
预期:11963 我的结果:28651
最佳答案
除非您的任务是使用皮萨诺周期,否则我建议您使用更常见的已知方法以 log2(n) 步计算第 n 个斐波那契数(通过计算 2*2 矩阵的幂:https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form) .
有两个原因:
关于c++ - 斐波那契模数 C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36675167/
我是一名优秀的程序员,十分优秀!