锐客网

  1. 首页 > it技术 > >

蓝桥杯算法特训 | 典型问题的递归框架 |未完待续

本节课主要的内容：
典型问题的递归框架
（1）排列问题

（2）组合计数问题
（3）组合枚举问题
（4）递归设计-条条大路通罗马


引入：
——————1————————1————————1————————————1————————————1
有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
* 木杆很细，不能同时通过一只蚂蚁。开始 时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，
* 但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。
* 编写程序，求所有蚂蚁都离开木杆 的最小时间和最大时间。
思路：

首先，讲一下思路：蚂蚁碰头后掉头，可以当作蚂蚁可以直接”穿过“对方，即蚂蚁碰头对蚂蚁运动没有影响。然后可以转换为每一只蚂蚁从初始位置直接到离开木杆的场景。求最短时间：以木杆中心为基准，左边的蚂蚁往左走，右边的蚂蚁往右走，这样子，左右两边的最短时间就是所求的最短时间。求最长时间：以木杆中心为基准，左边的蚂蚁往右走，右边的蚂蚁往左走，这样子，时间就会最长


题1：蚂蚁感冒
长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左，有的朝右。 每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。 当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。 这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。 请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。

输入
第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。
接着的一行是n个用空格分开的整数 Xi (-100 < Xi < 100), Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。其中，第一个数据代表的蚂蚁感冒了。
输出
要求输出1个整数，表示最后感冒蚂蚁的数目。
样例输入

3 5 -2 8 5 -10 8 -20 12 25
样例输出

1 3
蓝桥杯算法特训 | 典型问题的递归框架 |未完待续
文章图片

递归的真正难点在于：相似性的设计，在于如何设计参数才能相似


3.2排列问题 = 排列计数 + 排列枚举
关键点：不重复不遗漏
题2：已知不同字母构成的串，求它的全排列
第一种解法：直观递归
第二种：数组
#include using namespace std; void swap(char* a,char* b){ char temp; temp = *a; *a = *b; *b = temp; } void permute(char *a, int low, int high) { int j; if (low == high) //当low==high的时候，此时的a就是其中一个排列 printf("%s\n", a); else { for (j = low; j <= high; j++) //每个元素与第一个元素交换 { if (a[low] == a[j] && j != low) //为避免生成重复排列，当不同位置的字符相同时不再交换 continue; swap((a + low), (a + j)); permute(a, low + 1, high); //交换后得到子序列，再用函数得到子序列的全排列 swap((a + low), (a + j)); //backtrack回溯到原来的字符串状态，复原元素 } } }int main() { //method2 char a[] = "ABCD"; permute(a, 0, 3); return 0; }


视频中老师讲的我有点不理解所以就在网上找了全排列的一些解释
中心思想:
设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}.
Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列。
（1）当n=1时，Perm(R)=(r),其中r是集合R中唯一的元素；

（2）当n>1时，Perm(R)可由(r1)+Perm(R1),(r2)+Perm(R2),…,(rn)+Perm(Rn)构成。

我们来个实际的例子,假设有一数列1,2,3,4

那么1,2,3,4的全排列
perm({1,2,3,4})=1perm({2,3,4})+2perm({1,3,4})+3perm({1,2,4})+4perm(1,2,3)
也就是取出序列中的每一个元素作为序列的开头
注意：这里介绍一下C++ 标准库STL 中提供了计算下一个排列的函数next_permutation，利用该函数我们可以方便
地获得全排列。
#include #include #includeusing namespace std; int main() { string s = "ABCDEF"; sort(s.begin(),s.end()); do{ cout<


3.3 排列的应用
题3：搭积木
小明最近喜欢搭数字积木。一共有10块积木，每个积木上有一个数字，0~9。

搭积木规则：
每个积木放到其它两个积木的上面，并且一定比下面的两个积木数字小。
最后搭成4层的金字塔形，必须用完所有的积木。

下面是两种合格的搭法：

0
1 2
3 4 5
6 7 8 9

0
3 1
7 5 2

9 8 6 4
请你计算这样的搭法一共有多少种？
#include #include using namespace std; void show(int a[]) { cout<<""<



题4：组合（不计顺序）
引入：有m个不同的球取出n个有几种情况？
解1
#include using namespace std; //m个不同的球,取出n个 int f(int m,int n) { if(n==m) return 1; if(n==0) return 1; //假设有一个特殊的球，一定取出、不取出 return f(m-1,n) + f(m-1,n-1); }int main() { cout<

解2
#include using namespace std; //ABCDE中取出3个 int main() { for(char i= 'A'; i<='E'; i++) { for(char j = i+1; j<='E'; j++) { for(char k = j+1; k <='E'; k++) { cout<


题：有重复的字母中求取出m个所有组合
例如： "AAABBCCCCCCDD" 中取3个字母的所有组合
#include using namespace std; int main(){ char arr[10] = { 0 }; for (char i = 'A'; i <= 'E'; i++) { for (char j = (char)(i + 1); j <= 'E'; j++){ for (char k = (char)(j + 1); k <= 'E'; k++){arr[0] = i; arr[1] = j; arr[2] = k; printf("%s ", arr); } } } return 0; }


实际应用题5：
X星球要派出一个5人组成的观察团前往W星。
其中：
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
D国最多可以派出1人。
E国最多可以派出1人。
F国最多可以派出3人。

那么最终派往W星的观察团会有多少种国别的不同组合呢？
#include using namespace std; #define N 6 #define M 5 #define BUF 1024//a：可取最大个数的限定 //k: 当前考虑位置 //m: 目标名额 //b: 已经决定的代表团成员 void f(int a[],int k,int m,char b[]) { int i,j; if(k==N) { b[M] = 0; if(m==0) cout<




作业题6：扑克序列
A A 2 2 3 3 4 4， 一共4对扑克牌。请你把它们排成一行。
要求：两个A中间有1张牌，两个2之间有2张牌，两个3之间有3张牌，两个4之间有4张牌。

请填写出所有符合要求的排列中，字典序最小的那个。

例如：22AA3344 比 A2A23344 字典序小。当然，它们都不是满足要求的答案。
思路(全排列（含有重复）、结果放入集合可以去重复)
#include #include using namespace std; char para[8]; int findit(char a, int index) { for (int i = index; i < 8; i++) { if (para[i] == a)return i; } } int main() { char card[8] = { 'A', 'A', '2', '2', '3', '3', '4', '4' }; for (int i = 0; i < 8; i++) { para[0] = card[i]; for (int i2 = 0; i2 < 8; i2++) { if (i2 == i)continue; para[1] = card[i2]; for (int i3 = 0; i3 < 8; i3++) { if (i3 == i || i3 == i2)continue; para[2] = card[i3]; for (int i4 = 0; i4 < 8; i4++) { if (i4 == i || i4 == i2 || i4 == i3)continue; para[3] = card[i4]; for (int i5 = 0; i5 < 8; i5++) { if (i5 == i || i5 == i2 || i5 == i3 || i5 == i4)continue; para[4] = card[i5]; for (int i6 = 0; i6 < 8; i6++) { if (i6 == i || i6 == i2 || i6 == i3 || i6 == i4 || i6 == i5)continue; para[5] = card[i6]; for (int i7 = 0; i7 < 8; i7++) { if (i7 == i || i7 == i2 || i7 == i3 || i7 == i4 || i7 == i5 || i7 == i6)continue; para[6] = card[i7]; for (int i8 = 0; i8 < 8; i8++) { if (i8 == i || i8 == i2 || i8 == i3 || i8 == i4 || i8 == i5 || i8 == i6 || i8 == i7)continue; para[7] = card[i8]; int in1 = findit('A', 0); int in2 = findit('A', in1 + 1); int in3 = findit('2', 0); int in4 = findit('2', in3 + 1); int in5 = findit('3', 0); int in6 = findit('3', in5 + 1); int in7 = findit('4', 0); int in8 = findit('4', in7 + 1); //cout<


【蓝桥杯算法特训 | 典型问题的递归框架 |未完待续】

    推荐阅读


    上一篇：分布式|小试国产开源HTAP分布式NewSQL数据库TiDB-v5.3.0

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