全排列问题
题目描述
输出自然数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;
}