鱼C论坛

 找回密码
 立即注册
查看: 2510|回复: 1

[已解决]火车问题

[复制链接]
发表于 2017-3-26 13:47:02 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 我是追风者 于 2017-3-26 17:50 编辑

编号为1、2、3、...n的n列火车进栈式结构的站台,问出站的序列是哪些?编写程序打印这些出站序列
最佳答案
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;  
      
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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;  
      
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 16:40

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表