2020年4月19日16:08:44添加:
1.最基础的递归实现全排列:
#include<iostream>
using namespace std;
int n,a[30];
int sum;
int f(int k){
// cout<<k<<endl;
int i,j,flag;
if(k<=n){
for(i=1;i<=n;i++)
{
a[k] = i;
flag = 0;
for(j=1;j<k;j++){//判断前k个数与第k个数有重复不
if(a[j]==a[k])
flag = 1;
}
if(flag==0){
if(k==n){//最后一个数
sum++;
for(j=1;j<=n;j++)
cout<<a[j];
cout<<endl;
}else{
f(k+1);
}
}
}
}
else{
return sum;
}
}
int main(){
cin>>n;
f(1);
cout<<sum;
}
2.回溯法
#include"iostream"
using namespace std;
int n,f[100],ans[100];
void dfs(int k){
int i;
if(k==n){
for(int j=1;j<=n;j++)
cout<<ans[j]<<' ';
cout<<endl;
return;
}
for(i=1;i<=n;i++){
//未被遍历过的
if(!f[i]){
f[i] = 1;//表示遍历过了
ans[k+1] = i;
dfs(k+1);
f[i] = 0;//回溯
}
}
}
int main(){
cin>>n;
dfs(0);
}
3.手写交换法
#include<bits/stdc++.h>
using namespace std;
//求n的全排列 n!组数据
/*
每个全排列都有n个数,所以将求这n个数的全排列进行分解 :
1-求n-1的全排列
2-求n-2的全排列
3-求n-3的全排列
.
.
.
n-求1的全排列
*/
int n;
int data[100];
//void swap(int& x,int& y){//交换两个数的值
// int temp = x;
// x = y;
// y = temp;
//}
void swap(int *x,int *y){//形参为两个指针
int temp = *x;
x = y;
*y = temp;
}
void solve(int t){
int i;
if(t == n)
{
for(i=1;i<=n;i++)
cout<<data[i]<<" ";
cout<<endl;
return;
}
//前t个数的已确定 接下来确定后面的数
for(i = t; i <= n; i++){
//每次交换两个数的值
swap(data[i],data[t]);
//进入递归------->每次进入solve()即开始确认第t+1位上的数
//当t == n 那么就进行输出这一组排列数据
solve(t + 1);
//还原数组为原来状态
swap(data[i],data[t]);
}
}
int main(){
//初始化 数组
memset(data,0,sizeof(data));
cout<<"input n:";
cin>>n;
//数组放入值
for(int i = 1; i <= n; i++)
data[i]=i;
solve(1);
}
后面继续努力,祝我,也祝各位在算法的道路上坚持下来。
原文链接: https://www.cnblogs.com/Tisou1/p/12173565.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/191672
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!