火車調(diào)度問題PROJECT.

1、Project1火車車廂重排調(diào)度年級：2014級 學院：電子與信息工程學院 班級：智能科學與技術(shù)、自動化姓名：王金頂 14350046 姓名：王帆 14350045 姓名：張宇航 14350069 【題目要求】1.問題：一列火車要將n節(jié)車廂分別送往n個車站，車站按照n,n-1,1的編號次序經(jīng)過車站。假設(shè)車廂的編號就是其目的地車站的編號。2.要求：給定一個任意的車廂排列次序。重新排列車廂，使其按照從1到n的次序排列。規(guī)定重排調(diào)度時車廂只能從入軌到緩沖鐵軌，或者從緩沖鐵軌到出軌?！緮?shù)據(jù)結(jié)構(gòu)與算法】本程序?qū)５目臻g設(shè)為25（可以通過全局常量maxstack直接修改），棧的最大數(shù)量設(shè)為100（可以直接

2、修改）?？梢蕴幚砣我馍儆?00個任意次序車廂的火車重排調(diào)度問題。流程圖如圖1：圖1 總流程圖【測試數(shù)據(jù)、結(jié)果及分析】實驗1：順序輸入車廂節(jié)數(shù)：10車廂順序：1 2 3 4 5 6 7 8 9 10測試結(jié)果如圖2。圖2 實驗1測試結(jié)果測試序列重排成功，使用0個棧，返回值正常，實驗程序運行良好。實驗2：倒序輸入車廂節(jié)數(shù)：10車廂順序：10 9 8 7 6 5 4 3 2 1測試結(jié)果如圖3。圖3實驗2測試結(jié)果測試序列重排成功，使用1個棧，實驗程序運行良好。實驗3：亂序輸入車廂節(jié)數(shù)：10車廂順序：3 2 4 5 7 8 9 6 1 10測試結(jié)果如圖4。圖4實驗3測試結(jié)果測試序列重排成功，使用7個棧，實

3、驗程序運行良好。實驗4：亂序輸入車廂節(jié)數(shù)：25車廂順序：25 2 6 4 5 3 7 23 9 19 11 12 16 14 15 13 17 18 10 22 21 20 8 24 1測試結(jié)果如圖5。圖5 實驗4測試結(jié)果測試序列重排成功，使用13個棧，實驗程序運行良好。實驗五：亂序輸入車廂節(jié)數(shù)：50車廂順序：46 47 50 38 32 29 21 39 1 37 12 22 2 30 11 31 41 3 20 36 19 23 5 14 44 4 45 1335 8 24 40 7 28 43 16 27 34 6 42 15 26 10 17 9 33 18 25 49 48測試結(jié)果如

4、下（由于太長無法完全截圖，只能粘貼）：請輸入火車車廂的個數(shù)：50請輸入火車車廂次序（中間有間隔）：46 47 50 38 32 29 21 39 1 37 12 22 2 30 11 31 41 3 20 36 19 23 5 14 44 4 45 1335 8 24 40 7 28 43 16 27 34 6 42 15 26 10 17 9 33 18 25 49 48將第46車廂移動到緩沖軌道1將第47車廂移動到緩沖軌道2將第50車廂移動到緩沖軌道3將第38車廂移動到緩沖軌道1將第32車廂移動到緩沖軌道1將第29車廂移動到緩沖軌道1將第21車廂移動到緩沖軌道1將第39車廂移動到緩沖軌道2

5、將第1車廂從入站軌道移動到出站軌道將第37車廂移動到緩沖軌道2將第12車廂移動到緩沖軌道1將第22車廂移動到緩沖軌道2將第2車廂從入站軌道移動到出站軌道將第30車廂移動到緩沖軌道3將第11車廂移動到緩沖軌道1將第31車廂移動到緩沖軌道4將第41車廂移動到緩沖軌道5將第3車廂從入站軌道移動到出站軌道將第20車廂移動到緩沖軌道2將第36車廂移動到緩沖軌道5將第19車廂移動到緩沖軌道2將第23車廂移動到緩沖軌道3將第5車廂移動到緩沖軌道1將第14車廂移動到緩沖軌道2將第44車廂移動到緩沖軌道6將第4車廂從入站軌道移動到出站軌道將第45車廂移動到緩沖軌道7將第5車廂從緩沖軌道1移動到出站軌道將第13車

6、廂移動到緩沖軌道2將第35車廂移動到緩沖軌道5將第8車廂移動到緩沖軌道1將第24車廂移動到緩沖軌道4將第40車廂移動到緩沖軌道6將第7車廂移動到緩沖軌道1將第28車廂移動到緩沖軌道5將第43車廂移動到緩沖軌道7將第16車廂移動到緩沖軌道3將第27車廂移動到緩沖軌道5將第34車廂移動到緩沖軌道6將第6車廂從入站軌道移動到出站軌道將第42車廂移動到緩沖軌道7將第7車廂從緩沖軌道1移動到出站軌道將第15車廂移動到緩沖軌道3將第8車廂從緩沖軌道1移動到出站軌道將第26車廂移動到緩沖軌道5將第10車廂移動到緩沖軌道1將第17車廂移動到緩沖軌道4將第9車廂從入站軌道移動到出站軌道將第33車廂移動到緩沖軌道

7、6將第10車廂從緩沖軌道1移動到出站軌道將第18車廂移動到緩沖軌道5將第11車廂從緩沖軌道1移動到出站軌道將第25車廂移動到緩沖軌道6將第12車廂從緩沖軌道1移動到出站軌道將第49車廂移動到緩沖軌道8將第13車廂從緩沖軌道2移動到出站軌道將第48車廂移動到緩沖軌道8將第14車廂從緩沖軌道2移動到出站軌道將第15車廂從緩沖軌道3移動到出站軌道將第16車廂從緩沖軌道3移動到出站軌道將第17車廂從緩沖軌道4移動到出站軌道將第18車廂從緩沖軌道5移動到出站軌道將第19車廂從緩沖軌道2移動到出站軌道將第20車廂從緩沖軌道2移動到出站軌道將第21車廂從緩沖軌道1移動到出站軌道將第22車廂從緩沖軌道2移動到

8、出站軌道將第23車廂從緩沖軌道3移動到出站軌道將第24車廂從緩沖軌道4移動到出站軌道將第25車廂從緩沖軌道6移動到出站軌道將第26車廂從緩沖軌道5移動到出站軌道將第27車廂從緩沖軌道5移動到出站軌道將第28車廂從緩沖軌道5移動到出站軌道將第29車廂從緩沖軌道1移動到出站軌道將第30車廂從緩沖軌道3移動到出站軌道將第31車廂從緩沖軌道4移動到出站軌道將第32車廂從緩沖軌道1移動到出站軌道將第33車廂從緩沖軌道6移動到出站軌道將第34車廂從緩沖軌道6移動到出站軌道將第35車廂從緩沖軌道5移動到出站軌道將第36車廂從緩沖軌道5移動到出站軌道將第37車廂從緩沖軌道2移動到出站軌道將第38車廂從緩沖軌道

9、1移動到出站軌道將第39車廂從緩沖軌道2移動到出站軌道將第40車廂從緩沖軌道6移動到出站軌道將第41車廂從緩沖軌道5移動到出站軌道將第42車廂從緩沖軌道7移動到出站軌道將第43車廂從緩沖軌道7移動到出站軌道將第44車廂從緩沖軌道6移動到出站軌道將第45車廂從緩沖軌道7移動到出站軌道將第46車廂從緩沖軌道1移動到出站軌道將第47車廂從緩沖軌道2移動到出站軌道將第48車廂從緩沖軌道8移動到出站軌道將第49車廂從緩沖軌道8移動到出站軌道將第50車廂從緩沖軌道3移動到出站軌道共用8個緩沖軌道結(jié)果分析：本程序可對少于100個任意次序車廂的火車進行調(diào)度。進行多次亂序重排，實驗程序均成功運行，且結(jié)果全部與人

10、工計算相符合，實驗程序滿足實驗要求?！痉止ぁ⒇暙I%、自我評分】王金頂：算法設(shè)計，主程序，調(diào)試，實驗報告 34% 100分王帆：算法設(shè)計，棧程序，測試，實驗報告 33% 100分張宇航：算法設(shè)計，流程圖設(shè)計，實驗報告 33% 100分【項目總結(jié)】本次題目較為簡單，考察了我們對棧的學習與理解情況，同時也讓我們復習了類的相關(guān)知識。大家都為終于能夠解決實際問題而感到開心。在算法設(shè)計中也遇到了很多問題，如我們發(fā)現(xiàn)標準庫中的棧占用內(nèi)存過大，因此導致程序在處理車廂數(shù)很大時經(jīng)常崩潰。因此我們自己寫了一個簡單的棧，節(jié)省了大量內(nèi)存，因此能夠處理更加復雜的問題。我們也增加了好幾處錯誤處理代碼，增加了程序的容錯性。如

11、棧滿、?？宅F(xiàn)象等。但是該程序在處理不連續(xù)序列時會出現(xiàn)問題，這也是我們一直在改進的地方，但是輸出一直不穩(wěn)定，有時正確有時錯誤，因此在程序清單中刪除了這一部分?？傮w而言，本次的實驗讓我們對自己有了更大的信心。【程序清單】1.stack.h/*文件名：stack.h作用：棧的類定義*/#ifndef STACK_H#define STACK_Hconst int maxstack=25;class Stackpublic:Stack();bool empty() const;bool full() const;int top() const;void push(int item);void pop(

12、);private:int count;int entrymaxstack;#endif2.stack.cpp/*文件名：stack.cpp作用：棧的類成員函數(shù)的實現(xiàn) */#include<iostream>#include"stack.h"using namespace std;void Stack:push(int item)if (count<maxstack)entrycount+=item;void Stack:pop()if (count>0)-count;int Stack:top() constif (count>0)retur

13、n entrycount-1;else return 0;bool Stack:empty() constif(count>0) return false;return true;bool Stack:full() constif(count=maxstack) return true;return false;Stack:Stack()count=0;3.train.cpp/*文件名：train.cpp作用：主程序*/#include<iostream>#include"stack.h"using namespace std;int main()int

14、n, now_out=1;int stack_count=0;cout<<"請輸入火車車廂的個數(shù)：" <<endl; /輸入數(shù)據(jù)并儲存cin>>n;int arrayn;cout<<"請輸入火車車廂次序（中間有間隔）："<<endl;for (int i=0; i<n; i+)cin>>arrayi;/輸入部分Stack stack_array100;for (int i=0; i<n; i+)if (arrayi=now_out) /判斷當前車廂數(shù)是否恰好滿足輸出條件c

15、out<<"將第"<<now_out<<"車廂從入站軌道移動到出站軌道"<<endl; /如果滿足直接輸出now_out+;continue;else /不滿足則將數(shù)壓入合適的棧 for (int j=0; j<stack_count+1; j+)if (stack_arrayj.empty() cout<<"將第"<<arrayi<<"車廂移動到緩沖軌道"<<j+1<<endl; stack_arra

16、yj.push(arrayi); if (j=stack_count) stack_count+; break; else if (stack_arrayj.full() /棧滿時另找新棧 continue; else if(arrayi<stack_arrayj.top() cout<<"將第"<<arrayi<<"車廂移動到緩沖軌道"<<j+1<<endl; stack_arrayj.push(arrayi); break; else ;for (int s=0; s<stack

17、_count; s+)/遍歷各個棧頂是否有滿足輸出條件的數(shù) if (stack_arrays.top()=now_out)cout<<"將第"<<now_out<<"車廂從緩沖軌道"<<s+1<<"移動到出站軌道"<<endl;stack_arrays.pop();now_out+;break;for (int m=now_out; now_out<=n; m+)for (int s=0; s<stack_count; s+)/遍歷各個棧頂是否有滿足輸出條件的數(shù) if (stack_arr