设有编号为1，2，3，4，5，6～～～n的n辆列车，顺序进入一个栈式结构的站台。列出这n辆车的所有可能顺序。
谢谢！！！
楼上的意思应该是列车出站时候的所有可能顺序吧
其实，问题的本质就是 在N辆车的全排列中，一个排列只要满足条件：
对于此排列的任何一个元素A，比A元素小的且排在A后面的其他元素是从大到小的顺序排列（不一定要相邻）；
那么，此排列是列车出站顺序的一种。
如，4123不是，4321则是。
由栈的性质知，当某一元素出栈，如比它先入栈的元素还未出栈，则这些元素出来时必按从大到小的顺序弹出栈。
#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <process.h>
bool isTure(const int*, const int);//检验一个排列是否是出站顺序
void main()
{
fstream file;
file.open("result.txt",ios::in|ios::out|ios::trunc);//创建文件
if(!file) //检验是否打开
{
cout<<"无法打开文件！";
exit(1);
}
int traNum; //车的数目
cout<<"请输入车的数目：";
cin>>traNum;
int* p = new int[traNum]; //用于保存由阶乘数产生的排列
int* b = new int[traNum+1]; //阶乘数，最高位b[traNum]用来检验循环，剩下traNum位产生排列
for(int i = 0; i <= traNum; i++)//初始化
b[i] = 0;
while(b[traNum] == 0)
{
int* a = new int[traNum];//用于保存排列的元素
for(int i = 0; i <= traNum-1; i++)//初始化1....traNum
a[i] = i + 1;
for( i = traNum-1; i >= 0; i--)//由阶乘数b产生排列p
{
p[i] = a[b[i]];
for( int j = b[i]; j <= i-1; j++)
a[j] = a[j+1];
}
if( isTure(p, traNum) )//检验是否满足出站顺序条件
{
for(i = 0; i<=traNum-1; i++)//输出至文件
file<<p[i];
file<<endl;
}
b[0]=b[0]+1; //阶乘数b递增1
for(i = 0; (i<=traNum-1)&&(b[i]>i);i++)//检验进制
{
b[i]=0;
b[i+1]=b[i+1]+1;
}
}
file.close();//关闭文件
}
bool isTure(const int* t, const int num)
{
for(int k = 0; k <= num-1; k++)//对每个元素进行比较
{
int temp = num+1;
for( int j = k+1; j <= num-1; j++)//一个元素与其后的每个元素比较
if(t[k] > t[j])
if(temp > t[j])
temp = t[j];
else
return false;
}
return true;
}
楼上的，我只能给这样的注释了，你必须自己去看懂原理，不懂原理光看我的注释是没用的。
_________________
fleeizng
结果保存在result.txt文件里。程序是在VC6.0下通过编译的。
注意：源代码中 \ 都要去掉
_________________
fleeizng
再付上产生全排列的原理：
阶乘数与全排列
所谓阶乘数是指其最低位的基为1，即逢一进一，每高一位则基加一，即进位依次为二、三…，n位阶乘数共有n!个。如三位阶乘数从小到大依次为：000，010，100，110，200，210。
设n元集S={a 0 , a1 , a2, … an-1}，则S的全排列与n位阶乘数一一对应。对应方式为：从n个元素中选取第一个元素有n种方法，被选取的元素的下标值为0到n-1之间的一个整数，将这个数作为n位阶乘数的最高位，将剩下的元素按下标从0到n-2重新编号，重新编号时不改变它们的相对次序，则选取第二个元素有n-1种方法，被选取的元素的下标值为0到n-2之间的一个整数，将这个数作为n位阶乘数的次高位，…，选取最后一个元素只有1种方法，被选取的元素的下标值为0，将这个数作为n位阶乘数的最低位，这样任何一种排列必可对应一个n位阶乘数，显然这种对应关系是一一对应的。
_________________
fleeizng
评论0