一、递归实现全排列
#include"cstdio"
int A[];
void print_permutation(int n,int *A,int cur){
if(cur==n){
for(int i=;i<n;i++)
printf("%d",A[i]);
printf("\n");
}
else for(int j=;j<n+;j++){
int ok=;
for(int k=;k<cur;k++)
if(A[k]==j)
ok=;
if(ok){
A[cur]=j;
print_permutation(n,A,cur+);
}
}
}
int main(){
int n;
scanf("%d",&n);
print_permutation(n,A,);
return ;
}
二、解答树
#include <string.h>
#include <iostream> using namespace std;
const int N = ; //输入排序的个数的最大值
int record[N]; //记录每次排序的序列
int visited[N]; //标记节点是否被访问过
int n; //输入节点的数目
int totalSize = ;
void DFS(int start){
if(start>=n){ //递归出口
for(int i=;i<n;i++){
cout<<record[i]<<" ";
}
totalSize++;
cout<<endl;
return;
}
for(int i=;i<=n;i++){ //深度遍历节点，并标记已经访问过的节点
if(visited[i]==){
visited[i] = ;
record[start] = i;
DFS(start+); //递归遍历
visited[i] = ; //回退时标记回退的节点为未被访问节点
}
}
} int main()
{
cin>>n;
memset(visited,,n);
DFS();
cout<<"totalSize = "<<totalSize<<endl;
return ;
}
三、
调用next_permutation()方法
四、回溯法总结
1、八皇后问题代码
#include<iostream>
#include<math.h>
using namespace std;
int n=8; int rows[];//存储n行的第几列
int j=;
bool Is(int row){
for(int i=;i<row+;i++){
if(rows[row-i]==rows[row]-i||rows[row-i]==rows[row]+i||rows[row]==rows[row-i])
return false;
}
return true;
}
void start(int row){
if(row==n)
j++;
else {
for(int col=;col<n;col++){
rows[row]=col;
if(Is(row)){
printf("%d %d\n",row,rows[row]);
start(row+);
}
}
}
}
int main(){
start();
printf("%d\n",j);
return ;
}
总结：在全排列和八皇后问题中，均使用了递归回溯。其格式大致为
void f(){
If(){//符合要求的一组解求出后
count++
}else{
For(int ....){
f();//递归调用
}
}
}