【算法分析】 求蜜蜂从 xxx 到 yyy 所有可能的方案数。 aia_iai 表示跨越 iii 格的方案数。 从 111 到 222 可能的路径为：1->2，a[1] = 1; 从 111 到 333 可能的路径为: 1->2->3，1->3，a[2] = 2; 从 111 到 444 可能的路径为: 1->2->3->4，1->3->4，1->2->4，a[3] = 3; 得出爬 nnn 个格子的方案数为：aia_iai = ai−1a_{i-1}ai−1 + ai−2a_{i - 2}ai−2 。 【参考代码】 【时间复杂度】 O(n)O(n)O(n) 【预计得分】 100pts100pts100pts

#include<iostream> using namespace std; int main(){ int n; cin>>n; long long a[60]; a[1]=1; a[2]=2; for(int i=3;i<=50;i++){ a[i]=a[i-2]+a[i-1]; } while(n--){ int x,y; cin>>x>>y; cout<<a[y-x]<<endl; } return 0; }

翻版兔子数列（一定要开long long）

#include <iostream> #include <algorithm> using namespace std; long long d[51]={1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074}; short n,a,b; int main() { cin>>n; for(int i=1;i<=n;++i){ cin>>a>>b; cout<<d[b-a]<<endl; } return 0; }

#include<iostream> using namespace std; int main(){ int n; long long a[55]; cin>>n; a[1]=1; a[2]=2; for(int i=3;i<=50;i++){ a[i]=a[i-1]+a[i-2]; } while(n--){ int x,y; cin>>x>>y; cout<<a[y-x]<<endl; } return 0; }