AKSZ-深度优先搜索
2024-05-12 17:33:43
发布于:广东
3阅读
0回复
0点赞
AKSZ-深度优先搜索
排列组合( A (n,m) )($ *****) )
A (n,m) =n(n-1)(n-2)......(n-m+1)
*****)=A(n,m)/A(m,m)=n(n-1)(n-2)......(n-m+1)/m!
排列代码
//排列
#include<bits/stdc++.h>
using namespace std;
int n,m,a[114514],vis[114514]={0};
void dfs(int x){
if(x>m){
for(int i=1;i<=m;i++){
cout<<a[i]<<" ";
}
cout<<endl;
return ;
}
for(int i=1;i<=n;i++){
if(vis[i]==0){
vis[i]=1;
a[x]=i;
dfs(x+1);
vis[i]=0;
}
}
}
int main(){
cin>>n>>m;
dfs(1);
return 0;
}
组合代码
//组合
#include<bits/stdc++.h>
using namespace std;
int n,m,a[114514],vis[114514]={0};
void dfs(int x,int last){
if(x>m){
for(int i=1;i<=m;i++){
cout<<a[i]<<" ";
}
cout<<endl;
return ;
}
for(int i=last+1;i<=n;i++){
if(vis[i]==0){
vis[i]=1;
a[x]=i;
dfs(x+1,i);
vis[i]=0;
}
}
}
int main(){
cin>>n>>m;
dfs(1,0);
return 0;
}
DFS
1.标记(vis[]->回溯(vis[i]=0))
2.剪枝
1.可行性
2.最优性
3.连通性
全部评论 1
DFS可以放一些例题,内容有些不足
2024-05-15 来自 广东
0
有帮助,赞一个