本文共 2520 字，大约阅读时间需要 8 分钟。
//题意：找到一个数子序列包含所有的n位数一次切仅一次。
分析：首先要明白为什么选择一个好的数字序列，至多只需要按键10^n+n-1就可以打开保险箱了。n位数有10^种编码方案（即10^n组数），要使得一个数字序列包含这10^n组n位数，且序列的长度最短，唯一的可能是每组数出现一次切尽一次，且前一组数的后n-1位是后以数组的前n-1位，这样10^n组数各取1位，共10^n位，再加上最后一组数的后n-1位，总位数是10^n+n-1.
求序列的方法是:对于当前长度为n-1的序列，其后添加一个数字，使得添加后的序列没有在前面出现过。需要注意的是：由于1<=n<=6，直接用递归方法会照成栈溢出，需要显式的用栈来实现算法。这时的输出序列为从后往前，故用栈存储结构时，优先存储的应是较大的值。这样最后对结果栈进行逆序输出的时候得到的串是按字典序排列的。
// I'm the Topcoder//C#include #include #include #include #include #include //C++#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;//*************************OUTPUT*************************#ifdef WIN32#define INT64 "%I64d"#define UINT64 "%I64u"#else#define INT64 "%lld"#define UINT64 "%llu"#endif//**************************CONSTANT***********************#define INF 0x3f3f3f3f#define eps 1e-8#define PI acos(-1.)#define PI2 asin (1.);typedef long long LL;//typedef __int64 LL; //codeforcestypedef unsigned int ui;typedef unsigned long long ui64;#define MP make_pairtypedef vector VI;typedef pair PII;#define pb push_back#define mp make_pair//***************************SENTENCE************************#define CL(a,b) memset (a, b, sizeof (a))#define sqr(a,b) sqrt ((double)(a)*(a) + (double)(b)*(b))#define sqr3(a,b,c) sqrt((double)(a)*(a) + (double)(b)*(b) + (double)(c)*(c))//****************************FUNCTION************************template double DIS(T va, T vb) { return sqr(va.x - vb.x, va.y - vb.y); }template inline T INTEGER_LEN(T v) { int len = 1; while (v /= 10) ++len; return len; }template inline T square(T va, T vb) { return va * va + vb * vb; }// aply for the memory of the stack//#pragma comment (linker, "/STACK:1024000000,1024000000")//end#define M 1000000+100int lists[M];int stacks[M];//用数组模拟栈结构char ans[M];//结果栈，序列逆序存放int s,a;//数组栈的大小以及结果栈的大小//对于当前长度为n-1的序列，其后添加一个数字，使得添加后的序列没有在前面出现过void search(int v,int m){ int w; while(lists[v]<10){ //printf("lists[%v]=%d\n",v,lists[v]); w=v*10+lists[v]; //printf("w=%d\n",lists[v]); lists[v]++; //printf("lists[v]=%d") stacks[s++]=w; //存入栈中 v=w%m; }}int main(){ int n,m,v; while(scanf("%d",&n)!=EOF){ if(n==0) break; if(n==1){ printf("0123456789\n");continue; } s=0; a=0; v=0;//初始化 s:数组栈的大小， a结果栈的大小 ，v??? m=pow(10.0,double(n-1)); //m=10^(n-1) for(int i=0;i
转载于:https://www.cnblogs.com/lanjiangzhou/archive/2013/04/01/2992658.html
View Code