蓝桥杯——巧妙地递归

技术分享 2年前 (2023-01-05) 0 999+

一、切蛋糕思想

对于递归，我们可以采用思想之一，切蛋糕思想。
简而言之，就是将一个大问题，切成若干个小问题进行解决。
递归三要素：找重复、找变化、找边界
我们可以理解为，自己处理一小部分，剩下的部分交给别人处理（递归）
分解为：直接量 + 小规模子问题

1.1 经典求阶乘

求阶乘
- jc(n)：求n的阶乘 jc(n-1)：求n-1的阶乘
- 1.找重复： n*(n-1) ————子问题
- 2.找变化：变化的量应该作为参数
- 3.找边界：出口

public class 递归 {     public static int jc(int n) {         if(n == 1)             return 1;         return n * jc(n-1);     } }

1.2 打印i到j

1.找重复：理解为我处理当前参数问题，剩下的部分交给这个函数处理（规模更小的子问题）
2.找变化：变化的量应该作为参数
3.找边界：出口

public static void print(int i, int j) {         // 出口         if(i > j) return;         System.out.println(i);         // 重复与变化         print(i+1,j);     }

1.3 数组求和

当我们发现无法进行递归时，肯定是我们的参数不够

 public static int sum(int[] arr,int start) {         if(start == arr.length)             return 0;         return arr[start] + sum(arr,start+1);     }

1.4 翻转字符串

使用递归对一个字符串进行翻转

public static String reverse(String str, int end) {         if(end == 0)             return ""+str.charAt(0);         return str.charAt(end) + reverse(str,end-1);     }

二、递归公式与等价转换思想

和上面切蛋糕思想不同的是，这种问题我们无法进行切分，但是我们都可以转换成数学问题，当找到数学问题后进行等价转换即可。
分解为：多个子规模小问题

2.1 经典斐波那契数列

F(n) = F(n-1) + F(n-2)

// 求斐波那契数列第n项的值 public static int fib(int n) {         // 3. 找出口         if(n == 1 || n == 2) return 1;         // 1.找变化 | 2.找重复         return fib(n-1) + fib(n-2);     }

2.2 最大公约数

经典的欧几里得算法也称之为辗转相除法
通过最大公约数我们也可以判断两个数是否互质
F(m,n) = F(n,m%n)

public static int zzxc(int m, int n) {         if(n == 0) return m;         return zzxc(n,m%n);     }

2.3 递归形式的插入排序

同样是利用切分思想，我们对数组前k-1个元素进行排序
最后处理最后一个单独的元素
递归都是父问题转换成子问题

public static void insertArr(int[] arr, int k) {         // 1.对数组前k-1个元素进行排序         insertArr(arr, k - 1);          // 2.将最后一个元素插入到排好序的数组中         int temp = arr[k]; // 记录该数         while(temp < arr[k-1]) { // 后一个数比前一个数小的情况，将大的数后移             arr[k] = arr[k-1];  // 直到找到适合自己的位置为止             k--;         }         arr[k] = temp;     }

三、搞不清楚的汉诺塔

1~N从A移动到B，C作为辅助

等价于：

1~N-1从A移动到C，B为辅助
把N从A移动到B
1~N-1从C移动到B，A为辅助

	/**      * 八、汉诺塔问题      * 将N个盘子从source移动到target的路径打印      * @param N 初始的N个从小到大的盘子，N是最大编号      * @param from 原始柱子      * @param help 辅助的柱子      * @param to 目标柱子      */     public static void printHanoiTower(int N, String from, String to, String help) {          printHanoiTower(N-1, from, help, to);         System.out.println("move" + N + "from" + from + "to" + to);         printHanoiTower(N-1, help, to, from);     }