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++初學者 今朝逗留在“水題”階段 走一步看一步,摸著石頭過河 向年夜牛看齊