程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 更多編程語言 >> 更多關於編程 >> C++火車入軌算法的實現代碼

C++火車入軌算法的實現代碼

編輯:更多關於編程

     這篇文章主要介紹了C++火車入軌算法的實現代碼,有需要的朋友可以參考一下

    【問題描述】   某城市有一個火車站,鐵軌鋪設如圖所示。有n節車廂從A方向駛入車站,按進站順序編號為1~n。你的任務是讓它們按照某種特定的順序進入B方向的鐵軌並駛出車站。為了重組車廂,你可以借助中轉站C。這是一個可以停放任意多節車廂的車站,但由於末端封頂,駛入C的車廂必須按照相反的順序駛出。對於每個車廂,一旦從A移入C,就不能再回到A了;一旦從C移入B,就不能回到C了。換句話說,在任意時刻,只有兩種選擇:A→C和C→B。   這個問題和之前數據結構實驗的火車入軌類似,而且較之簡化。自己嘗試寫了下,和書上參考答案的代碼量仍有較大差距。代碼如下:     代碼如下: #include<iostream> using namespace std; const int MAXSIZE=100; void main() {     int n;     cin>>n;     int a[MAXSIZE],b[MAXSIZE];     int stack[MAXSIZE];     for(int i=0;i<n;i++)     {         a[i]=i+1;         cin>>b[i];                      //出棧順序     }     int top=-1;     int count=0;     int i=0;     for(;;)     {         if(i<n)         {             ++top;             stack[top]=a[i++];            //入棧             cout<<"PUSH"<<endl;         }           if(stack[top]==b[count])         {             top--;count++;             cout<<"POP"<<endl;         }         else if(i==n)         {             cout<<"NO"<<endl;             break;         }         if(count==n)         {             cout<<"YES"<<endl;             break;         }         if(top<-1)         {                 cout<<"NO"<<endl;             break;         }     }   }        書中參考代碼如下:       代碼如下:  #include<iostream> using namespace std; const int MAXN=1000+10; int n,target[MAXN]; void main() {     while(cin>>n)     {         int stack[MAXN],top=0;         int A=1,B=1;                                              //A用來記錄入棧次數,B用來記錄出軌的火車序號         for(int i=1;i<=n;i++)             cin>>target[i];                                        //記錄出軌順序         int ok=1;         while(B<=n)         {             if(A==target[B]){A++;B++;}             else if(top && stack[top]==target[B]){top--;B++;}      //出棧             else if((A<=n)) stack[++top]=A++;                      //入棧             else {ok=0;break;}         }         if(ok)             cout<<"Yes"<<endl;         else             cout<<"No"<<endl;     }      同樣,可以用STL來實現,只需對書中參考答案作微小改動,代碼如下:       代碼如下:  /*STL棧來實現*/ #include<iostream> #include<stack> using namespace std; const int MAXN=1000+10; int n,target[MAXN]; int main() {     while(cin>>n)     {         stack<int> s;         int A=1,B=1;         for(int i=1;i<=n;i++)             cin>>target[i];         int ok=1;         while(B<=n)         {             if(A==target[B]){A++;B++;}             else if(!s.empty() && s.top()==target[B]){s.pop();B++;}             else if(A<=n) s.push(A++);             else {ok=0;break;}         }         if(ok)             cout<<"YES"<<endl;         else             cout<<"NO"<<endl;     } }     【總結】   自己寫的代碼仍有優化的空間。學習參考答案的清晰邏輯的表達。學習STL棧的使用。   聯系數據結構實驗中關於火車入軌的提升,對緩沖軌的限制,應該增加一個判斷即可。   不知坑有多深的C++初學者 目前停留在“水題”階段 走一步看一步,摸著石頭過河 向大牛看齊  
    1. 上一頁:
    2. 下一頁:
    Copyright © 程式師世界 All Rights Reserved