課程設(shè)計(jì)內(nèi)容

1、算法設(shè)計(jì)與分析課程設(shè)計(jì)內(nèi)容1 .馬的Hamilton周游路線問題問題描述：8 x 8的國際象棋棋盤上的一只馬，恰好走過除起點(diǎn)外的其他63個(gè)位置各一 次，最后回到起點(diǎn)。這條路線稱為馬的Hamilton周游路線。對(duì)于給定的m x n的國際象棋棋 盤，m和n均為大于5的偶數(shù)，且m - nk 2，試設(shè)計(jì)一個(gè)分治算法找出馬的一條Hamilton 周游路線。設(shè)計(jì)任務(wù)：對(duì)于給定的偶數(shù)m，n 6且Im - n| 2，設(shè)計(jì)算法并驗(yàn)證算法的正確性， 編程計(jì)算m x n的國際象棋棋盤上馬的一條Hamilton周游路線。設(shè)計(jì)要求：程序運(yùn)行結(jié)束時(shí)，將計(jì)算出的馬的Hamilton周游路線用下面的2種表達(dá)方 式輸出。第一種

2、表達(dá)方式按照馬步的次序給出馬的Hamilton周游路線。馬的每一步用所在的方 格坐標(biāo)（x, y）來表示，X表示行坐標(biāo)，編號(hào)為0,1,，m - 1 ； y表示列坐標(biāo)，編號(hào)為0,1,，n -1。起始方格為（0,0）。第二種表達(dá)方式在棋盤的方格中標(biāo)明馬到達(dá)該方格的步數(shù)。（0,0）方格為起跳步，并標(biāo) 明為第1步。排列的字典序問題問題描述：n個(gè)元素1,2,., n有n!個(gè)不同的排列。將這n!個(gè)排列按字典序排列，并 編號(hào)為0,1,., n !-1。每個(gè)排列的編號(hào)為其字典序列。例如，* = 3時(shí)，6個(gè)不同排列的字 典序值如下：字典序列012345排列123132213231312321設(shè)計(jì)任務(wù)：給定n以及n

3、個(gè)元素1,2,., n的一個(gè)排列，計(jì)算出這個(gè)排列的字典序值， 以及按字典序排列的下一個(gè)排列。圈乘運(yùn)算問題問題描述：對(duì)于給定的十進(jìn)制整數(shù)X和K，由X和運(yùn)算可以組成各種不同的表達(dá) 式。試設(shè)計(jì)一個(gè)算法，計(jì)算出由X和運(yùn)算組成的值為K的表達(dá)式最少需用多少個(gè)運(yùn)算。關(guān)于整數(shù)的二元圈乘運(yùn)算定義為：（XY ）=十進(jìn)制整數(shù)X的各位數(shù)字之和x十進(jìn)制整數(shù)Y的最大數(shù)字+ Y的最小數(shù)字例如：（9 30 ）= 9 x 3 + 0設(shè)計(jì)任務(wù)：對(duì)于給定的十進(jìn)制整數(shù)設(shè)計(jì)任務(wù)：對(duì)于給定的十進(jìn)制整數(shù)X和K，1 X , K 10 20，試設(shè)計(jì)一個(gè)有效算法，編程計(jì)算由X和運(yùn)算組成的值為K的表達(dá)式最少需用多少個(gè)運(yùn)算。有向樹k中值問題問題描述

4、：給定一棵有向樹T，樹T中每個(gè)頂點(diǎn)u都有一個(gè)權(quán)叭u ），樹的每條邊（u , v） 也都有一個(gè)非負(fù)邊長d （u , v）。有向樹T的每個(gè)頂點(diǎn)u可以看作客戶，其服務(wù)需求量為叭u ）。 每條邊（u , v）的邊長d （u , v）可以看作運(yùn)輸費(fèi)用。如果在頂點(diǎn)u處未設(shè)置服務(wù)機(jī)構(gòu)，則將頂點(diǎn) u處的服務(wù)需求沿有向樹的邊（u , v）轉(zhuǎn)移到頂點(diǎn)v處服務(wù)機(jī)構(gòu)需付出的服務(wù)轉(zhuǎn)移費(fèi)用為 叭u ） . d （u , v）。樹根處已設(shè)置了服務(wù)機(jī)構(gòu)，現(xiàn)在要在樹T中增設(shè)k處服務(wù)機(jī)構(gòu)，使得整棵 樹T的服務(wù)轉(zhuǎn)移費(fèi)用最小。設(shè)計(jì)任務(wù)：對(duì)于給定的有向樹T，試設(shè)計(jì)一個(gè)有效算法，編程計(jì)算在樹T中增設(shè)k處服 務(wù)機(jī)構(gòu)的服務(wù)轉(zhuǎn)移費(fèi)用最小。套匯

5、問題問題描述:套匯是指利用貨幣兌換率的差異將一個(gè)單位的某種貨幣轉(zhuǎn)換為大于一個(gè)單位 的同種貨幣。例如，假定1美元可以買0.7英鎊，1英鎊可以買9.5法郎，且1法郎可以買到 0.16美元。通過貨幣兌換，一個(gè)商人可以從1美元開始買入，得到0.7 x 9.5 x 0.16 = 1.064 美元，從而獲得6.4%的利潤。設(shè)計(jì)任務(wù)：對(duì)于n種貨幣c 1, C2,., c的有關(guān)兌換率，試設(shè)計(jì)一個(gè)有效算法，用以確定 是否存在套匯的可能性。非單位時(shí)間任務(wù)安排問題問題描述：具有截止時(shí)間和誤時(shí)懲罰的任務(wù)安排問題要描述如下。（1）給定n個(gè)任務(wù)的集合S = 1,2, . , n；（2）完成任務(wù)z需要t時(shí)間，1 i n ；

6、（3）任務(wù)i的截止時(shí)間d，1 i n，即要求任務(wù)i在時(shí)間d之前結(jié)束；（4）任務(wù)i的誤時(shí)懲罰w，1 i n，即任務(wù)i未在時(shí)間dZ前結(jié)束將招致w的懲罰; 若按時(shí)完成則無懲罰。任務(wù)安排問題要求確定S的一個(gè)時(shí)間表（最優(yōu)時(shí)間表）使得總誤時(shí)懲罰達(dá)到最小。設(shè)計(jì)任務(wù)：給定的n個(gè)任務(wù)，編程計(jì)算總誤時(shí)懲罰最小的最優(yōu)時(shí)間表。運(yùn)動(dòng)員最佳配對(duì)問題問題描述：羽毛球隊(duì)有男女運(yùn)動(dòng)員各n人。給定2個(gè)n x n矩陣P和Q。P z j是男 運(yùn)動(dòng)員Z和女運(yùn)動(dòng)員j配對(duì)組成混合雙打的男運(yùn)動(dòng)員競(jìng)賽優(yōu)勢(shì)；Q i j是女運(yùn)動(dòng)員j和男 運(yùn)動(dòng)員Z配對(duì)組成混合雙打的女運(yùn)動(dòng)員競(jìng)賽優(yōu)勢(shì)。由于技術(shù)配合和心理狀態(tài)等各種因素影 響，P i j不一定等于Q i

7、 j。男運(yùn)動(dòng)員i和女運(yùn)動(dòng)員j配對(duì)組成混合雙打的男女雙方競(jìng) 賽優(yōu)勢(shì)為P i j * Q i j。設(shè)計(jì)一個(gè)算法，計(jì)算男女運(yùn)動(dòng)員最佳配對(duì)法，使各組男女雙方 競(jìng)賽優(yōu)勢(shì)的總和達(dá)到最大。設(shè)計(jì)任務(wù)：設(shè)計(jì)一個(gè)算法，對(duì)于給定的男女運(yùn)動(dòng)員競(jìng)賽優(yōu)勢(shì)，計(jì)算男女運(yùn)動(dòng)員最佳配對(duì) 法，使各組男女雙方競(jìng)賽優(yōu)勢(shì)的總和達(dá)到最大。n色方柱問題問題描述：設(shè)有n個(gè)立方體，每個(gè)立方體的每一面用紅、黃、藍(lán)、綠等n種顏色之一染 色。要把這n個(gè)立方體疊成一個(gè)方形柱體，使得柱體的4個(gè)側(cè)面的每一側(cè)均有n種不同的顏 色。試設(shè)計(jì)一個(gè)回溯算法，計(jì)算出n個(gè)立方體的一種滿足要求的重疊方案。設(shè)計(jì)任務(wù)：對(duì)于給定的n個(gè)立方體以及每個(gè)立方體各面的顏色，計(jì)算出n個(gè)立方體的一 種疊置方案，使得柱體的4個(gè)側(cè)面的每一側(cè)均有n種不同的顏色。最小權(quán)頂點(diǎn)覆蓋問題問題描述：給定一個(gè)賦權(quán)無向圖G = (V , E )，每個(gè)頂點(diǎn)v e V都有一個(gè)權(quán)值w3)。如果U c V，且對(duì)任意(u , v) e E有v e U，就稱U為圖G的一個(gè)頂點(diǎn)覆蓋。G的最小權(quán)頂 點(diǎn)覆蓋是指G中所含頂點(diǎn)權(quán)之和最小的頂點(diǎn)覆蓋。設(shè)計(jì)任務(wù)：對(duì)于給定一個(gè)賦權(quán)無向圖G = (V , E )，設(shè)計(jì)一個(gè)優(yōu)先隊(duì)列式分支限界法， 計(jì)算G的最小權(quán)頂點(diǎn)覆蓋。行列變換問題問題描述:給定2個(gè)m x n方格陣列組成的圖形A和每個(gè)方格的顏色為黑色或白色。 行列變換問