C++递归与分治算法原理示例详解
目录
1. 汉诺塔问题
2. 全排列问题
3. 利用递归与分治策略寻找最大值
4. 归并排序
5. 快速排序
6. 棋盘覆盖问题
1. 汉诺塔问题 
递归算法，分为 3 步：将 n 个 a 上的盘子借助 c 移动到 b
① 将 n-1 个 a 上的盘子借助 b 移动到 c
② 将 a 上的盘子移动到 b
③ 将 c 上的 n-1 个盘子借助 a 移动到 b
所有盘子都移动到 b 上了
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 相同时，说明前置所有数都已经交换完成，进行输出。
③ 递归结束后进行状态回调，保证不影响下一次递归的进行。
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. 利用递归与分治策略寻找最大值
#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. 归并排序
#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. 快速排序
图解快速排序：//www.jb51.net/article/113769.htm
递归 + 交换法
#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. 棋盘覆盖问题
#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++递归与分治算法的资料请关注软件开发网其它相关文章！
