高质量题解|蜜蜂路线

题目大意

通过递推求出蜂房 $a$ 到蜂房 $b$ 有多少种方法

考纲知识点

基础数据类型、控制语句结构、递推的使用方法、变量的定义以及使用

数据范围

$N$$($$0$ $<$ $N$ $≤$ $100$$)$
$a$ 和 $b$$($$0$ $<$ $a$ $<$ $b$ $≤$ $50$$)$

解题思路

1. 举个例子:
   1.1 蜂房 $1$ 到蜂房 $2$ 只有 $1$ 种方法，直接到达
   1.2 蜂房 $1$ 到 $3$ 共有 $2$ 种方法，分别是直接到达和经过蜂房 $2$
   1.2 蜂房 $1$ 到 $4$ 共有 $3$ 种方法，分别是经过蜂房 $3$ 到达、经过蜂房 $2$ 到达、经过蜂房 $2$ 再到蜂房 $3$ ，最后到达蜂房 $4$
2. 根据 1 的推导和往后的计算，我们可以得出:
   2.1 蜂房编号相差为 $1$ 的永远只有 $1$ 个方法到达
   2.2 蜂房编号相差为 $2$ 的永远只有 $2$ 个方法到达
   2.3 从第 $3$ 个蜂房开始，行走路线方案为前两个蜂房行走路线方案相加

先定义一个数组 $a$ ，定义 $a$ 的前两项($a[1]$ $=$ $1$、$a[2]$ $=$ $2$)
从 $3$ 开始循环到 $50$ (因为$N$$($$0$ $<$ $N$ $≤$ $100$$)$)，后面再调用
第 $2$ 个循环，输出数组 $a$ 中 $x$ $-$ $y$ 的值

参考程序

#include <bits/stdc++.h>
using namespace std;
long long a[51];
int main(){
	int n;
	cin >> n;
	a[1] = 1;
	a[2] = 2;
	for(int i = 3;i <= 50;i++){
		a[i] = a[i - 2] + a[i - 1];
	}
	for(int i = 1;i <= n;i++){
		int x,y;
		cin >> x >> y;
		int sum = y - x;
		cout << a[sum] << endl;
	}
	return 0;
} 

时间复杂度

$O(50 + n)$