火车问题
本帖最后由 我是追风者 于 2017-3-26 17:50 编辑编号为1、2、3、...n的n列火车进栈式结构的站台，问出站的序列是哪些？编写程序打印这些出站序列 火车编号为：1~9，且不重复。
如：编号分别为“1”、“2”、“3”、“4”、“5”的5个火车顺序进站，那么进站序列为“12345”，全部进站后再顺序出站，则出站序列为“54321”，如果先进1,2，然后2出站，然后1出站，然后再3进站、出站，4进站、出站，5进站、出站，那么出站序列就为21345.
问题分析：
栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是1 ，2 ，3 ，4 全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对于序列中的任何一个数其后面所有比它小的数应该是倒序的，例如4321 是一个有效的出栈序列，1423不是一个有效的出栈结果（4 后面比它小的两个数 2 ，3 不是倒序）。
如果要列出所有的出站组合，则可以通过算法产生n 个数的全排列，然后将满足出栈规则的序列输出。
view plain copy 在CODE上查看代码片派生到我的代码片
/*
详细描述：
int JudgeTrainSequence (int maxNum, char *pOutSeq);
输入参数：
int maxNum：进站的火车最大编号
char* pOutSeq：使用字符串表示火车出站序列
输出参数（指针指向的内存区域保证有效）：
无。
返回值：
Int: 根据输入的进站序列判断，如果输入的出战序列是可能的，返回1，否则返回0；
*/
int JudgeTrainSequence (int maxNum, char *pOutSeq)
{
if(maxNum<1 || maxNum>9)
{
return 0;
}
/*
if(pOutSeq == 0)
{
return 0;
}
*/
int length = strlen(pOutSeq);
int *num = (int *)malloc(length*sizeof(int));
memset(num,0,length);
int i=0;
while(pOutSeq!='\0')
{
num = pOutSeq-'0';
printf("%d",num);
i++;
}
int j,k;
//从num开始逐个选择元素
for(j=0;j<length;j++)
{
int flag = num;
int max = 0;
int sw = 0;
for(k=j+1;k<length;k++)
{
//找出比num小的元素
if(num<flag)
{
//降序排列
if(sw==0)
{
max = num;
}
sw = 1;
if(num>max)
{
return 0;
}
}
}
}
return 1;
}
页:
[1]