



下載本文檔
版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、算法設計與分析課程設計內容1 .馬的Hamilton周游路線問題問題描述:8 x 8的國際象棋棋盤上的一只馬,恰好走過除起點外的其他63個位置各一 次,最后回到起點。這條路線稱為馬的Hamilton周游路線。對于給定的m x n的國際象棋棋 盤,m和n均為大于5的偶數(shù),且m - nk 2,試設計一個分治算法找出馬的一條Hamilton 周游路線。設計任務:對于給定的偶數(shù)m,n 6且Im - n| 2,設計算法并驗證算法的正確性, 編程計算m x n的國際象棋棋盤上馬的一條Hamilton周游路線。設計要求:程序運行結束時,將計算出的馬的Hamilton周游路線用下面的2種表達方 式輸出。第一種
2、表達方式按照馬步的次序給出馬的Hamilton周游路線。馬的每一步用所在的方 格坐標(x, y)來表示,X表示行坐標,編號為0,1,,m - 1 ; y表示列坐標,編號為0,1,,n -1。起始方格為(0,0)。第二種表達方式在棋盤的方格中標明馬到達該方格的步數(shù)。(0,0)方格為起跳步,并標 明為第1步。排列的字典序問題問題描述:n個元素1,2,., n有n!個不同的排列。將這n!個排列按字典序排列,并 編號為0,1,., n !-1。每個排列的編號為其字典序列。例如,* = 3時,6個不同排列的字 典序值如下:字典序列012345排列123132213231312321設計任務:給定n以及n
3、個元素1,2,., n的一個排列,計算出這個排列的字典序值, 以及按字典序排列的下一個排列。圈乘運算問題問題描述:對于給定的十進制整數(shù)X和K,由X和運算可以組成各種不同的表達 式。試設計一個算法,計算出由X和運算組成的值為K的表達式最少需用多少個運算。關于整數(shù)的二元圈乘運算定義為:(XY )=十進制整數(shù)X的各位數(shù)字之和x十進制整數(shù)Y的最大數(shù)字+ Y的最小數(shù)字例如:(9 30 )= 9 x 3 + 0設計任務:對于給定的十進制整數(shù)設計任務:對于給定的十進制整數(shù)X和K,1 X , K 10 20,試設計一個有效算法,編程計算由X和運算組成的值為K的表達式最少需用多少個運算。有向樹k中值問題問題描述
4、:給定一棵有向樹T,樹T中每個頂點u都有一個權叭u ),樹的每條邊(u , v) 也都有一個非負邊長d (u , v)。有向樹T的每個頂點u可以看作客戶,其服務需求量為叭u )。 每條邊(u , v)的邊長d (u , v)可以看作運輸費用。如果在頂點u處未設置服務機構,則將頂點 u處的服務需求沿有向樹的邊(u , v)轉移到頂點v處服務機構需付出的服務轉移費用為 叭u ) . d (u , v)。樹根處已設置了服務機構,現(xiàn)在要在樹T中增設k處服務機構,使得整棵 樹T的服務轉移費用最小。設計任務:對于給定的有向樹T,試設計一個有效算法,編程計算在樹T中增設k處服 務機構的服務轉移費用最小。套匯
5、問題問題描述:套匯是指利用貨幣兌換率的差異將一個單位的某種貨幣轉換為大于一個單位 的同種貨幣。例如,假定1美元可以買0.7英鎊,1英鎊可以買9.5法郎,且1法郎可以買到 0.16美元。通過貨幣兌換,一個商人可以從1美元開始買入,得到0.7 x 9.5 x 0.16 = 1.064 美元,從而獲得6.4%的利潤。設計任務:對于n種貨幣c 1, C2,., c的有關兌換率,試設計一個有效算法,用以確定 是否存在套匯的可能性。非單位時間任務安排問題問題描述:具有截止時間和誤時懲罰的任務安排問題要描述如下。(1)給定n個任務的集合S = 1,2, . , n;(2)完成任務z需要t時間,1 i n ;
6、(3)任務i的截止時間d,1 i n,即要求任務i在時間d之前結束;(4)任務i的誤時懲罰w,1 i n,即任務i未在時間dZ前結束將招致w的懲罰; 若按時完成則無懲罰。任務安排問題要求確定S的一個時間表(最優(yōu)時間表)使得總誤時懲罰達到最小。設計任務:給定的n個任務,編程計算總誤時懲罰最小的最優(yōu)時間表。運動員最佳配對問題問題描述:羽毛球隊有男女運動員各n人。給定2個n x n矩陣P和Q。P z j是男 運動員Z和女運動員j配對組成混合雙打的男運動員競賽優(yōu)勢;Q i j是女運動員j和男 運動員Z配對組成混合雙打的女運動員競賽優(yōu)勢。由于技術配合和心理狀態(tài)等各種因素影 響,P i j不一定等于Q i
7、 j。男運動員i和女運動員j配對組成混合雙打的男女雙方競 賽優(yōu)勢為P i j * Q i j。設計一個算法,計算男女運動員最佳配對法,使各組男女雙方 競賽優(yōu)勢的總和達到最大。設計任務:設計一個算法,對于給定的男女運動員競賽優(yōu)勢,計算男女運動員最佳配對 法,使各組男女雙方競賽優(yōu)勢的總和達到最大。n色方柱問題問題描述:設有n個立方體,每個立方體的每一面用紅、黃、藍、綠等n種顏色之一染 色。要把這n個立方體疊成一個方形柱體,使得柱體的4個側面的每一側均有n種不同的顏 色。試設計一個回溯算法,計算出n個立方體的一種滿足要求的重疊方案。設計任務:對于給定的n個立方體以及每個立方體各面的顏色,計算出n個立方體的一 種疊置方案,使得柱體的4個側面的每一側均有n種不同的顏色。最小權頂點覆蓋問題問題描述:給定一個賦權無向圖G = (V , E ),每個頂點v e V都有一個權值w3)。如果U c V,且對任意(u , v) e E有v e U,就稱U為圖G的一個頂點覆蓋。G的最小權頂 點覆蓋是指G中所含頂點權之和最小的頂點覆蓋。設計任務:對于給定一個賦權無向圖G = (V , E ),設計一個優(yōu)先隊列式分支限界法, 計算G的最小權頂點覆蓋。行列變換問題問題描述:給定2個m x n方格陣列組成的圖形A和每個方格的顏色為黑色或白色。 行列變換問
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度解除勞動合同通知書及員工離職培訓費用補償合同
- 2025年度新能源車充電設施建設合同終止函模板
- 二零二五年度山場租賃承包與林業(yè)資源保護與管理協(xié)議
- 2025年度飯店客房租賃及管理服務合同
- 二零二五年度魚塘養(yǎng)殖與鄉(xiāng)村旅游綜合開發(fā)合同
- 二零二五年度新能源電動車銷售授權合同
- 二零二五年度勞動合同解除后的員工關系維護與調解協(xié)議
- 二零二五年度企業(yè)內部解雇員工安置與培訓協(xié)議
- 二零二五年度醫(yī)療行業(yè)職工勞動合同終止協(xié)議及醫(yī)療補助
- 二零二五年度房產(chǎn)贈與子女協(xié)議書及子女房產(chǎn)租賃收入分配協(xié)議
- 高中主題班會 復盤-在思考中學習課件-高中上學期主題班會
- 學生創(chuàng)新能力培養(yǎng)方案計劃
- 《西門子PLC應用》一體化教案1-20周全篇
- 新蘇教版一年級科學下冊第一單元第1課《撿石頭》課件
- 2025年湖北省技能高考(建筑技術類)《建筑材料與檢測》模擬練習試題庫(含答案)
- 人行道道鋪設施工方案
- 2025年度模特代言合同隱私條款規(guī)范樣本4篇
- 【歷史】元朝的建立與統(tǒng)一課件 2024-2025學年統(tǒng)編版七年級歷史下冊
- 2025年度游戲工作室游戲客服中心用工合同
- 2024年高州市人民醫(yī)院廣東醫(yī)學院附屬高州醫(yī)院高層次衛(wèi)技人才招聘筆試歷年參考題庫頻考點附帶答案
- 橋梁拆除施工方案及安全措施
評論
0/150
提交評論