[已解决]火车问题

我是追风者

编号为1、2、3、...n的n列火车进栈式结构的站台，问出站的序列是哪些？编写程序打印这些出站序列

最佳答案

月排行榜 / 总排行榜

新手·ing

2017-3-26 16:32:44

火车编号为：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 个数的全排列，然后将满足出栈规则的序列输出。

[cpp] 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[i]!='\0')  
    {  
        num[i] = pOutSeq[i]-'0';  
        printf("%d",num[i]);  
        i++;  
    }  
    int j,k;  
    //从num[0]开始逐个选择元素  
    for(j=0;j<length;j++)  
    {  
        int flag = num[j];  
        int max = 0;  
        int sw = 0;  
        for(k=j+1;k<length;k++)  
        {  
            //找出比num[j]小的元素  
            if(num[k]<flag)  
            {  
                //降序排列  
                if(sw==0)  
                {  
                    max = num[k];  
                }  
                sw = 1;  
                if(num[k]>max)  
                {  
                    return 0;  
                }  
            }  
        }  
    }  
    return 1;  
      
}

跳转到最佳答案楼层

新手·ing

火车编号为：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 个数的全排列，然后将满足出栈规则的序列输出。

[cpp] 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[i]!='\0')  
    {  
        num[i] = pOutSeq[i]-'0';  
        printf("%d",num[i]);  
        i++;  
    }  
    int j,k;  
    //从num[0]开始逐个选择元素  
    for(j=0;j<length;j++)  
    {  
        int flag = num[j];  
        int max = 0;  
        int sw = 0;  
        for(k=j+1;k<length;k++)  
        {  
            //找出比num[j]小的元素  
            if(num[k]<flag)  
            {  
                //降序排列  
                if(sw==0)  
                {  
                    max = num[k];  
                }  
                sw = 1;  
                if(num[k]>max)  
                {  
                    return 0;  
                }  
            }  
        }  
    }  
    return 1;  
      
}