目录
C++找路线
第十四届蓝桥杯青少年创意编程大赛C++选拔赛真题
一、题目要
1、编程实现
现有 22 名小朋友，依次编号1到 22，22 名小朋友分别按照下图的位置站好。
每名小朋友只能按照图中箭头指向的方向移动。给出两名小朋友的编号 N和 M(1≤N<M≤22)，
请你找出从编号 N 到编号 M 共有多少条不同的路线。
例如:N=3,M=7，从编号3的位置到编号7的位置共有5条路线，分别为:(3->5->7)，(3->5->6->7)，(3->4->5->7)，(3->4->5->6>7)，(3->4>6->7)
2、输入输出
输入描述：只有一行，输入两个正整数 N 和 M(1≤N<M≤22)，分别表示两名小朋友的编号，之间以一个空格隔开。
输出描述：输出一个整数，表示从编号 N 到编号 M 共有多少条不同的路线。
输入样例：
3 7
输出样例：
5
二、算法分析
- 从给定题目的初步分析可以看出，题目看着很多，但其实认真分析难度不是很大
- 根据给定的图片可以看到，从第一名同学到每一名同学的路线总数符合斐波那契数列的
- 那从N到编号M，其实可以先转换为相对从1到对应的同学编号即可，如何转换，直接将M-N再加1就转换好了，然后就是求第几项斐波那契数列值就是我们对用的路线总数
三、程序编写
#include <iostream>
using namespace std;
int fn(int k)
{
if (k == 1 || k == 2)
return 1;
else
return fn(k-1) + fn(k-2);
}
int main(void)
{
int n,m,res;
cin >> n >> m;
res = fn(abs(m-n)+1);
cout << res << endl;
}四、程序说明
- 首先需要导入输入输出流头文件
- 接着再次导入输入输出流格式控制头文件
- 然后是引入std命名空间中的所有成员到当前的程序中，这样在当前的程序中就可以直接使用 std 命名空间中的所有成员，而不需要使用的时候在成员前面加上（std::）前缀
- 定义一个递归函数fn求斐波那契数列，当数字为1或者2的时候返回1
- 否则返回n-1个人的数量加上n-2个人的数量
- 接着声明程序的入口，也就是主函数（主函数在一个程序中只允许出现一次）
- 根据题目要求声明3个整型变量n,m和res，n和m表示输入的人数，res就是路线总数
- 然后利用输入流对象cin，从键盘读取变量n和m的值
- 调用递归函数fn，将m-n的绝对值加1作为参数传递，最后结果保存再res中
- 最后利用输出流对象cout，输出res的值
- 最后返回0，程序结束
本文作者：小兔子编程 作者首页：https://blog.csdn.net/frank2102
五、运行结果
3 7
5六、考点分析
难度级别：中等，这题相对而言还是有点难度，在于如何分析出斐波那契数列规律，具体主要考查如下：
- 充分掌握变量的定义和使用
- 学会斐波那契数列的原理和实现
- 学会输入流对象cin的使用，从键盘读入相应的数据
- 学会for循环的使用，在确定循环次数的时候推荐使用学会
- 学会while循环的使用，在不确定循环次数的时候推荐使用
- 学会if条件判断语句的使用，满足一定条件才能执行后面的语句
- 学会if...else...双分支语句的使用，条件满足执行一种处理，不满足执行另一种处理
- 学会abs函数的使用，返回当前对象的绝对值
- 掌握输出流对象cout的使用，与流插入运算符 << 结合使用将对象输出到终端显示
- 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
- 充分掌握变量定义和使用、分支语句、循环语句和简单算法知识的使用及输入输出的用法
PS：方式方法有多种，小朋友们只要能够达到题目要求即可！
