蓝桥杯--典型问题的递归框架

2019-04-13 12:00发布

站内文章 / 模拟电子
10159 0 1688
典型问题的递归框架 （1）排列问题 （2）组合计数问题 （3）组合枚举问题 （4）递归设计--条条大路通罗马 例1【蚂蚁感冒】 长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左，有的朝右。 每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。 当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。 这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。 请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。 【数据格式】 第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。 接着的一行是n个用空格分开的整数 Xi (-100 < Xi < 100), Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。其中，第一个数据代表的蚂蚁感冒了。 要求输出1个整数，表示最后感冒蚂蚁的数目。 例如，输入： 3 5 -2 8 程序应输出： 1 再例如，输入： 5 -10 8 -20 12 25 程序应输出： 3 分析：两只蚂蚁掉头走=》两只蚂蚁交换身份，就像两只交叉走 例2【排列组合】：求字符串的全排列 排列问题=排列计数 + 排列枚举（不重复不遗漏） 方法一：直观递归 f("ABCD"){ 准备列表LX f("BCD") ===> 列表L1 "A" + L1中每个元素 加入LX f("ACD") ===> 列表L2 "B" + L2中每个元素 加入LX f("ABD") ===> 列表L3 "C" + L3中每个元素 加入LX f("ABC") ===> 列表L4 "D" + L4中每个元素 加入LX 最后返回LX } 方法二：用数组 f(数组="ABC", 位置=0){ if(位置==3){ 处理(数组) return; } f("ABC",位置=1) f("BAC",位置=1) f("CBA",位置=1) } //a:待排数组 //k:考虑的当前位置（数组下标） static void f(char[]a,int k) { if(k==a.length-1) System.out.println(String.valueOf(a)); for(int i=k;i 例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 请你计算这样的搭法一共有多少种？ 分析：变化的是数字可以用一维数组表示每个位置是什么；求出全排列，筛选条件类似：a[0] static int N=0; //a:待排数组 //k:考虑的当前位置（数组下标） static void f(int[]a,int k) { if(k==a.length-1) { if(a[0] 例4【组合问题】 组合计数问题：五个中取三个，有多少种取法？f(m,n) = f(m-1,n-1) + f(m-1,n) 组合枚举问题：“ABCDE”中取三个，所有取法【无重复】
  • 循环暴力解法：
                                  
  • 递归解法：
f(串="ABCDE", 取数=3){ 创建空列表 LL 'A' 拿出来 f("BCDE",2) ==> 列表L1 'A' 组合 L1 入 LL 'B' 拿出来 f("ACDE",2) ==> 列表L2 'B' 组合 L2 入 LL .... .... }
  • 使用于更一般的情况，比如：AAABBCCCCDD 中取3个，所有取法【有重复】
最多：3, 2, 4, 2 方案：0, 0, 1, 2 0, 0, 2, 1 0, 0, 3, 0 0, 1, 1, 1 0, 1, 2, 0 实际应用【代表团出访】 X星球要派出一个5人组成的观察团前往W星。 其中： A国最多可以派出4人。 B国最多可以派出2人。 C国最多可以派出2人。 D国最多可以派出1人。 E国最多可以派出1人。 F国最多可以派出3人。 那么最终派往W星的观察团会有多少种国别的不同组合呢？ public class Main { static int sum = 0; public static void main(String[] args) { int []a= {4,2,2,1,1,3}; int []x=new int[a.length]; f(a,x,0,5); System.out.println(sum);//101种 } //a:限制条件 //x:取法 //k:当前考虑的位置 //goal:剩余名额 private static void f(int[] a,int[] x, int k,int goal) { if(k==x.length) { if(goal==0) { sum++; for(int j=0;j 例5：A A 2 2 3 3 4 4， 一共4对扑克牌。请你把它们排成一行。 要求：两个A中间有1张牌，两个2之间有2张牌，两个3之间有3张牌，两个4之间有4张牌。 请填写出所有符合要求的排列中，字典序最小的那个。 例如：22AA3344 比 A2A23344 字典序小。当然，它们都不是满足要求的答案。      

热门文章