單循環(huán)賽中選手勝負(fù)序列求解問題

《單循環(huán)賽中選手勝負(fù)序列求解問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、XX學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告2008～2009學(xué)年第2學(xué)期課程數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)名稱單循環(huán)賽中選手勝負(fù)序列求解問題學(xué)生姓名學(xué)號(hào)專業(yè)班級(jí)指導(dǎo)教師2009年2月題目：?jiǎn)窝h(huán)賽中選手勝負(fù)序列求解問題一、問題分析和任務(wù)定義單循環(huán)賽：　　單循環(huán)賽，是所有參加比賽的隊(duì)均能相遇一次，最后按各隊(duì)在全部比賽中的積分、得失分率排列名次。如果參賽球隊(duì)不多，而且時(shí)間和場(chǎng)地都有保證，通常都采用這種競(jìng)賽方法?！　窝h(huán)比賽輪次的計(jì)算本題可有兩種不同的理解，一個(gè)是按比賽的積分排名產(chǎn)生勝負(fù)序列，第二個(gè)是按比賽過程中各個(gè)選手間的

2、勝負(fù)關(guān)系產(chǎn)生勝負(fù)序列，下面具體分析：（1）按比賽中積分排名產(chǎn)生勝負(fù)序列：比賽可規(guī)定各個(gè)選手之間均遭遇且只遭遇一次，比賽時(shí)勝方得1分，負(fù)方不得分，在比賽結(jié)束時(shí)按積分排名進(jìn)行排序，由此產(chǎn)生勝負(fù)序列關(guān)系。（2）按比賽過程中各個(gè)選手間的勝負(fù)關(guān)系產(chǎn)生勝負(fù)序列：該種方法是以過程中的勝負(fù)為標(biāo)準(zhǔn)從而產(chǎn)生勝負(fù)序列，當(dāng)然，這種勝負(fù)序列很大的可能性是不唯一的，本程序按課程設(shè)計(jì)任務(wù)書的要求，僅求出其中的一個(gè)勝負(fù)序列關(guān)系。二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)(1)對(duì)于第一種情況，本實(shí)驗(yàn)選用的數(shù)據(jù)結(jié)構(gòu)是類。將選手的編號(hào)、積分、以及勝負(fù)處理等等封

3、裝在類中。勝負(fù)序列的求解轉(zhuǎn)化為了對(duì)所有選手的積分的排序問題。(2)對(duì)于第二種情況，本實(shí)驗(yàn)采用的數(shù)據(jù)結(jié)構(gòu)是有向圖，每個(gè)選手視為一個(gè)點(diǎn)，每條邊視為選手之間的勝負(fù)關(guān)系，箭頭指向的一方為失敗方。所以勝負(fù)序列的求解就轉(zhuǎn)化為了圖的深度遍歷問題。為了便于深度遍歷有向圖，采用的存儲(chǔ)結(jié)構(gòu)為圖的臨街矩陣存儲(chǔ)。三、詳細(xì)設(shè)計(jì)和編碼（1）就第一種情況而言，較為簡(jiǎn)單，設(shè)計(jì)一個(gè)選手類Player，私有成員包括分?jǐn)?shù)score和選手編號(hào)num。公有成員包括構(gòu)造函數(shù)Player（），設(shè)置編號(hào)voidsetnum（intnum1），獲勝處理函數(shù)v

4、oidwin（），失敗處理函數(shù)voidfail（），返回編號(hào)函數(shù)intgetnum（），返回積分函數(shù)intgetscore（）。類的定義如下：classplayer//選手類{private:intscore;//積分intnum;//參賽編號(hào)public:player(){}voidsetnum(intnum1)//設(shè)置編號(hào){num=num1;score=0;}voidwin()//勝利{score++;}voidfail()//失敗{score--;}intgetscore()//獲取分?jǐn)?shù){returns

5、core;}intgetnum()//獲取編號(hào){returnnum;}};這些代碼定義為頭文件score.h在程序的初始化時(shí)根據(jù)輸入的選手?jǐn)?shù)量n，動(dòng)態(tài)申請(qǐng)一個(gè)選手類的數(shù)組Player[n]。依次輸入第一個(gè)選手和后面的n-1個(gè)選手的勝負(fù)關(guān)系，第二個(gè)選手和后面n-2個(gè)選手的勝負(fù)關(guān)系……第n-1個(gè)選手和第n個(gè)選手的勝負(fù)關(guān)系。W（w）表示勝利，F(xiàn)（f）表示失敗。在選手的勝負(fù)關(guān)系輸入完畢后通過getscore（）返回各個(gè)選手的積分對(duì)各個(gè)選手的積分進(jìn)行排序，從而得到選手的勝負(fù)序列關(guān)系。（2）就第二種情況而言，較為復(fù)雜，使

6、用的圖，即將比賽過程中的各個(gè)選手間的勝負(fù)關(guān)系轉(zhuǎn)化為一個(gè)有向圖且是連同的完全有向圖。模型表示：由于僅涉及到n個(gè)選手，并且這些選手之間的關(guān)系僅是勝負(fù)關(guān)系，因此可用圖來表示，用頂點(diǎn)表示選手，用弧表示選手之間的勝負(fù)關(guān)系：當(dāng)且僅當(dāng)Pi勝Pj時(shí)，有從頂點(diǎn)i到j(luò)的一條弧。在這種表示下，本題問題變成了如下的問題：在有向圖中求解出一條包含所有頂點(diǎn)的簡(jiǎn)單路徑的問題。下圖所示為一個(gè)有8個(gè)選手的問題的一個(gè)示例。其中的一個(gè)解為1,2,3,4,8,6,5,7。算法設(shè)計(jì)：設(shè)計(jì)本題算法的構(gòu)思如下：為搜索出符合條件的簡(jiǎn)單路徑，需按深度優(yōu)先搜索

7、方式進(jìn)行遍歷。因此求解算法應(yīng)是深度遍歷算法的變形形式，也應(yīng)是遞歸形式的算法。由于要求遍歷序列中的各結(jié)點(diǎn)按次序構(gòu)成一條簡(jiǎn)單路徑，因此算法與深度遍歷算法有明顯的不同：并非任意選擇的起點(diǎn)和訪問次序都能得到解。而這些又是事先難以確定的。這就要求在求解過程中進(jìn)行試探：試探起點(diǎn)以及訪問次序。既然要在求解過程中進(jìn)行試探，則需要記錄試探的中間狀態(tài)：某頂點(diǎn)是否在當(dāng)前試探的路徑中，已經(jīng)試探的各頂點(diǎn)的次序，當(dāng)前正在試探的頂點(diǎn)等。將所用到的變量及有關(guān)參數(shù)設(shè)置如下：設(shè)置MAX_POINT_NUM100為最大選手?jǐn)?shù)量。路徑結(jié)構(gòu)WAY，包

8、含路徑上選手在序列數(shù)組中的小標(biāo)k和選手序列way[MAX_POINT_NUM]，都是整型。設(shè)置結(jié)構(gòu)體Graph為圖的存儲(chǔ)結(jié)構(gòu)，包含選手的人數(shù)n和存儲(chǔ)矩陣edges[MAX_POINT_NUM][MAX_POINT_NUM]，為鄰接存儲(chǔ)矩陣，即本程序采用臨街矩陣作為圖的存儲(chǔ)結(jié)構(gòu)。設(shè)圖為g，設(shè)當(dāng)前試探路徑中最后的頂點(diǎn)號(hào)為i，i在試探路徑中的序號(hào)為k，用整型數(shù)組visited[n]表示各頂點(diǎn)是否在當(dāng)前試探