[18/12/3]蓝桥杯 练习系统 入门级别 Fibonacci数列求模问题 题解思路

 1 //Fibonacci数列递归一般问题常规方法(当目标序列号<32时适用 评判标准:运行时间<1.00s)
 2 #include <iostream>
 3 using namespace std;
 4 
 5 long Fib(int);
 6 
 7 int main()
 8 {
 9 
10     int n = 0; cin >> n;
11     cout << Fib(n) % 10007;
12     return 0;
13 }
14 
15 long Fib(int x)
16 {
17     if (x != 0)
18     {
19         if (x == 1 || x == 2)
20         {                         
21             return 1;
22         }
23         else return (Fib(x - 1) % 10007 + Fib(x - 2) % 10007) % 10007;
24     }
25 }

 1 //Fibonacci数列对数求模问题 题解 来源:蓝桥杯训练系统入门级 作者:Yuudachi晚风
 2 
 3 #include <iostream>
 4 using std::cin;
 5 using std::cout;
 6 
 7 int main()
 8 {
 9 
10     int n = 0; cin >> n;
11 
12     int Fibs[10] = {};        //10个一轮进行循环填充，可以自行调试更改
13     Fibs[0] = Fibs[1] = 1;
14     int seq = n % 10 - 1; //目标输出数组中目标数值序列号
15     if (seq == -1) seq = 9;   //重置10的倍数的序列值
16     long times = n / 10 + 1; //打到目标输出数组所需轮数
17     if (n % 10 == 0) times = n / 10;   //重置10的倍数的循环填充轮数值
18 
19     //cout << "seq=" << seq << "times=" << times << endl;
20 
21     for (int i = 0; i < times; i++)
22     {
23         for (long j = 2; j < 10; j++)
24         {
25             if (i != 0 && j == 2)
26             {
27                 Fibs[0] = Fibs[8] + Fibs[9];        //第一轮填充后每轮重置序列0的值
28                 Fibs[1] = Fibs[9] + Fibs[0];        //第一轮填充后每轮重置序列1的值
29             }
30             Fibs[j] = (Fibs[j - 1] + Fibs[j - 2]) % 10007;
31         }
32     }
33     cout << Fibs[seq] % 10007;
34 
35     return 0;
36 }