課程設計內容

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和每個方格的顏色為黑色或白色。 行列變換問