1. 漢諾塔問題
遞歸算法，分為 3 步：將 n 個 a 上的盤子借助 c 移動到 b
① 將 n-1 個 a 上的盤子借助 b 移動到 c
② 將 a 上的盤子移動到 b
③ 將 c 上的 n-1 個盤子借助 a 移動到 b
所有盤子都移動到 b 上了
|
1
2
3
4
5
6
7
8
9
10
11
|
void hanoi(int n,char a,char b,char c)//將n個碟子從a借助c 移到b { if(n==0) return; else { hanoi(n-1,a,c,b); move(a,b); hanoi(n-1,c,b,a); ｝｝ |
2. 全排列問題
問題描述：設R={r1,r2,…,rn}是要進行排列的n個元素，求R的全排列Perm(R)。
算法思路：
① 從 n 個數中取出數列的第一個數，然后不斷將數列中剩余的數與第一個數進行交換，計算剩余 n-1 個數的全排列。
② 對 n - 1 個數進行同樣的遞歸操作，當交換的第一個數的下標 k 和 序列末尾的 m 相同時，說明前置所有數都已經交換完成，進行輸出。
③ 遞歸結束后進行狀態回調，保證不影響下一次遞歸的進行。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void Perm(int list[], int k, int m){ if(k==m) { for(int i=0;i<m;i++） { cout<<list[i]; } cout<<endl; return; } for(int i=k;i<m;i++) { swap(list[k], list[i]) Perm(list, k+1, m) swap(list[k], list[i]) }} |
3. 利用遞歸與分治策略尋找最大值
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <bits/stdc++.h>using namespace std; int find_max(int a[], int from, int to){ if(from>=to) return a[from]; int mid = (from + to)/2; int v1 = find_max(a, from, mid); int v2 = find_max(a, mid+1, to); if(v1<=v2) return v2; else return v1;} int main(){ int n, a[100000]; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } cout<<find_max(a, 0, n-1);} |
4. 歸并排序
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <bits/stdc++.h> using namespace std; void merge_array(int a[], int from, int mid, int to){ int tmp[100000], idx_tmp=0; int i,j; for(i=from, j=mid+1; i<=mid && j<=to;){ if(a[i]<=a[j]) tmp[idx_tmp++] = a[i++]; else tmp[idx_tmp++] = a[j++]; } while(i<=mid) tmp[idx_tmp++]=a[i++]; while(j<=to) tmp[idx_tmp++]=a[j++]; for(int i=from,j=0; i<=to;i++) a[i] = tmp[j++]; } void merge_sort(int a[], int from, int to){ if(from < to){ int mid = (from + to)/2; merge_sort(a, from, mid); merge_sort(a, mid+1, to); merge_array(a, from, mid, to); }} int main(){ int n, a[100000]; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } merge_sort(a, 0, n-1); for(int i=0;i<n;i++){ printf("%d ", a[i]); }} |
5. 快速排序
圖解快速排序：http://www.ythuaji.com.cn/article/162749.html
遞歸 + 交換法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <bits/stdc++.h> using namespace std; int sort_array(int a[], int from, int to){ int base = a[from]; int i,j; for(i=from, j=to; i<j;) { while(a[j]>=base && i<j) j--; while(a[i]<=base && i<j) i++; //function swap() if(i<j){ int t=a[i]; a[i]=a[j]; a[j]=t; } } a[from]=a[i]; a[i]=base; return i;} void quick_sort(int a[], int from, int to){ if(from>=to) return; int i = sort_array(a, from, to); quick_sort(a, from, i-1); quick_sort(a, i+1, to);} int main(){ int n, a[100000]; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } quick_sort(a, 0, n-1); for(int i=0;i<n;i++){ printf("%d ", a[i]); }} |
6. 棋盤覆蓋問題
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include <bits/stdc++.h> using namespace std; int num=0;int a[1000][1000]; void make_chess(int px, int py, int tx, int ty, int sze){ if(sze==1) return; num++; sze/=2; //左上 if(px<tx+sze && py<ty+sze) { a[tx+sze-1][ty+sze]=num; a[tx+sze][ty+sze-1]=num; a[tx+sze][ty+sze]=num; } //右上 if(px<tx+sze && py>=ty+sze) { a[tx+sze-1][ty+sze-1]=num; a[tx+sze][ty+sze-1]=num; a[tx+sze][ty+sze]=num; } //左下 if(px>=tx+sze && py<ty+sze) { a[tx+sze-1][ty+sze-1]=num; a[tx+sze-1][ty+sze]=num; a[tx+sze][ty+sze]=num; } //右下 if(px>=tx+sze && py>=ty+sze) { a[tx+sze-1][ty+sze-1]=num; a[tx+sze-1][ty+sze]=num; a[tx+sze][ty+sze-1]=num; } //左上 if(px<tx+sze && py<ty+sze) make_chess(px, py, tx, ty, sze); else make_chess(tx+sze-1, ty+sze-1, tx, ty, sze); //右上 if(px<tx+sze && py>=ty+sze) make_chess(px, py, tx, ty+sze,sze); else make_chess(tx+sze-1, ty+sze, tx, ty+sze,sze); //左下 if(px>=tx+sze && py<ty+sze) make_chess(px, py, tx+sze, ty,sze); else make_chess(tx+sze, ty+sze-1, tx+sze, ty, sze); //右下 if(px>=tx+sze && py>=ty+sze) make_chess(px, py, tx+sze, ty+sze, sze); else make_chess(tx+sze, ty+sze, tx+sze, ty+sze, sze); } int main(){ int k, px, py; int tx=0, ty=0; cin>>k>>px>>py; make_chess(px-1, py-1, tx, ty, k); for(int i=0; i<k; i++){ for(int j=0; j<k; j++){ printf("%2d ", a[i][j]); } cout<<endl; } } |
以上就是C++遞歸與分治算法原理示例詳解的詳細內容，更多關于C++遞歸與分治算法的資料請關注服務器之家其它相關文章！
原文鏈接：https://blog.csdn.net/sinat_40471574/article/details/115439533
