组合数
时间限制：3000 ms | 内存限制：65535 KB
难度：3
描述
找出从自然数1、2、... 、n（0<n<10）中任取r(0<r<=n)个数的所有组合。
输入
输入n、r。
输出
按特定顺序输出所有组合。
特定顺序：每一个组合中的值从大到小排列，组合之间按逆字典序排列。
样例输入
5 3样例输出
543
542
541
532
531
521
432
431
421
321
import java.util.Scanner;
public class Main {
static int a[];
static int number;
public static void result(int n,int r)
{
int i,j;
for(i=n;i>0;i--)
{
a[r]=i;
if(r>1)
result(i-1, r-1);
else {
for(j=number;j>0;j--)
{
System.out.print(a[j]);
}
System.out.println();
}
}
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext())
{
int n=scanner.nextInt();
int r=scanner.nextInt();
a=new int[r+1];
number=r;
result(n,r);
}
}
}
另外的一个题目，方法不是很好
擅长排列的小明
时间限制：1000 ms | 内存限制：65535 KB
难度：4
- 描述
- 小明十分聪明，而且十分擅长排列计算。比如给小明一个数字5，他能立刻给出1-5按字典序的全排列，如果你想为难他，在这5个数字中选出几个数字让他继续全排列，那么你就错了，他同样的很擅长。现在需要你写一个程序来验证擅长排列的小明到底对不对。
- 输入
- 第一行输入整数N（1<N<10）表示多少组测试数据，
每组测试数据第一行两个整数 n m (1<n<9,0<m<=n) - 输出
- 在1-n中选取m个字符进行全排列，按字典序全部输出,每种排列占一行，每组数据间不需分界。如样例
- 样例输入
-
2 3 1 4 2
- 样例输出
-
1 2 3 12 13 14 21 23 24 31 32 34 41 42 43
import java.util.Scanner;
public class Main {
static int a[];
static int number,num;
public static void result(int n,int r)
{
int i,j;
for(i=1;i<=n;i++)
{
a[r]=i;
if(r>1)
result(n, r-1);
else {
int flag=1,p,q;
for(p=1;p<=number;p++)
{
for(q=p+1;q<=number;q++)
{
if(a[p]==a[q])
{
flag=0;break;
}
}
if(flag==0)break;
}
if(flag==1)
{
for(j=number;j>0;j--)
{
System.out.print(a[j]);
}
System.out.println();
}
}
}
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int cases=scanner.nextInt();
while(cases--!=0)
{
num=scanner.nextInt();
int r=scanner.nextInt();
a=new int[r+1];
number=r;
result(num,r);
}
}
}
擅长排列的小明比较省时间的方法，深度优先搜索！！！
import java.util.Scanner;
public class Main {
public static int n,r;
public static StringBuffer string;
public static boolean mark[];
public static void dfs(int k)
{
if(k<r)
{
for(int i=1;i<=n;i++)
{
if(!mark[i])
{
string.append(i);
mark[i]=true;
dfs(k+1);
mark[i]=false;
string.deleteCharAt(k);
}
}
}
else {
System.out.println(string);
}
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int cases=scanner.nextInt();
while(cases--!=0)
{
n=scanner.nextInt();
r=scanner.nextInt();
mark=new boolean[n+1];
string=new StringBuffer();
dfs(0);
}
}
}
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main{
public static int n,m;
public static boolean[] mark;
public static StringBuffer sb;
// j也就是for的层数，应该有m层
public static void dfs(int j){// j表示当前正在选第几个数
if(j<m){// 如果j小于总共需要选取的数字个数m
for(int i=1;i<=n;++i)
if(!mark[i-1]){// 如果第i个数字没有被选过
sb.append(i);// 将i记录在字符串中
mark[i-1]=true;// 并标记数字i，已经被选过
dfs(j+1);// 迭代入下一层
mark[i-1]=false;// 还原被标记的数字i
sb.deleteCharAt(j);// 将i删除，还原字符串
}
}else
System.out.println(sb);// j>m，数字已经选择完，输出
}
public static void main(String[] args){
Scanner sc=new Scanner(new BufferedInputStream(System.in));
for(int i=sc.nextInt();i>0;--i){
n=sc.nextInt();// 表示总共有1-n个数字
m=sc.nextInt();// 表示总共需要选取的数字个数
sb=new StringBuffer();// 记录所选上的数字
mark=new boolean[n];// 标记已被选过的数字
dfs(0);// 开始递归取数
}
sc.close();
}
}
类似题目，深度优先搜索题目：素数环
素数环
时间限制：1000 ms | 内存限制：65535 KB
难度：2
- 描述
-
有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。
为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。
- 输入
- 有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束。
- 输出
- 每组第一行输出对应的Case序号，从1开始。
如果存在满足题意叙述的素数环，从小到大输出。
否则输出No Answer。 - 样例输入
-
6 8 3 0
- 样例输出
-
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 Case 3: No Answer
import java.util.Scanner;
public class Main {
static int result[],number;
static boolean vis[];
public static boolean prim(int x)
{
if(x==2||x==3||x==5||x==7||x==11||x==13||x==17||x==19||x==23||x==29)return true;
else {
return false;
}
/*int flag=1;
for(int i=2;i<=Math.sqrt((double)x);i++)
{
if(x%i==0)
{
flag=0;break;
}
}
if(flag==1)return true;
else return false;*/
}
//深度优先搜索的思想
public static void dfs(int x,int n)
{
result[0]=1;
//prim(1+result[number-1])也是一个容易忽略的条件
if(x==number&&prim(1+result[number-1]))
{
for(int i=0;i<number-1;i++)
{
System.out.print(result[i]+" ");
}
System.out.println(result[number-1]);
}
else
{
for(int i=2;i<=number;i++)
{
if(!vis[i]&&prim(result[x-1]+i))
{
result[x]=i;
vis[i]=true;
dfs(x+1, n);
vis[i]=false;
}
}
}
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int cases=1;
while(true)
{
number=scanner.nextInt();
if(number==0)break;
result=new int[number+1];
vis=new boolean[number+1];
result[0]=1;
System.out.printf("Case %d:\n",cases++);
if(number%2==1)
{
//容易忽略的点，1的时候输出1
if(number==1)
System.out.println("1");
else
System.out.println("No Answer");
}
else {
dfs(1,number);
}
}
}
}