全排列问题
题目描述
输出自然数1到n所有不重复的排列,即n的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
输入描述
输入一行,一个正整数n(1≤n≤9)
输出描述
由1~n组成的所有不重复的数字序列,每行一个序列。每个数字保持5个场宽。
样例输入
3
样例输出
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
代码
#include<iostream>
#include<cstdio>//printf头文件
using namespace std;
int vis[15];//标记数组vis
int n,a[15];
void dfs(int x){
if(x>n){//递归结束条件:个数大于n
for(int i=1;i<=n;i++){//遍历 a数组
printf("%5d",a[i]);//控制列宽为5,不足补空格
}
cout<<endl;
return ;
}
for(int i=1;i<=n;i++){//递归不结束,继续求每一位
if(vis[i]==0){//如果未标记(因为题目不让重复)
a[x]=i;//a数组第X个为i
vis[i]=1;//标记
dfs(x+1);//递归下一位
vis[i]=0;//回溯、清0
a[x]=0;
}
}
}
int main(){
cin>>n;
dfs(1);//从1位开始
return 0;
}
全排列
全排列问题字符版
题目描述
给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。
我们假设对于小写字母有‘a’ <‘b’ < ... <‘y’<‘z’,而且给定的字符串中的字母已经按照从小到大的顺序排列。
输入描述
只有一行,是一个由不同的小写字母组成的字符串,已知字符串的长度在1到8之间。
输出描述
输出这个字符串的所有排列方式,每行一个排列。要求字母序比较小的排列在前面。
字母序如下定义: 已知S=s1s2...sk, T=t1t2...tk,则S<T等价于,存在p(1≤p≤k),使得s1=t1,s2=t2,...,sp−1=tp−1,sp<tp。
样例输入
abc
样例输出
abc acb bac bca cab cba
代码
#include<iostream>
#include<cstring>//n.size()头文件
using namespace std;
int vis[15];//标记数组vis
int len;
string n;
char a[30];
void dfs(int x){
if(x>len-1){//递归结束条件:位数大于原字符串
for(int i=0;i<=len-1;i++){//0~长度-1,遍历
cout<<a[i];
}
cout<<endl;
return ;
}
for(int i=0;i<=len-1;i++){//递归不结束,继续求每一位
if(vis[i]==0){//如果未标记(因为题目不让重复)
a[x]=n[i];//第X位为字符串n第i位
vis[i]=1;//标记
dfs(x+1);//递归下一位
vis[i]=0;//回溯、清0
}
}
}
int main(){
cin>>n;
len=n.size();//求长度
dfs(0);//从0位开始
return 0;
}
素数圆环
题目描述
如图所示为一个由n个圆圈构成的圆环。将自然数1,2,...,n放入圆圈内,并且要求任意两个相邻的圆圈内的数字之和为素数。请问给你圆圈数,你能给出放置自然数的所有正确方案吗?
注意:圆圈中的数字一定是从1开始的,并且连续不重复。
输入描述
输入包含多组测试数据。每组输入占一行,为整数n(0<n<20),表示圆圈数。
输出描述
对于每组输入,输出所有正确的方案,按字典序从小到大排序。每组输出后输出一个空行。具体输出格式见输出样例。
注意:只能按照顺时针方向放置数字。
样例输入
6 8
样例输出
Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2
代码
#include<iostream>
#include<cstdio>//printf头文件
using namespace std;
int vis[15];//标记数组vis
int n,a[15];
bool prime(int n){
int i;
for(int i=2;i*i<=n;i++){
if(n%i==0){
return 0;
}
}
return 1;
}
void dfs(int x){
if(x==n+1){//递归结束条件:位数大于原字符串
if(prime(a[n]+1)&&n!=1){
for(int i=1;i<=n;i++){//遍历 a数组
cout<<a[i]<<" ";//控制列宽为5,不足补空格
}
cout<<endl;
}
return ;
}
for(int i=2;i<=n;i++){//递归不结束,继续求每一位
if(vis[i]==0&&prime(i+a[x-1])==1){//如果未标记(因为题目不让重复)
vis[i]=1;//标记
a[x]=i;//a数组第X个为i
dfs(x+1);//递归下一位
vis[i]=0;//回溯、清0
a[x]=0;
}
}
}
int main(){
a[1]=1;
int cnt=0;
while(cin>>n){
printf("Case %d:\n",++cnt);
dfs(2);
cout<<endl;
}
return 0;
}
01背包问题
题目描述
一个旅行者有一个最多能装 M 公斤的背包,现在有 n 件物品,它们的重量分别是 W1,W2,...,Wn ,它们的价值分别为 C1 , C2 ,..., Cn ,求旅行者能获得最大总价值。
输入描述
第一行:两个整数,M (背包容量,M≤200 )和 N (物品数量, N≤20 );
第 2..N+1 行:每行二个整数 Wi,Ci ,表示每个物品的重量和价值。
输出描述
仅一行,一个数,表示最大总价值。
样例输入
10 4 2 1 3 3 4 5 7 9
样例输出
12
代码
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,w[205],c[25],maxx;
void dfs(int x,int sumw,int sumc){
if(x==n+1){
if(sumw<=m&&sumc>maxx){
maxx=sumc;
}
return ;
}
dfs(x+1,sumw,sumc);
dfs(x+1,sumw+w[x],sumc+c[x]);
}
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>c[i];
}
dfs(1,0,0);
cout<<maxx;
return 0;
}
标签:输出,int,样例,dfs,搜索,include,直观,D3,输入
From: https://blog.csdn.net/XuyuxuanAa/article/details/140495234