【正文】 【問題描述】 設(shè)計一個國際象棋的馬踏遍棋盤的演示程序。【基本要求】將馬隨機(jī)放在國際象棋的88棋盤Board[8][8]的某個方格中，馬按走棋規(guī)則進(jìn)行移動。要求每個方格只進(jìn)入一次，走遍棋盤上全部64個方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，…，64依次填入一個88的方陣，輸出之。4. 算術(shù)表達(dá)式求值演示【問題描述】表達(dá)式計算是實(shí)現(xiàn)程序設(shè)計語言的基本問題之一，也是棧的應(yīng)用的一個典型例子。設(shè)計一個程序，演示用算符優(yōu)先法對算術(shù)表達(dá)式求值的過程?！净疽蟆恳宰址蛄械男问綇慕K端輸入語法正確的、不含變量的整數(shù)表達(dá)式。，實(shí)現(xiàn)對算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教科書的例31演示在求值中運(yùn)算符械、運(yùn)算數(shù)校、輸入字符和主要操作的變化過程。5. 銀行業(yè)務(wù)模擬【問題描述】客戶業(yè)務(wù)分為兩種。第一種是申請從銀行得到一筆資金，即取款或借款。第二種是向銀行投入一筆資金，即存款或還款。銀行有兩個服務(wù)窗口，相應(yīng)地有兩個隊列?？蛻舻竭_(dá)銀行后先排第一個隊。處理每個客戶業(yè)務(wù)時，如果屬于第一種，且申請額超出銀行現(xiàn)存資金總額而得不到滿足，則立刻排入第二個隊等候，直至滿足時才離開銀行；否則業(yè)務(wù)處理完后立刻離開銀行。每接待完一個第二種業(yè)務(wù)的客戶，則順序檢查和處理(如果可能)第二個隊列中的客戶，對能滿足的申請者予以滿足，不能滿足者重新排到第二個隊列的隊尾。注意，在此檢查過程中，一旦銀行資金總額少于或等于剛才第一個隊列中最后一個客戶(第二種業(yè)務(wù))被接待之前的數(shù)額，或者本次已將第二個隊列檢查或處理了一遍，就停止檢查(因?yàn)榇藭r已不可能還有能滿足者)轉(zhuǎn)而繼續(xù)接待第一個隊列的客戶。任何時刻都只開一個窗口。假設(shè)檢查不需要時間。營業(yè)時間結(jié)束時所有客戶立即離開銀行。寫一個上述銀行業(yè)務(wù)的事件驅(qū)動模擬系統(tǒng)，通過模擬方法求出客戶在銀行內(nèi)逗留的平均時間。【基本要求】利用動態(tài)存儲結(jié)構(gòu)實(shí)現(xiàn)模擬?！緶y試數(shù)據(jù)】 一天營業(yè)開始時銀行擁有的款額為10000(元)，營業(yè)時間為600(分鐘)。其他模擬參量自定，注意測定兩種極端的情況：一是兩個到達(dá)事件之間的間隔時間很短，而客戶的交易時間很長，另一個恰好相反，設(shè)置兩個到達(dá)事件的間隔時間很長，而客戶的交易時間很短?！緦?shí)現(xiàn)提示】事件有兩類：到達(dá)銀行和離開銀行。初始時銀行現(xiàn)存資金總額為total。開始營業(yè)后的第一今事件是客戶到達(dá)，營業(yè)時間從0到closetime。到達(dá)事件發(fā)生時隨機(jī)地設(shè)置此客戶的交易時間和距下一到達(dá)事件之間的時間間隔。每個客戶要辦理的款額也是隨機(jī)確定的，用負(fù)值和正值分別表示第一類和第二類業(yè)務(wù)。變量total，closetime以及上述兩個隨機(jī)量的上下界均交互地從終端讀入，作為模擬參數(shù)。兩個隊列和一個事件表均要用動態(tài)存儲結(jié)構(gòu)實(shí)現(xiàn)。注意弄清應(yīng)該在什么條件下設(shè)置離開事件，以及第二個隊列用怎樣的存儲結(jié)構(gòu)實(shí)現(xiàn)時可以獲得較高的效率。注意：事件表是按時間順序有序的?！具x作內(nèi)容】自己實(shí)現(xiàn)動態(tài)數(shù)據(jù)類型。例如對于客戶結(jié)點(diǎn)，定義pool為CustNodepoolfMAX]；// 結(jié)構(gòu)類型CustNode含四個域：aITHIne，durtime，amount，next或者定義四個同樣長的，以上述域名為名字的數(shù)組。初始時，將所有分量的next域鏈接起來，形成一個靜態(tài)鏈找，設(shè)置一個樓頂元素下標(biāo)指示量top，top=0表示找空。動態(tài)存儲分配函數(shù)可以取名為myMalloc，其作用是出錢，將錢頂元素的下標(biāo)返回。若返回的值為0，則表示無空間可分配。歸還函數(shù)可取名為myFree，其作用是把該分量入錢。用FORTRAN和BASIC等語言實(shí)現(xiàn)時只能如此地自行組織。6. 航空客運(yùn)訂票系統(tǒng)【問題描述】航空客運(yùn)訂票的業(yè)務(wù)活動包括：查詢航線、客票預(yù)訂和辦理退票等。試設(shè)計一個航空客運(yùn)訂票系統(tǒng)，以使上述業(yè)務(wù)可以借助計算機(jī)來完成?！净疽蟆?1)每條航線所涉及的信息有：終點(diǎn)站名、航班號、飛機(jī)號、飛行周日(星期幾)、乘員定額、余票量、已訂票的客戶名單(包括姓名、訂票量、艙位等級1，2或3)以及等候替補(bǔ)的客戶名單(包括姓名、所需票量)；(2)作為示意系統(tǒng)，全部數(shù)據(jù)可以只放在內(nèi)存中；(3)系統(tǒng)能實(shí)現(xiàn)的操作和功能如下：①查詢航線：根據(jù)旅客提出的終點(diǎn)站名輸出下列信息：航班號、飛機(jī)號、星期幾飛行，最近一天航班的日期和余票額；②承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求(航班號、訂票數(shù)額)查詢該航班票額情況，若尚有余票，則為客戶辦理訂票手續(xù)，輸出座位號；若已滿員或余票額少于訂票額，則需重新詢問客戶要求。若需要，可登記排隊候補(bǔ)；③承辦退票業(yè)務(wù)：根據(jù)客戶提供的情況(日期、航班)，為客戶辦理退票手續(xù)，然后查詢該航班是否有人排隊候補(bǔ)，首先詢問排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問其他排隊候補(bǔ)的客戶。【測試數(shù)據(jù)】由讀者自行指定?！緦?shí)現(xiàn)提示】兩個客戶名單可分別由線性表和隊列實(shí)現(xiàn)。為查找方便，已訂票客戶的線性表應(yīng)按客戶姓名有序，并且，為插入和刪除方便，應(yīng)以鏈表作存儲結(jié)構(gòu)。由于預(yù)約人數(shù)無法預(yù)計，隊列也應(yīng)以鏈表作存儲結(jié)構(gòu)。整個系統(tǒng)需匯總各條航線的情況登錄在一張線性表上，由于航線基本不變，可采用順序存儲結(jié)構(gòu)，并按航班有序或按終點(diǎn)站名有序。每條航線是這張表上的一個記錄，包含上述8個域、其中乘員名單域?yàn)橹赶虺藛T名單鏈表的頭指針，等候替補(bǔ)的客戶名單域?yàn)榉謩e指向隊頭和隊尾的指針。【選作內(nèi)容】當(dāng)客戶訂票要求不能滿足時，系統(tǒng)可向客戶提供到達(dá)同一目的地的其他航線情況。讀者還可充分發(fā)揮自己的想象力，增加你的系統(tǒng)的功能和其他服務(wù)項(xiàng)目。7. 電梯模擬【問題描述】設(shè)計一個電梯模擬系統(tǒng)。這是一個離散的模擬程序，因?yàn)殡娞菹到y(tǒng)是乘客和電梯等“活動體“構(gòu)成的集合，雖然他們彼此交互作用，但他們的行為是基本獨(dú)立的。在離散的模擬中，以模擬時鐘決定每個活動體的動作發(fā)生的時刻和順序，系統(tǒng)在某個模擬瞬間處理有待完成的各種事情，然后把模擬時鐘推進(jìn)到某個動作預(yù)定要發(fā)生的下一個時刻?！净疽蟆?1) 模擬某校五層教學(xué)樓的電梯系統(tǒng)。該樓有一個自動電梯，能在每層停留。五個樓層由下至上依次稱為地下層、第→層、第二層、第三層和第四層，其中第一層是大樓的迸出層，即是電梯的“本壘層“，電梯“空閑“時，將來到該層候命。 (2) 乘客可隨機(jī)地進(jìn)出于任何層。對每個人來說，他有一個能容忍的最長等待時間，一旦等候電梯時間過長，他將放棄。 (3) 模擬時鐘從0開始。人和電梯的各種動作均要耗費(fèi)一定的時間單位(簡記為t)，比如：有人進(jìn)出時，電梯每隔40t測試一次，若無人進(jìn)出，則關(guān)門；關(guān)門和開門各需要20tg每個人進(jìn)出電梯均需要25h如果電梯在某層靜止時間超過300t，則駛回1層候命。(4) 按時序顯示系統(tǒng)狀態(tài)的變化過程：發(fā)生的全部人和電梯的動作序列?！緶y試數(shù)據(jù)】 模擬時鐘Time的初值為0，終值可在500~10000范圍內(nèi)逐步增加?！緦?shí)現(xiàn)提示】(1)樓層由下至上依次編號為0，1，2，3，4。每層有要求Up(上)和Down(下〉的兩個按鈕，對應(yīng)10個變量CaliUp[0..4]和CallDOWEl[0..4]。電梯內(nèi)5個目標(biāo)層按鈕對應(yīng)變量Caucar[0..4]。有人按下某個按鈕時，相應(yīng)的變量就置為1，一旦要求滿足后，電梯就把該變量清為0。(2)電梯處于三種狀態(tài)之zGoingUp(上行)、GoingDown(下行)和Idle(停候)。如果電梯處于Idle狀態(tài)且不在1層，則關(guān)門并駛回1層。在1層停候時，電梯是閉門候命。一旦收到往另一層的命令，就轉(zhuǎn)入GoingUp或GoingDown狀態(tài)，執(zhí)行相應(yīng)的操作。 (3)用變量Time表示模擬時鐘，初值為0，時間單位。)為0。l秒。其他重要的變量有：Floor ——電梯的當(dāng)前位置(樓層)；DI ——值為0，除非人們正在進(jìn)入和離開電梯；D2 ——值為0，如果電梯已經(jīng)在某層停候30Ot以上；D3 ——值為0，除非電梯門正開著又無人迸出電梯；State ——電梯的當(dāng)前狀態(tài)(GoingUp，GoingDOWEl，Idle)。系統(tǒng)初始時，F(xiàn)loor=1，Dl=D2=D3=0，State=Idle。(4)每個人從進(jìn)入系統(tǒng)到離開稱為該人在系統(tǒng)中的存在周期。在此周期內(nèi)，他有6種可能發(fā)生的動作：M1. [進(jìn)入系統(tǒng)，為下一人的出現(xiàn)作準(zhǔn)備]產(chǎn)生以下數(shù)值：InFloor ——該人進(jìn)入哪層樓；011tFloor ——他要去哪層樓；GiveupTime ——他能容忍的等候時間；InterTime ——下一人出現(xiàn)的時間間隔，據(jù)此系統(tǒng)預(yù)置下一人進(jìn)入系統(tǒng)的時刻。M2. [按電鈕并等候]此時應(yīng)對以下不同情況作不同的處理：①Floor=InFloor且電梯的下一個活動是E6(電梯在本層，但正在關(guān)門〉；②Floor=InFloor且D3手0(電梯在本層，正有人迸出)；③其他情況，可能D2=0或電梯處于活動El(在1層停候)。M3. [進(jìn)入排隊]在等候隊列Queue[InFloor]末尾插入該人，并預(yù)置在GiveupTime個t之后，他若仍在隊列中將實(shí)施動作M4。 M4. [放棄]如果Floor手InFloor或Dl=0，則從Quem[InFloor]和系統(tǒng)刪除該人。如果Floor=InFloor且D1學(xué)0，他就繼續(xù)等候(他知道馬上就可進(jìn)入電梯〉。 M5. [進(jìn)入電梯]從Queue[InFloor〕刪除該人，并把他插入到lElevator(電梯)校中。置Cancar[011tFloor]為1。 M6. [離去]從Elevator和系統(tǒng)刪除該人。 (5)電梯的活動有9種：E1. [在1層停候]若有人按下一個按鈕，則調(diào)用Controler將電梯轉(zhuǎn)入活動E3或E60。E2. [要改變狀態(tài)?]如果電梯處于GoingUp(或GoingDown〉狀態(tài)，但該方向的樓層卻無人等待，則要看反方向樓層是否有人等候，而決定置State為GoingDown(或GoingUp〉還是Idle。E3. [開門]置DI和D2為非0值，預(yù)置300個t后啟動活動E9和76個t后啟動E5，然后預(yù)置20個t后轉(zhuǎn)到目。E4. [讓人出入]如果Elevator不空且有人的011tFloor=Floor，則按進(jìn)入的倒序每隔25個t讓這類人立即轉(zhuǎn)到他們的動作M6。Elevator中不再有要離開的人時，如果Queue[Floor]不空，則以25個t的速度讓他們依次轉(zhuǎn)到MLQueue[Floor]空時，置Dl為0，D3手0，而且等候某個其他活動的到來。E5. [關(guān)門]每隔40個t檢查D1，直到是D1=O(若D1手0，則仍有人出入〉。置D3為0并預(yù)置電梯再20個t后啟動活動E6(再關(guān)門期間，若有人到來，則如M2所述，門再次打開)。E6. [準(zhǔn)備移動]置Caucar[Floor]為0，而且若State手GoingDown，則置CallUPCFloor]為05若State手GoingUp，則置CallDownCFloor]為0。調(diào)用Controler函數(shù)。如果State=Idle，則即使已經(jīng)執(zhí)行了Controler，也轉(zhuǎn)到E1。否則，如果D2手0，則取消電梯活動E9。最后，如果State=GoingUp，則預(yù)置15個t后(電梯加速〉轉(zhuǎn)到E7；如果State=GoingDown，則預(yù)置15個t后(電梯加速)轉(zhuǎn)到E8。E7. [上升一層]置Floor加1并等候51個人如果現(xiàn)在Caucar[Floor〕=1或CallUp[Floor]=1，或者如果((Floor=1或CallDOWEl[Floor]=1)且CallUp[j]=CallDOWEl[j]=CallCar0]=0對于所有jFloor)，則預(yù)置14個t后(減速)轉(zhuǎn)到E2；否則重復(fù)E7。 E8. [下降一層]除了方向相反之外，與E7類似，但那里的51和14個t，此時分別改為61和23個t(電梯下降比上升慢)。 E9. [置不活動指示器]置D2為0并調(diào)用Controler函數(shù)(E9是由E3預(yù)置的，但幾乎總是被E6取消了訓(xùn)。 (6)當(dāng)電梯須對下一個方向作出判定時，便在若干臨界時刻調(diào)用Controler函數(shù)。該 函數(shù)有以下要點(diǎn)： C1. [需要判斷?]若State手Idle，則返回。 C2. [應(yīng)該開門?]如果電梯處于E1且CallUp[1]，CallDown[1]或Caucar[1]非0，則預(yù)置20個t后啟動E3，并返回。C3. [有按鈕按下?]找最小的j手Floor，使得CallUp[j]，CallDOWEl〔j]或Caucar[j]非0，并轉(zhuǎn)到C4。但如果不存在這樣的j，那么，如果Controler正為E6所調(diào)用，則置j為1，否則返回。 C4. [置State]如果Floorj，則置State為GoingDOWEl；如果Floorj，則置State為GoingUp。 C5. [電梯靜止?]如果電梯處于E1而且j手1，則預(yù)置20個t后啟動E6。返回。 (7)由上可見，關(guān)鍵是按時序管理系統(tǒng)中所有乘客和電梯的動作設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)。【選作內(nèi)容】(l) 增加電梯數(shù)量，模擬多梯系統(tǒng)。 (2) 某高校的一座30層住宅樓有三部自動電梯，每梯最多載客15人。大樓每層8戶，每戶平均3。5人，每天早晨平均每戶有3人必須在7時之前離開大樓去上班或上學(xué)。模擬該電梯系統(tǒng)，并分析分別在一梯、二梯和三梯運(yùn)行情況下，下樓高峰期間各層的住戶應(yīng)提前多少時間候梯下樓?研究多梯運(yùn)行最佳策略。8. 迷宮問題 【問題描述】以一個mn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論?！净疽蟆渴紫葘?shí)現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的錢類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組(i，j，d)的形式輸出，其中：(i，j)指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為z(1，1，1)，(1，2，2)，(2，2，2)，(3，2，3)，(3，1，2)，【測