版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、吉林財(cái)經(jīng)大學(xué)算法設(shè)計(jì)與分析課程設(shè)計(jì) 專業(yè):計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)號(hào): 1401101431 姓名: 黃河一·課設(shè)內(nèi)容分析1)問(wèn)題描述第二次世界大戰(zhàn)時(shí)期,英國(guó)皇家空軍從淪陷國(guó)征募了大量外籍飛行員。由皇家空軍派出的每一架飛機(jī)都需要配備在航行技能和語(yǔ)言上能互相配合的2 名飛行員,其中1名是英國(guó)飛行員,另1名是外籍飛行員。在眾多的飛行員中,每一名外籍飛行員都可以與其他若干名英國(guó)飛行員很好地配合。如何選擇配對(duì)飛行的飛行員才能使一次派出最多的飛機(jī)。對(duì)于給定的外籍飛行員與英國(guó)飛行員的配合情況,試設(shè)計(jì)一個(gè)算法找出最佳飛行員配對(duì)方案,使皇家空軍一次能派出最多的飛機(jī)。2)問(wèn)題分析基礎(chǔ)的二分圖最大匹配問(wèn)題。
2、 給定一個(gè)二分圖G,M為G邊集的一個(gè)子集,如果M滿足當(dāng)中的任意兩條邊都不依附于同一個(gè)頂點(diǎn),則稱M是一個(gè)匹配。極大匹配是指在當(dāng)前已完成的匹配下,無(wú)法再通過(guò)增加未完成匹配的邊的方式來(lái)增加匹配的邊數(shù)。最大匹配是所有極大匹配當(dāng)中邊數(shù)最大的一個(gè)匹配。選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問(wèn)題。如果一個(gè)匹配中,圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián),則稱此匹配為完全匹配,也稱作完備匹配。求二分圖最大匹配可以用最大流或者匈牙利算法。 3)建模方法 在二分圖的基礎(chǔ)上增加源S和匯T。 (1): S向X集合中每個(gè)頂點(diǎn)連一條容量為1的有向邊。 (2): Y集合中每個(gè)頂點(diǎn)向T連一條容量為1的有向邊。 (3): XY集合
3、之間的邊都設(shè)為從A集合中的點(diǎn)到B集合之中的點(diǎn),容量為1的有向邊。 4)建模分析 基本的二分圖最大匹配,可以直接用匈牙利算法或Hopcroft_Karp算法解決,更一般的方法是網(wǎng)絡(luò)最大流。 求網(wǎng)絡(luò)最大流,流量就是匹配數(shù),所有滿流邊是一組可行解。 可行解的輸出:枚舉所以邊< u , v >,如果uX,vY,并且< u , v >滿流,那么當(dāng)前邊為可行解的一組匹配。 二·課程設(shè)計(jì)目的 通過(guò)課程設(shè)計(jì),提高用計(jì)算機(jī)解決實(shí)際問(wèn)題的能力,提高獨(dú)立實(shí)踐的能力,將課本上的理論知識(shí)和實(shí)際有機(jī)的結(jié)合起來(lái),鍛煉分析解決實(shí)際問(wèn)題的能力。提高結(jié)合實(shí)際的編程能力。在實(shí)際的編程和調(diào)試綜合試題
4、的基礎(chǔ)上,把高級(jí)語(yǔ)言程序設(shè)計(jì)的思想、編程巧和解題思路進(jìn)行總結(jié)與概括,通過(guò)比較系統(tǒng)地練習(xí)達(dá)到真正比較熟練地掌握計(jì)算機(jī)編程的基本功,為后續(xù)的學(xué)習(xí)打下基礎(chǔ)。 最重要的事培養(yǎng)自己的理性思維,無(wú)論是在編程還是在以后的工作生活中養(yǎng)成一個(gè)良好的思維習(xí)慣。三·算法原理及思路運(yùn)用數(shù)學(xué)上的短除法讓一個(gè)整數(shù)對(duì)二取余,然后再讓這個(gè)整數(shù)除以二,取整數(shù)部分,然后繼續(xù)對(duì)二取余,如此繼續(xù)循環(huán),中間只要對(duì)二取余的結(jié)果是一,就累加一次,直到該整數(shù)最后為零,最后把累加的結(jié)果輸出,就是該整數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)后里面有多少個(gè)一。四·源代碼 #include <iostream.h>#include <
5、cstdio>#include <cstring>#include <algorithm>#define maxn 10020#define INF 100000000using namespace std;int n, m, s, t, tot, ans, dmaxn, headmaxn, distmaxn;struct E int from;int to;int next;int tab;edgemaxn;void add_edge(int u, int v, int f) tot+; edgetot.from = u, edgetot.to = v, edg
6、etot.tab = f, edgetot.next = headu, headu = tot; tot+; edgetot.from = v, edgetot.to = u, edgetot.tab = 0, edgetot.next = headv, headv = tot;int min(int a,int b)if(a>b)return b;elsereturn a;int dfs(int x, int low) int a; if (x = t) return low; for (int i = headx; i != -1; i = edgei.next) if (edgei
7、.tab > 0 && distedgei.to = distx + 1 && (a = dfs(edgei.to, min(edgei.tab, low) edgei.tab -= a, edgei1.tab += a; return a; return 0; int bfs() int l, r, k; memset(dist,0xff,sizeof(dist); d0 = 0; d1 = s; l = 0, r = 1; dists = 0; while (l < r) k = d+l; for (int i = headk; i != -1;
8、 i = edgei.next) if (edgei.tab > 0 && distedgei.to < 0) distedgei.to = distk + 1, d+r = edgei.to; if (distt > 0) return 1; else return 0; void dinic() ans = 0; while (bfs() ans += dfs(0,INF); void print() if (ans = 0) printf("No Sulotionn"); return; printf("%dn",
9、ans); for (int i = 0; i <= tot; i += 2) if (edgei.tab = 0 && edgei.from != s && edgei.to != t) printf("%d %dn", edgei.from, edgei.to); int main()FILE *file=NULL;file=fopen("data/air0.in","r"); if(file=NULL)cout<<"don't open the file&quo
10、t;<<endl;exit(0); int x, y,i; memset(head,0xff,sizeof(head); tot = -1; while(fscanf(file,"%d%d",&m,&n)!=EOF) s = 0, t = n + 1; for (i = 1; i <= m; i+) add_edge(0, i, 1); for (i = m+1; i <= n; i+) add_edge(i, t, 1); while (fscanf(file,"%d%d",&x,&y)!=EOF) if (x = -1 && y = -1) break; else add_edge(x, y, 1); dinic(); print(); return 0;五·個(gè)人總結(jié) 在這次課程設(shè)計(jì)的學(xué)習(xí)中,我學(xué)到了很多,也找到了自己身上的不足。感受良多,獲益匪淺。 在課程設(shè)計(jì)的過(guò)程中,經(jīng)歷了奮斗的酸甜苦辣。分享了成功的喜悅。這次的課程設(shè)計(jì)對(duì)我來(lái)說(shuō)是一個(gè)挑戰(zhàn)。課程設(shè)計(jì)中文檔的撰寫(xiě)我從來(lái)就沒(méi)有擔(dān)心過(guò),就是代
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 人教版八年級(jí)物理下冊(cè)《7.1力》同步測(cè)試題有答案
- 云南省昭通市2024年中考模擬預(yù)測(cè)數(shù)學(xué)模擬預(yù)測(cè)題附答案
- 科學(xué)育種技術(shù)優(yōu)化作物抗病蟲(chóng)害能力
- 繼續(xù)教育八大員施工員(設(shè)備安裝)考試題目+答案資料
- 中國(guó)糧食生產(chǎn)現(xiàn)狀及需求預(yù)測(cè)
- 高一化學(xué)鞏固練習(xí):第一章從實(shí)驗(yàn)學(xué)化學(xué)全章復(fù)習(xí)與鞏固提高
- 2024屆金昌市重點(diǎn)中學(xué)高考仿真卷化學(xué)試卷含解析
- 2024高中地理第2章區(qū)域可持續(xù)發(fā)展第5節(jié)礦產(chǎn)資源合理開(kāi)發(fā)和區(qū)域可持續(xù)發(fā)展學(xué)案湘教版必修3
- 2024高中物理第三章傳感器第一節(jié)認(rèn)識(shí)傳感器第二節(jié)傳感器的原理達(dá)標(biāo)作業(yè)含解析粵教版選修3-2
- 2024高中語(yǔ)文第5單元莊子蚜第5課惡乎往而不可訓(xùn)練含解析新人教版選修先秦諸子蚜
- 八年級(jí)散文閱讀專題訓(xùn)練-八年級(jí)語(yǔ)文上冊(cè)知識(shí)梳理與能力訓(xùn)練
- 2024年杭州市中醫(yī)院高層次衛(wèi)技人才招聘筆試歷年參考題庫(kù)頻考點(diǎn)附帶答案
- 2024-2025學(xué)年人教版八年級(jí)數(shù)學(xué)上冊(cè)期末測(cè)試模擬試題(含答案)
- 《環(huán)境感知技術(shù)》2024年課程標(biāo)準(zhǔn)(含課程思政設(shè)計(jì))
- GB/T 45079-2024人工智能深度學(xué)習(xí)框架多硬件平臺(tái)適配技術(shù)規(guī)范
- GB/T 25772-2010滾動(dòng)軸承鐵路客車軸承
- GB 31247-2014電纜及光纜燃燒性能分級(jí)
- 士卓曼種植系統(tǒng)外科植入流程課件
- 二年級(jí)下冊(cè)《一起長(zhǎng)大的玩具》導(dǎo)讀教學(xué)-一場(chǎng)別樣的童年之旅
- 二尖瓣狹窄并關(guān)閉不全共17張課件
- 心臟瓣膜病護(hù)理課件
評(píng)論
0/150
提交評(píng)論