RUC_JudgeOnline 1008 3位数排列问题
?
3位数排列问题
Description
求出所有用N~M之间的数组成的各位数字各不相同的三位数
Input
输入文件包括两个10以内的正整数N,M,两数间有一空格(N小于M)。
Output
输出文件按大小顺序输出组成的三位数,每行一个三位数,每位数间不加空格。
Sample Input
?
7 9
?
Sample Output
?
789798879897978987
?
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;//有相同数字就continuefor (k=1;k<=l;k++){//有相同数字就continueif((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;}?