前言略.
看到这个题目本来应该很高兴的，因为什么，因为太TM的基础了啊!
可是当你用常规方法尝试提交OJ时你会发现..hhh...运行超时..(开心地摇起了呆毛
//Fibonacci数列递归一般问题常规方法(当目标序列号<32时适用 评判标准:运行时间<1.00s)
#include <iostream>
using namespace std; long Fib(int); int main()
{ int n = ; cin >> n;
cout << Fib(n) % ;
return ;
} long Fib(int x)
{
if (x != )
{
if (x == || x == )
{
return ;
}
else return (Fib(x - ) % + Fib(x - ) % ) % ;
}
}
这里顺带提一下，大数求模的一个运算律(只列了一个):
(a+b)%N == a%N+b%N == (a%N+b%N)%N，常用哦~
于是我想，这样用原来的常规方法内存又要占爆，CPU又要发烧(毕竟n值一上去那个递归次数你懂得.)
于是转变思路用循环多次填充的方法尝试再(wan)次(quan)实(chong)现(xie)了一遍代码，以10位Fibonacci数的顺序生成为一轮填充
剩下的只需要找到目标n值对应的10位中的序列号以及循环填充轮数就行了，省省宝贵的内存(虽然限制是256M但是总觉得是虚报的...)
下面是具体实现方案，记得打注释部分要写，不然就会在循环填充的时候卡死。
//Fibonacci数列对数求模问题 题解 来源:蓝桥杯训练系统入门级 作者:Yuudachi晚风 #include <iostream>
using std::cin;
using std::cout; int main()
{ int n = ; cin >> n; int Fibs[] = {}; //10个一轮进行循环填充，可以自行调试更改
Fibs[] = Fibs[] = ;
int seq = n % - ; //目标输出数组中目标数值序列号
if (seq == -) seq = ; //重置10的倍数的序列值
long times = n / + ; //打到目标输出数组所需轮数
if (n % == ) times = n / ; //重置10的倍数的循环填充轮数值 //cout << "seq=" << seq << "times=" << times << endl; for (int i = ; i < times; i++)
{
for (long j = ; j < ; j++)
{
if (i != && j == )
{
Fibs[] = Fibs[] + Fibs[]; //第一轮填充后每轮重置序列0的值
Fibs[] = Fibs[] + Fibs[]; //第一轮填充后每轮重置序列1的值
}
Fibs[j] = (Fibs[j - ] + Fibs[j - ]) % ;
}
}
cout << Fibs[seq] % ; return ;
}
大概就是这样了，欢迎批评指正，以及比我更高效的算法方案在评论区讨论！感谢观看。