C++HOJ列車が駅に入る

【問題の説明】列車数を表す正の整数Nが与えられ、0入力:複数の試験例があり、各組の第1行に正の整数Nが入力される(0出力:辞書順に並べ替えられた列車の駅外シリアル番号を出力し、各番号はスペースで区切られ、各出力シーケンスは改行され、具体的にはsampleを参照.サンプル入力:3 1 2 3サンプル出力:1 2 3 1 3 3 2 2 1 3 3 3 1 3 2 2 3 3 2 1
【問題解きの考え方一】
スタックは先進的な後出、後進的な先出の特徴を持っているため、いずれのスケジューリング結果も1,2,3,4の全配列の要素であるべきである.スタックに入る順序は小さいから大きいので、スタックを出る順序は以下の条件を満たすべきである:シーケンスのいずれかの数に対して、その後のすべてのそれより小さい数は逆順序であるべきであり、例えば4321は有効なスタックを出るシーケンスであり、1423は有効なスタック結果ではありません(4より小さい2つの数2、3は逆の順序ではありません).これにより、本題はアルゴリズムによってn個の数の全配列を生成し、その後、スタック規則を満たすシーケンスを出力します.この再帰定義に従って、再帰アルゴリズムは以下のようになります.

#include  
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;istr[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

【問題解きの考え方2】
ここで辞書順ソートとは、このn台の列車がどのように駅を出る可能性のある順序(すなわち、データ構造のスタックがどのようにスタックを出すか)を意味する.構想は、3つの変数で待機駅列車、駅中列車、およびすでに駅を出た列車をそれぞれ格納し、その中で待機駅火車用Queue(キュー)格納および駅中列車はstackを採用する(スタック)記憶、すでに駅を出た列車はStringBuilderを採用して記憶して、具体的に実現するのは再帰の方法を採用して、再帰関数のパラメータは現在の待機駅の列車、駅の中の列車、すでに駅を出た列車の値からなる3元のグループで、再帰の終了条件は、まだ駅に入っていない列車と駅の中の列車はすべて空で、この時すでに駅を出た列車を出力するのはすべての駅の1種の可能性で、再帰の関門現在の状況に対して次の列車を駅に入れるか、駅の中の1台を駅から出させるかの2つの可能性があり、2つの可能性に対してそれぞれ再帰関数を呼び出すと、問題の解が得られる.
【Java実装】
【解題構想3】この問題は、すべてのスタックの順序を求めるためにスタックのシーケンスを与えるように抽出することができる.この問題はシミュレーション問題であり、スタックの順序をシミュレートする.要素ごとにスタックに入ると、2つの行為が可能である:スタックを出るかスタックに残る.プロセス全体を1つの木の形式で表現することができる.そのため、朔法を採用する(遡及法の過程は一課樹の形式である)

//   ，       +  。       ，       （     ，   ）  
//             （        ，   ）  
#include  
#include  
#include  
#include  
using namespace std;  
int num;  
int input[10];  
int output[10];  
int output_index;  
int heap[10];  
int heap_index;  
vectorvec;  
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

【問題解きの考え方四】
STL方法:1、n=1なら配列方式;2、n>1の場合はn-1の出桟順を求め、n-1の前、n-1の後、n-1の後、n-1の後の各数に分けて挿入します!

#include 
#include 
#include 
#include 
using namespace std;


void helper(string &inTrain,vector &outTrain,int index){
    if(index == inTrain.size()){
        return;
    }//if
    if(index == 0){
        string outNum("");
        outNum += inTrain[index];
        outTrain.push_back(outNum);
    }//if
    else{
        vector 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 TrainLeft(string inTrain){
    vector 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 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<