列车调度问题.txt

是一个堆栈的典型事例

设有编号为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