RUC_JudgeOnline 1008 3位数排列问题

 

3位数排列问题

Description

求出所有用N~M之间的数组成的各位数字各不相同的三位数

Input

输入文件包括两个10以内的正整数N,M,两数间有一空格(N小于M)。

Output

输出文件按大小顺序输出组成的三位数,每行一个三位数,每位数间不加空格。

Sample Input

 

7 9

 

Sample Output

 

789
798
879
897
978
987

 

Source

习题6-9

问题分析

这个题目是很典型的数字全排列的问题的演变。鉴于这个题目是指明了三位数，所以有两种思路。一种就是用常规的递归去找数字的全排列的问题。另外一个就是给一个三重的循环通过查重来打印这个全排列。

解决方案

由于是全排列问题的变化，所以，总个数是确定的，是可以通过已经计算出来的。

在查找的过程中，因为在一个排列里面是不允许出现重复数字的，所以必然会使用到一个used[n]的数组，来标记在当前的排列中某个数字是不是使用过。

详见参考代码。

参考代码

顺序方法，用三重循环 使用和递归不一样的方法。用枚举法。虽然效率不高，但是由于数字量小，影响不大。

#include <stdio.h>

int main()
{
	
	int num[11]={0};		//存数字	
	int start,end;			//开始和结束的数字
	
	scanf("%d%d",&start,&end);

	int i,j,k,l;		
	l=end-start+1;				//循环的数字范围
	for (i=start;i<=end;i++)	//把数字存进num数组
	{
		num[i-start+1]=i;
	}
	for (i=1;i<=l;i++)
	{
		for (j=1;j<=l;j++)
		{
			if(num[j]==num[i]) continue;	//有相同数字就continue
			for (k=1;k<=l;k++)
			{
				//有相同数字就continue
				if((num[k]==num[i])||(num[k]==num[j])) continue;
				//如果没有continue则说明现在的三个数字都没有重复的
				printf("%d%d%d\n",num[i],num[j],num[k]);
			}
		}
	}
	return 0;
}

 代码2，用递归的方法去实现

#include <stdio.h>

int N,M;
int a[3];				//存放当前的3位数
bool used[10]={0};		//标记是不是使用过
void search(int);		//递归函数

int main()
{
	scanf("%d%d",&N,&M);
	search(0);
	return 0;
}

void search(int b)
{
	if(b>2)				//b>2说明已经放好了这个三位数，直接打印即可
	{
		int i;
		for(i=0;i<=2;i++)
		{
			printf("%d",a[i]);
		}
		printf("\n");
		return;
	}
	int k;
	for(k=N;k<=M;k++)		//对数字进行递归search
	{
		if(!used[k])		//如果没有使用过则接着做
		{
			a[b]=k;
			used[k]=1;
			search(b+1);	//放下一个位置
			a[b]=0;
			used[k]=0;
		}
	}
	return;
}

 最后复习一下用递归求全排列的方法，使用典型的递归结构。

#include <stdio.h>

int N;					//只考虑数字小于10的情况
int a[10];					//存放当前的序列 
bool used[10]={0};			//标记是不是使用过
void search(int);			//递归函数

int main()
{
	scanf("%d",&N);
	search(0);
	return 0;
}

void search(int b)
{
	if(b==N)				//递归的最前面写上递归的终止条件并进行相关处理，比如，这里的处理是进行打印
	{
		int i;
		for(i=0;i<N;i++)
		{
			printf("%d ",a[i]);
		}
		printf("\n");
		return;
	}
	int k;
	for(k=1;k<=N;k++)		//递归的循环，有时候不是用循环表示的
	{
		if(!used[k])
		{
			a[b]=k;		//进行标记
			used[k]=1;
			search(b+1);	//递归调用
			a[b]=0;		//把标记重置回来
			used[k]=0;
		}
	}
	return;
}