C++ HOJ 火车进站

Bertha 。 2022-08-02 12:50 185阅读 0赞

【问题描述】  
给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号。要求以字典序排序输出火车出站的序列号。  
输入:  
有多组测试用例，每一组第一行输入一个正整数N（0<N<10），第二行包括N个正整数，范围为1到9。  
输出:  
输出以字典序排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。  
样例输入:  
3  
1 2 3  
样例输出:  
1 2 3  
1 3 2  
2 1 3  
2 3 1  
3 2 1

【解题思路一】

栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是1 ，2 ，3 ，4全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对于序列中的任何一个数其后面所有比它小的数应该是倒序的，例如4321 是一个有效的出栈序列，1423不是一个有效的出栈结果（4 后面比它小的两个数 2 ，3 不是倒序）。据此，本题可以通过算法产生n 个数的全排列，然后将满足出栈规则的序列输出。 依此递归定义，递归算法如下：

#include<stdio.h>  
    int cont=1;  
    void print(int str[],int n);  
    void perm(int str[],int k,int n)  
    {  
        int i,temp;  
        if(k==n-1)print(str,n);//k和n-1相等，即一趟递归走完   
        else{  
            for(i=k;i<n;i++){//把当前节点元素与后续节点元素交换   
                temp=str[k]; str[k]=str[i]; str[i]=temp;//交换   
                perm(str,k+1,n);//把下一个节点元素与后续节点元素交换   
                temp=str[i]; str[i]=str[k]; str[k]=temp;//恢复原状    
            }  
        }  
    }  
    /* 本函数判断整数序列 str[] 是否满足进出栈规则, 若满足则输出*/   
    void print(int str[],int n)   
    {  
        int i,j,k,l,m,flag=1,b[2];   
        for(i=0;i<n;i++)    /* 对每个str[i] 判断其后比它小的数是否为降序序列*/   
        {  
            m=0;   
            for(j=i+1;j<n&&flag;j++){   
                if (str[i]>str[j])  
                {  
                    if (m==0) b[m++]=str[j];//记录str[i]后比它小的数   
                    else   
                    {  
                        //如果之后出现的数比记录的数还大，改变标记变量   
                        if (str[j]>b[0]) flag=0;  
                        //否则记录这个更小的数   
                        else b[0]=str[j];   
                    }   
                }  
            }   
        }   
        if(flag)        /* 满足出栈规则则输出 str[] 中的序列*/   
        {     
            printf(" %2d:",cont++); //输出序号   
            for(i=0;i<n;i++)   
                printf("%d",str[i]);//输出序列   
            printf("\n");   
        }   
    }   
    int main()   
    {  
        int str[100],n,i;   
        printf("input a int:");     /* 输出排列的元素个数*/   
        scanf("%d",&n);   
        for(i=0;i<n;i++)         /* 初始化排列集合*/   
            str[i]=i+1;             //第i个节点赋值为i+1   
        printf("input the result:\n");   
        perm(str,0,n);              //调用递归   
        printf("\n");   
        return 0;   
    }

【解题思路二】  
此处所谓字典序排序的意思是这n辆火车有多少种出站的可能顺序（也就是数据结构中的栈有多少种出栈顺序）。思路为用三个变量分别存储待进站火车，站中火车和已出站火车，其中待进站火车用Queue（队列）存储和站中火车采用stack（栈）存储，已出站火车采用StringBuilder来存储，具体实现是采用递归的方法，递归函数的参数为当前待进站火车、站中火车、已出站火车的值所组成的三元组，递归结束条件是，未进站火车和站中火车均为空，此时输出已出站火车即为所有出站的一种可能，递推关系为对于当前情况有让下一辆火车进站或让站中的一辆火车出站两种可能，对于两种可能分别调用递归函数，即可得出问题的解。

【Java 实现】

【解题思路三】  
该问题可以提炼成为给出进栈序列，求出所有的出栈顺序。该题是一道模拟题，模拟进栈出栈的顺序。对于每一个元素进栈后 都可以有2种行为：出栈或者驻留在栈中。整个过程可以用一个树的形式来表达。因此采用回朔法（回溯法的过程就是一课树的形式）

//回溯法，其核心就是循环+递归。为了表示正确性，其中每一步操作（如修改数据，进栈等）  
    //都应该有相应的对称操作还原（如将修改数据还原，出栈等）  
    #include<stdio.h>  
    #include<string.h>  
    #include<vector>  
    #include<algorithm>  
    using namespace std;  
    int num;  
    int input[10];  
    int output[10];  
    int output_index;  
    int heap[10];  
    int heap_index;  
    vector<int* >vec;  
    void DF(int n);  
    void df(int n)  
    {  
        if(heap_index==0)  
            return ;  
        //退出栈 放入输入队列中  
        output[output_index++]=heap[--heap_index];  //对称1  
        heap[heap_index]=0;  
        for(int i=0;i<2;i++)  
        {  
            if(i==0)  
                df(n);  
            else  
                DF(n+1);  
        }  
       heap[heap_index++]=output[--output_index];   //对称1  
       output[output_index]=0;  
      
      
    }  
      
    void DF(int n)  
    {  
        heap[heap_index++]=input[n];  //放入 ，对称2  
        if(n==num-1)   //该函数退出时（一般在回溯法中，在函数出口内部是不存在对称结构，但是该题中存在其他函数df调用该回溯函数，故返回到）  
        {  
            int temp=heap_index;  
            output[output_index++]=heap[--heap_index]; //对称3  
            heap[heap_index]=0;  
      
            while(heap_index)  
                output[output_index++]=heap[--heap_index];  
            int *p=(int *)malloc(sizeof(int)*num);  
            for(int i=0;i<output_index;i++)  
                p[i]=output[i];  
            vec.push_back(p);  
            while(temp)                                //对称3  
            {  
                heap[heap_index++]=output[--output_index];  
                output[output_index]=0;  
                temp--;  
            }  
            heap[--heap_index]=0;          //对称2  
            return ;  
      
      
        }  
        for(int i=0;i<2;i++)  
        {  
            if(i==0)  
                df(n);  
            else  
                DF(n+1);   //i==1的时候就是不将数据退出栈  
        }  
        heap[--heap_index]=0;      //对称2  
      
    }  
      
    bool cmp(int* t1,int* t2)  
    {  
        for(int i=0;i<num;i++)  
        {  
            if(t1[i]==t2[i])  
                continue;  
            return t1[i]<t2[i];  
        }  
        return true;  
    }  
    int main()  
    {  
        freopen("a.txt","r",stdin);  
        while(scanf("%d",&num)!=EOF)  
        {  
            memset(input,0,sizeof(input));  
            memset(output,0,sizeof(input));  
            memset(heap,0,sizeof(input));  
            output_index=0;  
            heap_index=0;  
            vec.clear();  
            for(int i=0;i<num;i++)  
                scanf("%d",input+i);  
            DF(0);  
            sort(vec.begin(),vec.end(),cmp);  
            for(unsigned int i=0;i<vec.size();i++)  
            {  
                for(int j=0;j<num-1;j++)  
                    printf("%d ",vec[i][j]);  
                printf("%d\n",vec[i][num-1]);  
            }  
        }  
        return 0;  
    }

【解题思路四】  
STL方法：1、若n=1那么就一种排列方式；2、n>1时先求出n-1的出栈顺序，再分开将n插入n-1之前，n-1之后和每一个n-1之后的每一个数！

#include <iostream>
    #include <string>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    
    void helper(string &inTrain,vector<string> &outTrain,int index){
        if(index == inTrain.size()){
            return;
        }//if
        if(index == 0){
            string outNum("");
            outNum += inTrain[index];
            outTrain.push_back(outNum);
        }//if
        else{
            vector<string> newOutTrain;
            // 出栈序列
            int size = outTrain.size();
            // 第index辆火车进栈
            for(int i = 0;i < size;++i){
                // 第i个出栈序列
                int count = outTrain[i].size();
                // 寻找前一个进栈的火车下标
                int targetIndex;
                for(int j = 0;j < count;++j){
                    if(inTrain[index-1] == outTrain[i][j]){
                        targetIndex = j;
                        break;
                    }//if
                }//for
                string tmp(outTrain[i]);
                for(int j = targetIndex;j <= count;++j){
                    tmp.insert(tmp.begin()+j,inTrain[index]);
                    newOutTrain.push_back(tmp);
                    tmp.erase(tmp.begin()+j);
                }//for
            }//for
            swap(outTrain,newOutTrain);
        }//else
        helper(inTrain,outTrain,index+1);
    }
    
    
    vector<string> TrainLeft(string inTrain){
        vector<string> result;
        int size = inTrain.size();
        if(size <= 0){
            result;
        }//if
        helper(inTrain,result,0);
        sort(result.begin(),result.end());
        return result;
    }
    
    
    int main(){
        int n;
        //freopen("C:\\Users\\Administrator\\Desktop\\c++.txt","r",stdin);
        while(cin>>n){
            string train("");
            int num;
            for(int i = 1;i <= n;++i){
                cin>>num;
                train += num + '0';
            }//for
            vector<string> trainNum = TrainLeft(train);
            // 输出
            int size = trainNum.size();
            for(int i = 0;i < size;++i){
                int count = trainNum[i].size();
                for(int j = 0;j < count;++j){
                    if(j == 0){
                        cout<<trainNum[i][j];
                    }//if
                    else{
                        cout<<" "<<trainNum[i][j];
                    }//else
                }//for
                cout<<endl;
            }//for
        }//while
        return 0;
    }