锐客网

  1. 首页 > it技术 > >

蓝桥杯算法特训 | C++ |递归原理与构造技巧

课程主要内容：
递归的重要性
递归与循环的关系
递归的构造技巧
递归出口的考虑
参数设计

间接递归
关键字：找相似性、设置出口
引入1：切面条

一根高筋拉面，中间切一刀，可以得到2根面条。
如果先对折1次，中间切一刀，可以得到3根面条。
如果连续对折2次，中间切一刀，可以得到5根面条。
那么，连续对折10次，中间切一刀，会得到多少面条呢？
答案是个整数，请通过浏览器提交答案。不要填写任何多余的内容。
蓝桥杯算法特训 | C++ |递归原理与构造技巧
文章图片
思路：根据面条端头考虑切一刀之后的变化、或者一开始将面条作为环形然后进行折叠


#include using namespace std; int f(int n) { //基本递归 if(n == 0) { return 2; } else { return 2 * f(n - 1) - 1; } } int main(void) { cout << f(10) << endl; return 0; }

引入2：字符串的翻转
#include #include using namespace std; string f(string s) { if(s.length()<=1) return s; int a=s.length()-1; string b=s.substr(1,a); return f(b)+s[0]; } int main() { cout<


【蓝桥杯算法特训 | C++ |递归原理与构造技巧】递归有基本递归和尾递归两种形式，（函数式语言中有提供这种尾递归技术）尾递归在一定程度上可以提高程序效率，通常比基本递归多一个参数。
递归的本质就是栈，当然可以用栈实现，在数据规模特别大的时候要显式的使用栈，以防止栈溢出。
将规模较大的问题转化为与之结构相同的规模较小的问题


1.振兴中华
小明参加了学校的趣味运动会，其中的一个项目是：跳格子。
地上画着一些格子，每个格子里写一个字，如下所示：（也可参见下图）

蓝桥杯算法特训 | C++ |递归原理与构造技巧
文章图片


比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。

要求跳过的路线刚好构成“从我做起振兴中华”这句话。

请你帮助小明算一算他一共有多少种可能的跳跃路线呢？
这个路线 从-->华 可以将格子转化为坐标轴从终点向起点返回去计算
#include using namespace std; int f(int a,int b) { if(a==1||b==1) { return 1; } return f(a-1,b)+f(a,b-1); } int main() { cout<

2.出栈顺序
X星球特别讲究秩序，所有道路都是单行线。
一个甲壳虫车队，共16辆车，按照编号先后发车，夹在其它车流中，缓缓前行。


路边有个死胡同，只能容一辆车通过，是临时的检查站，如图所示。
蓝桥杯算法特训 | C++ |递归原理与构造技巧
文章图片

X星球太死板， 要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。
如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？

为了方便起见，假设检查站可容纳任意数量的汽车。
显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。
根据题意得到进栈次序是：1 2 3 4 5……
#include using namespace std; //a为等待进栈的车辆数目 //b为栈中的个数 int f1(int a,int b) { if(a==0) return 1; if(b==0) return f1(a-1,1); return f1(a-1,b+1) + f1(a,b-1); //有一辆车进栈、或者有一辆车出栈 }int f2(int n) { return f1(n,0); } int main() { int n; cin>>n; cout<

3.算式填符号
匪警请拨110,即使手机欠费也可拨通！
为了保障社会秩序，保护人民群众生命财产安全，警察叔叔需要与罪犯斗智斗勇，因而需要经常性地进行体力训练和智力训练！
某批警察叔叔正在进行智力训练：
1 2 3 4 5 6 7 8 9 = 110
请看上边的算式，为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法；123+4+5+67-89 是另一个可能的答案。

请你利用计算机的优势，帮助警察叔叔快速找到所有答案。
每个答案占一行。形如：
12+34+56+7-8+9
123+4+5+67-89

......


4.第39级台阶
小明刚刚看完电影《第39级台阶》。离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？

请你利用计算机的优势，帮助小明寻找答案。
#include using namespace std; long ff(int n); // 奇数步 long gg(int n) { if (n == 0) return 0; if (n == 1) return 1; /*if(n==2) return 1; */ return ff(n - 1) + ff(n - 2); } // 偶数步 long ff(int n) { if (n == 0) return 1; if (n == 1) return 0; /*if(n==2) return 1; */ return gg(n - 1) + gg(n - 2); }int main() { cout<




    推荐阅读


    上一篇：蓝桥杯|蓝桥杯单片机省赛国赛资料（2020年前的检索）

    下一篇：蓝桥杯|01蓝桥杯特训课程第一次总结