一、介紹
1、介紹
遞歸:遞歸就是方法自己調用自己,每次調用時傳入不同的變量。遞歸有助于程式設計者解決複雜的問題,同時可以讓代碼變得簡潔。
疊代和遞歸差別:疊代使用的是循環結構,遞歸使用的選擇結構。使用遞歸能使程式的結構更清晰、更簡潔、更容易讓人了解,進而減少讀懂代碼的時間。其時間複雜度就是遞歸的次數。
但大量的遞歸調用會建立函數的副本,會消耗大量的時間和記憶體,而疊代則不需要此種付出。
遞歸函數分為調用和回退階段,遞歸的回退順序是它調用順序的逆序。
分治:當一個問題規模較大且不易求解的時候,就可以考慮将問題分成幾個小的子產品,逐一解決。
2、案例
- 兔子繁殖的問題。(斐波那契數列)。
- 計算 n! 。
- 任意長度的字元串反向輸出。
- 折半查找算法的遞歸實作。
- 漢諾塔問題
- 八皇後問題
二、迷宮問題
問題:尋找一條從起始點到達終點的有效路徑。
代碼示例:迷宮
1 public class MiGong {
2
3 /**
4 * 0:該點沒有走過, 1:表示牆, 2:可以走, 3:該點已經走過,但是走不通\
5 * 政策: 下->右->上->左, 如果該點走不通,再回溯
6 */
7 private int[][] map;
8 private int desX;
9 private int desY;
10
11 /**
12 * 建構 row*col的迷宮
13 *
14 * @param row 行
15 * @param col 列
16 */
17 public MiGong(int row, int col) {
18 if (row <= 0 || col <= 0) {
19 return;
20 }
21
22 map = new int[row][col];
23
24 // 預設 上下左右 全部為牆
25 for (int i = 0; i < col; i++) {
26 map[0][i] = 1;
27 map[row - 1][i] = 1;
28 }
29
30 for (int i = 0; i < row; i++) {
31 map[i][0] = 1;
32 map[i][col - 1] = 1;
33 }
34
35 }
36
37 /**
38 * 在迷宮内部添加擋闆
39 *
40 * @param i 橫坐标
41 * @param j 縱坐标
42 */
43 public void addBaffle(int i, int j) {
44 if (map == null) {
45 return;
46 }
47
48 // 外面一周都是牆
49 if (i > 0 && i < map.length - 1 && j > 0 && j < map[0].length - 1) {
50 map[i][j] = 1;
51 }
52 }
53
54 /**
55 * 設定迷宮的終點位置
56 *
57 * @param desX 橫坐标
58 * @param desY 縱坐标
59 */
60 public void setDes(int desX, int desY) {
61 this.desX = desX;
62 this.desY = desY;
63 }
64
65 public boolean setWay(int i, int j) {
66 // 通路已經找到
67 if (map[desX][desY] == 2) {
68 return true;
69 } else {
70 if (map[i][j] != 0) {
71 return false;
72 }
73
74 // map[i][j] == 0 按照政策 下->右->上->左 遞歸
75 // 假定該點是可以走通.
76 map[i][j] = 2;
77 if (setWay(i + 1, j)) {
78 return true;
79 } else if (setWay(i, j + 1)) {
80 return true;
81 } else if (setWay(i - 1, j)) {
82 return true;
83 } else if (setWay(i, j - 1)) {
84 return true;
85 } else {
86 // 說明該點是走不通,是死路
87 map[i][j] = 3;
88 return false;
89 }
90 }
91 }
92
93 // 顯示地圖
94 public void show() {
95 for (int i = 0; i < map.length; i++) {
96 for (int j = 0; j < map[0].length; j++) {
97 System.out.print(map[i][j] + " ");
98 }
99 System.out.println();
100 }
101 }
102 }
代碼示例:測試類
1 // 測試類
2 public class Main {
3
4 public static void main(String[] args) {
5 MiGong miGong = new MiGong(8, 7);
6 miGong.addBaffle(3, 1);
7 miGong.addBaffle(3, 2);
8 miGong.setDes(6, 5); // 設定目的地
9
10 System.out.println("初始地圖的情況");
11 miGong.show();
12 miGong.setWay(1, 1); // 設定起始位置
13
14 System.out.println("小球走過的路徑,地圖的情況");
15 miGong.show();
16 }
17 }
18
19 // 結果
20 初始地圖的情況
21 1 1 1 1 1 1 1
22 1 0 0 0 0 0 1
23 1 0 0 0 0 0 1
24 1 1 1 0 0 0 1
25 1 0 0 0 0 0 1
26 1 0 0 0 0 0 1
27 1 0 0 0 0 0 1
28 1 1 1 1 1 1 1
29 小球走過的路徑,地圖的情況
30 1 1 1 1 1 1 1
31 1 2 0 0 0 0 1
32 1 2 2 2 0 0 1
33 1 1 1 2 0 0 1
34 1 0 0 2 0 0 1
35 1 0 0 2 0 0 1
36 1 0 0 2 2 2 1
37 1 1 1 1 1 1 1
三、八皇後問題
問題:在8×8格的國際象棋上擺放八個皇後,使其不能互相攻擊,即:任意兩個皇後都不能處于同一行、同一列或同一斜線上,問有多少種擺法。
代碼示例:八皇後
1 public class Queue8 {
2
3 private static final int MAX = 8;
4 // 儲存皇後放置的位置,比如 arr = {0, 4, 7, 5, 2, 6, 1, 3}
5 private final int[] array = new int[MAX];
6
7 public static int count = 0;
8 public static int judgeCount = 0;
9
10 public void check() {
11 this.check(0);
12 }
13
14 // check 是每一次遞歸時,進入到check中都有 for(int i = 0; i < max; i++),是以會有回溯
15 private void check(int n) {
16 // n = 8, 表示8個皇後就已經放好
17 if (n == MAX) {
18 print();
19 return;
20 }
21
22 for (int i = 0; i < MAX; i++) {
23 array[n] = i;
24
25 // 判斷當放置第n個皇後到i列時,是否沖突
26 // 不沖突
27 if (!judge(n)) {
28 // 接着放n+1個皇後,即開始遞歸
29 check(n + 1);
30 }
31 }
32 }
33
34 private boolean judge(int n) {
35 judgeCount++;
36 for (int i = 0; i < n; i++) {
37 // 同一列 或 同一斜線
38 if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
39 return true;
40 }
41 }
42 return false;
43 }
44
45 private void print() {
46 count++;
47 for (int i = 0; i < array.length; i++) {
48 System.out.print(array[i] + " ");
49 }
50 System.out.println();
51 }
52
53 }
1 // 測試類
2 public class Main {
3
4 public static void main(String[] args) {
5 Queue8 queue8 = new Queue8();
6 queue8.check();
7
8 System.out.printf("一共有%d解法", Queue8.count);
9 System.out.printf("一共判斷沖突的次數%d次", Queue8.judgeCount); // 1.5w
10 }
11 }
四、漢諾塔問題
1、問題
2、思想
如果 n = 1,A -> C
如果 n >= 2,總是看做是兩個盤,①最下邊的盤。②上面所有的盤。則,步驟:
(1)先把上面所有的盤 A->B
(2)把最下邊的盤 A->C
(3)把 B 塔的所有盤 從 B->C
3、代碼
代碼示例:漢諾塔問題
1 // 漢諾塔
2 public class Hanoitower {
3
4 // 使用分治算法
5 public static void move(int num, char a, char b, char c) {
6 // 如果隻有一個盤
7 if (num == 1) {
8 System.out.println("第1個盤從 " + a + "->" + c);
9 } else {
10 // n >= 2,總是看做是兩個盤,①最下邊的盤。②上面所有的盤。則,步驟:
11
12 // 1.先把上面所有的盤 A->B.移動過程會使用到 c
13 move(num - 1, a, c, b);
14 // 2.把最下邊的盤 A->C
15 System.out.println("第" + num + "個盤從 " + a + "->" + c);
16 // 3.把 B 塔的所有盤 從 B->C.移動過程會使用到 a
17 move(num - 1, b, a, c);
18 }
19 }
20 }
1 // 測試類
2 public class Main {
3 public static void main(String[] args) {
4 Hanoitower.move(3, 'A', 'B', 'C');
5 }
6 }
7
8 // 結果
9 第1個盤從 A->C
10 第2個盤從 A->B
11 第1個盤從 C->B
12 第3個盤從 A->C
13 第1個盤從 B->A
14 第2個盤從 B->C
15 第1個盤從 A->C