演算法設計與分析課程設計
題目: 模擬實現穩定婚姻問題的gale-shapley演算法
設計分析測試報告
姓名：鄭展圖
學號：3100608010
班級：軟體1001
指導教師：蔣麗萍
2023年 1 月 9 日
程式演算法設計說明書
一、 前言
1.問題描述：穩定婚姻問題：
有n男n女，每人都按他對（異性）物件的喜好程度按1至n排列。安排男女結婚，使得下列情形為真:在n男n女中的任意兩對夫婦(m, w)和(m, w)，都不存在m男對w女喜好度大於現任妻子w女，並且w女對m男喜好度也大於現任丈夫m男的情形發生，此種情形稱為不穩定。
2.程式編制環境相關說明：
系統：windows 7
編制環境：visual studio 8
二、 程式主要演算法設計分析說明
演算法設計思路:在n對男女中，男生採用主動出擊追求自己最喜歡的女生策略，女生採用「守株待兔」和「喜新厭舊」策略。
每一位男生主動去追求自己最喜歡的女生，而女生則在追求自己的男生中與現任男友中，選擇一位最喜歡的接受。如果追求成功，為被拋棄的男友追求他下一位喜歡的女生。如果追求不成功，則為這位男生追求他下一位喜歡的女生。
這樣進行了n次迴圈後，每一位男生都是從自己最喜歡的女生開始追求，並且都有女友，那麼男生喜歡的程度多於現任妻子的那位女生肯定是曾經拒絕過自己的。同理，女生也是按照自己喜歡程度進行選擇的。那麼也不會出現不穩定問題。
三、 程式模組說明
1. 總體設計說明：
程式採用兩個二維陣列man[max][max],woman[max][max]來記錄max位男生，女生對異性的喜歡程度順序。
陣列acman記錄男生下一位追求的女生順序（最開始從0位，也就是最喜歡的一位開始）；
陣列acwoman記錄每一位女生當前男友（最開始設定一位虛擬男友，其喜歡程度最小）
採用4個for迴圈，分別對4個陣列初始化。
採用乙個for迴圈遍歷man陣列（為每一位男生追求其最喜歡的女生）
採用乙個for迴圈輸出結果
2. 模組說明：
2.1 模組一：bool changebf(vector > woman,int i,int newbf,int oldbf,int max)函式
(1) 概要說明：判斷某位女生的當前男友與追求她的男友的排位順序（喜歡程度）
(2) 關鍵資料結構和演算法及其分析（比較newbf和oldbf在陣列woman[max]的序號大小，從而判斷喜歡程度）
(3) 輸入（陣列woman）
(4) 輸出(bool型別1,0)
四、 總結（含主函式設計說明）
這次課程設計的題目有點複雜，一開始看到這個題目時，還不知道要怎麼下手解決。後來在網上搜尋了一下婚姻穩定問題及延遲確認演算法。發現將每個女生的喜歡程度進行排序後就很容易解決。
演算法解決了，接下來具體用什麼資料結構實現也是個問題。試過用結構體，鍊錶等資料結構。最後還是覺得直接用陣列最簡潔。
確定了用二維陣列，程式就基本定下來了，主函式就是對二維陣列的遍歷。
為了實現多樣化，我在對二維陣列初始化時採用了由使用者輸入實現初始化。這裡用到了動態陣列的知識。
總結這次課程設計，雖然程式的實現並不難，也不複雜。但是實現程式的演算法卻難倒了我。這也讓我深刻地體會到了演算法的力量。在以後的學習中，我一定會注意自己的薄弱環節，好好補充知識。
五、時間複雜性：o（n^2）;
程式及演算法測試報告
一、 前言
1. 測試目的及採用的主要測試方法
目的：測試該程式能否成功對n對男女成功配對，且婚姻穩定。
測試方法：設定不同的資料，判斷是否有錯誤。
被測試程式演算法說明及流程圖等
**：#include
#include
using namespace std;
void main()
for(int i=0;i
bool changebf(vector > woman,int,int,int,int);
for(int j=0;j
else
}for(int j=0;j
}bool changebf(vector > woman,int i,int newbf,int oldbf,int max)
for(int j=0;j<=max;j++)
return(temp1 }
2. 測試環境說明
系統：windows 7
測試環境：visual studio 8
二、 測試用例說明
1. 測試用例1
目的：判斷是否一對一的配對
輸入預期輸出：不會出現重複數字
實際輸出
測試結果：顯示每一位男生都唯一配對以為女生
2. 測試用例2
目的：測試每一位配對的組合是否婚姻穩定
輸入預期輸出：0 3 2 1
實際輸出
測試結果：配對婚姻穩定
3．測試用例3
目的：繼續測試每一對情侶婚姻是否穩定
輸入預期輸出：1 0 2
實際輸出
測試結果：配對婚姻穩定
三、 測試結果分析
測試結果顯示，每一位男生其配對的女生都是唯一的；每一位情侶都滿足婚姻穩定的條件。
演算法與資料結構課程設計報告
演算法與資料結構 課程設計實驗報告書 課程設計名稱 最小套圈設計 學生姓名 張延雲 學號 201058501314 學院 計算機學院 班級 計101 3班 日期 2012年7月13日 一 問題分析和任務定義 1 問題分析 本設計的要求是設計乙個最小套圈。規則是 遊戲者將手中的圓環套圈投向場中的玩具，...
資料結構與演算法課程設計
在程式正確性的前提下，要兼顧介面設計和 可重用性的質量，注重物件導向設計理念的考核。上交的成果的內容必須由以下四個部分組成，缺一不可 1 上交源程式 學生按照課程設計的具體要求所開發的所有源程式 應該放到乙個資料夾中 2 上交程式的說明檔案 儲存在.txt中 在說明文件中應該寫明上交程式所在的目錄，...
《數值分析》課程設計報告
課程設計報告 課程設計題目 牛頓迭代法求解非線性方程組 學生姓名 專業 班級 指導教師 題目 在化學工程中常常研究在乙個封閉系統中同時進行的兩種可逆反應 其中a，b，c和d代表不同的物質。反應達到平衡是有如下的平衡關係 其中稱為平衡常數，代表平衡狀態時該物質的濃度。假定反應開始時各種物質的濃度為 而...