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.zzvips.com/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
