官方题解
2024-03-21 16:36:26
发布于:浙江
67阅读
0回复
0点赞
【算法分析】
求蜜蜂从 到 所有可能的方案数。
表示跨越 格的方案数。
从 到 可能的路径为:1->2,a[1] = 1;
从 到 可能的路径为: 1->2->3,1->3,a[2] = 2;
从 到 可能的路径为: 1->2->3->4,1->3->4,1->2->4,a[3] = 3;
得出爬 个格子的方案数为: = + 。
【参考代码】
#include<iostream>
using namespace std;
const int N = 60;
long long a[N];
int main() {
int n;
cin >> n;
a[1] = 1; //初始条件:爬上1个格子的方案数
a[2] = 2; //爬上2个格子的方案数
for (int i = 3; i <= 50; i++) {
a[i] = a[i - 1] + a[i - 2]; //爬i个格子的方案数 = 爬i-1个格子的方案数 + 爬i-2个格子的方案数
}
while (n--) {
int x, y;
cin >> x >> y;
cout << a[y - x] << endl; //从x格到y格,爬上y-x个格子的方案数
}
return 0;
}
【时间复杂度】
【预计得分】
这里空空如也
有帮助,赞一个