第一篇：實驗3 貪心算法（定稿）
《算法設計與分析》實驗報告
實驗3貪心算法
姓名 學號班級 實驗日期實驗地點
一、實驗目的
1、掌握貪心算法的設計思想。
2、理解最小生成樹的相關概念。
二、實驗環境
1、硬件環境 CPU：酷睿i5 內存：4GB 硬盤：1T
2、軟件環境
操作系統：Windows10 編程環境：jdk 編程語言：Java
三、實驗內容：在Prim算法與Kruskal算法中任選一種求解最小生成樹問題。
1、你選擇的是：Prim算法
2、數據結構
（1）圖的數據結構——圖結構是研究數據元素之間的多對多的關系。在這種結構中，任意兩個元素之間可能存在關系，即結點之間的關系可以是任意的，圖中任意元素之間都可能相關。
圖形結構——多個對多個，如
（2）樹的數據結構——樹結構是研究數據元素之間的一對多的關系。在這種結構中，每個元素對下(層)可以有0個或多個元素相聯系，對上(層)只有唯一的一個元素相關，數據元素之間有明顯的層次關系。樹形結構——一個對多個，如
3、算法偽代碼 Prim(G,E,W)輸入：連通圖G 輸出：G的最小生成樹T 1.S←{1};T=? 2.While V-S ≠? do
3.從V-S中選擇j使得j到S中頂點的邊e的權最小；T←T∪{e} 4.S←S∪{j}
3、算法分析 時間復雜度：O(n)空間復雜度：O(n^2)
4、關鍵代碼（含注釋）
package Prim;
import java.util.*;publicclass Main { staticintMAXCOST=Integer.MAX_VALUE;
staticint Prim(intgraph[][], intn){ /* lowcost[i]記錄以i為終點的邊的最小權值，當lowcost[i]=0時表示終點i加入生成樹 */
intlowcost[]=newint[n+1];
/* mst[i]記錄對應lowcost[i]的起點，當mst[i]=0時表示起點i加入生成樹 */ intmst[]=newint[n+1];
intmin, minid, sum = 0;
/* 默認選擇1號節點加入生成樹，從2號節點開始初始化 */ for(inti = 2;i<= n;i++){
/* 標記1號節點加入生成樹 */ mst[1] = 0;
/* n個節點至少需要n-1條邊構成最小生成樹 */ for(inti = 2;i<= n;i++){
/* 找滿足條件的最小權值邊的節點minid */ for(intj = 2;j<= n;j++){
/* 輸出生成樹邊的信息:起點，終點，權值 */
System.out.printf(“%c1, minid + 'A''A' + 1;intj = chy-'A' + 1;graph[i][j] = cost;graph[j][i] = cost;for(intj = 1;j<= n;j++){ } graph[i][j] = MAXCOST;} } System.out.println(”Total:"+cost);} }
5、實驗結果（1）輸入
（2）輸出
最小生成樹的權值為： 生成過程：
(a)
(b)
(d)
(e)
(c)
四、實驗總結（心得體會、需要注意的問題等）
這次實驗，使我受益匪淺。這次實驗我選擇了Prim算法來求出樹的最小生成樹，在編寫代碼的過程中，我對Prim算法有了更深的了解，也使我對算法設計與分析更有興趣，今后一定要更努力的學習這門課。
第二篇：貪心算法實驗報告
實驗報告題目 實驗四 貪心算法
開課實驗室：數學實驗室
指導老師：韓逢慶
時間：2011.12 學院：理學院
專業：信息與計算科學
班級：2009級2班 姓名：古 月
學號：09180230
一、實驗目的 1．加深學生對貪心算法設計方法的基本思想、基本步驟、基本方法的理解與掌握；
2．提高學生利用課堂所學知識解決實際問題的能力；
3．提高學生綜合應用所學知識解決實際問題的能力。
二、實驗內容
題目見P143:4-16,4-23.三、實驗要求
（1）用分治法求解最少加油次數和最少硬幣個數問題；
（2）再選擇自己熟悉的其它方法求解本問題；
（3）上機實現所設計的所有算法；
四、實驗過程設計（算法設計過程）（1）最少加油次數 實驗題目
一輛汽車加滿油以后可以行使n公里，旅途中有若干個加油站，設計一個有效算法，指出應在哪些加油站停靠加油，使沿路加油次數最少。并證明算法能產生一個最優解。過程設計
貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。當然，希望貪心算法得到的最終結果也是整體最優的。雖然貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。比如說最少加油次數的問題。在這個算法中，我采用的貪心算法的策略。首先人機互動的設定加滿油以后最長能夠行使的距離，然后輸入了各個站點之間的距離，在程序的設計中，首先檢查了程序的可行性。要是遇到當某兩個站點之間的距離大于汽車一次加油以后所能夠行使的最大距離時，我們認為此問題是不可行的。這個在實際情況中也是很容易理解的。然后在滿足可行性條件下，依次采用貪心算法對問題得以實現。采用s這個來保存現在車里面留下的油，當此時留下的有能夠行駛完這一站點到下一站點之間的距離是，在這一站點的時候就不加油。但是若不能行使完這一段路程的時候，就加滿油。核心算法如下：
for(i=0,s=0;i { s=s+a[i]; if(s>n) { sum++; s=a[i]; } }（2）最少硬幣個數問題 實驗題目 考慮下面的用最少硬幣個數找出n分錢的問題： 當使用2角5分，1角，5分和1分四種硬幣面值時，設計一個找n分錢的貪心算法，并證明算法能產生最優解。過程設計 貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。當然，希望貪心算法得到的最終結果也是整體最優的。雖然貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。比如說找最少硬幣個數的問題。在算法的實現過程中，當剩余的錢數大于2角5分時，我們在記錄找2角5分硬幣的個數的變量里面加一，同時把剩余所找的錢的總數目也減2角5分。不斷重復這個過程，直到剩余所需找的錢的數目小于2角5分時，在記錄找1角硬幣的個數的變量里面加一，同時把剩余所找的錢的總數目也減1角，不斷重復這個過程，直到剩余所需找的錢的數目小于1角。5分和1分的硬幣實現過程同上述過程一樣，一直執行到所剩的錢的數目為0，此時停止計算，得到最優解。 五、實驗結果分析（1）最少加油次數 當加油后行駛的最大距離小于相鄰站點的最小值時，此時，可行，求解結果如下： 當加油后行駛的最大距離大于相鄰站點的最小值時，此時，沒用可行性，為邊沿情況，求解結果如下： （分析時空復雜性，設計測試用例及測試結果）時間復雜性：該算法的時間復雜度為O(n)空間復雜性分析：該算法的空間復雜度為O(1)（2）最少硬幣問題 當輸入的找零錢數為正常的時候的運行情況如下： 當輸入的找零錢數為不正常的時候（為負）的運行情況如下： （分析時空復雜性，設計測試用例及測試結果）時間復雜性：該算法的時間復雜性為O(n)空間復雜性分析：該算法的空間復雜性為O(1) 六、實驗體會 貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。當然，希望貪心算法得到的最終結果也是整體最優的。雖然貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。如單源最短路經問題，最小生成樹問題，相容活動安排問題等。這樣和采用動態規劃的算法相比，算法的思想更加的簡單，實現起來更加的容易。 但是也要明確貪心算法和動態規劃的主要區別。及0-1背包問題可以用動態規劃算法求解，但是貪心選擇算法卻不能用動態規劃算法求解。因為貪心算法無法最終將背包裝滿，部分閑置的背包空間使得每公斤背包空間的價值降低了。 七、附錄：（源代碼）（1）最少加油次數 具體算法的實現如下： #include cin>>a[i];} for(i=0;i<=n;i++){ cout<<“第”< if(a[j]>m) { sum=-1; break; } if(sum!=-1){ } for(i=0,s=0;i s=s+a[i]; if(s>n) { sum++; s=a[i]; } } } if(sum==-1)cout<<“沒有可行性”< #include cout<<“ 您輸入的數據有錯!”< a++; m=m-2.5;} while(m>=1){ b++; m=m-1;} while(m>=0.5){ c++; m=m-0.5;} while(m>=0.1){ d++; m=m-0.1;} f=a+b+c+d;cout<<“應找的最少的硬幣個數為：”< 算法分析與設計 實驗報告 班級：學號：姓名：上機時間： 一、實驗目的與要求： 1、熟悉貪心算法的基本原理和適用范圍； 2、使用貪心算法編程，求解最小生成樹問題。 二、實驗題目： 用貪心算法求解Prim算法 三、實驗內容： 任選一種貪心算法（prim或Kruskal），求解最小生成樹。對算法進行 描述和復雜性分析。編程實現。 四、問題描述： 設G=(V,E)是連通帶權圖，V={1,2,…,n}。構造G的最小生成樹的Prim 算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如 下的貪心選擇：選取滿足條件i∈s，j∈V-S，且c[i][j]最小的邊，將頂 點j添加到S中。這個過程一直進行到S=V時為止。在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹。 五、問題分析與算法設計 六、實驗結果及分析 七、實驗總結 八、程序代碼 #include #include #include #include #include #define maxint 20 #define inf 700 int AllSelected(int n,int s[]) { int i; for(i = 1;i <= n;i++) { if(s[i] == 0) return 0; } return 1; } void Prim(int n,int **c) { int lowcost[maxint]; int closest[maxint]; bools[maxint];s[1]=true; for(int i=2;i<=n;i++) { lowcost[i]=c[1][i]; closest[i]=1; s[i]=false; } for(i=1;i<=n;i++) { int min=inf; int j=1; for(int k=2;k<=n;k++) { if((lowcost[k] { min=lowcost[k]; j=k; } s[j]=true; for(int k=2;k<=n;k++) if((c[j][k] { lowcost[k]=c[j][k];closest[k]=j; } } } } void main() { int n,i,j; int **k; printf(“請輸入頂點個數:”); scanf(“%d”,&n); k=(int **)malloc(sizeof(int *)*(n + 1)); for(i = 1;i <= n;i++) k[i] =(int *)malloc(sizeof(int)*(n+1)); printf(“輸入頂點間的權值(自己到自己為0，沒有路的為大于其他任何值的數):n”);for(i=1;i<=n;i++) for(j=i;j<=n;j++) { printf(“k[%d][%d]=k[%d][%d]=”,i,j,j,i); scanf(“%d”,&k[i][j]); k[j][i]=k[i][j]; } printf(“n”); printf(“頂點t”); for(i=1;i<=n;i++) { printf(“%dt”,i); } printf(“n”); for(i=1;i<=n;i++) { printf(“%dt”,i); for(j=1;j<=n;j++) { printf(“%dt”,k[i][j]); } printf(“n”); } printf(“n”); Prim(n,k); } 一次，有黑、紅、白三只老鼠幫助土地神逃過了滅頂之災。為了表示感激之情，土地神答應給這三只老鼠一個特殊的獎賞：你能將土挖多深，那多么深的土層就屬于你的領地。 土地神警告它們，不要過于貪心，如果挖得過深，你們將難以返回地面而葬身地下。 這種獎賞令三只老鼠高興萬分，于是它們都使盡了全身的力氣去挖洞，至于挖多深的洞才是安全的，它們并不清楚，它們只能憑感覺。在它們看來，挖洞是自己的特長，它們可以用一半的力氣挖到很深的地方，再用剩下一半的力氣安全地返回地面。 黑老鼠挖洞的速度很快。沒過多久，它已經挖到了很深的地方。它十分興奮，一想到它所挖的深度就是它的領地，它的力量就源源不斷地涌出來。不知過了多久，它覺得自己的力氣已經用去了一半，它決定休息一會兒，然后返回地面。對它來說，這么深的土層已經足夠用了。 不一會兒，它的體力恢復了許多。它想，再挖一會兒也不會有什么危險，這樣返回去太可惜了。于是，它又挖了許久。當它覺得有些累了的時候，開始提醒自己：不要再向下面挖了，如果不能返回地面，一切就都完了。于是，它想沿著原來挖的路線向地面方向返回。 但此時，它又猶豫了，也許現在紅老鼠和白老鼠正全力向地下挖土呢，如果自己這樣返回去，可能是挖得最淺的一只老鼠，那么獲得的領地也是最少的，也就最沒有面子了。 想到這，它決定冒險再向下挖一陣子。又挖了許久后，黑老鼠覺得身體很疲乏，有些吃不消了。它明白，現在已經很危險了。不過，它又咬了咬牙，心想：反正已經冒險了，索性就再冒一步險，將土層挖得更深一些。 盡管它時時感覺到危險，但是，黑老鼠總是能找到各種理由激勵自己向更深的土層挖下去。 不知過了多久，它失去了知覺，累死了。 紅老鼠的經歷與黑老鼠大致相同。它也累死了。 只有白老鼠活了下來。 土地神覺得十分傷感的同時，也感到一絲安慰。原來，這個世界上到底還是有不貪心的老鼠呀！它決定大力宣傳白老鼠的事跡，告訴大家不貪心才是正確的生活態度。 事后，土地神問白老鼠的想法。 白老鼠冷冷地回答道：“難道你沒有發現我的兩只爪子是殘廢的嗎？” 貪心是人的一大弱點，如果控制不了自己的貪欲，那真是一件十分危險的事情。 證明人民幣找零問題貪心算法的正確性 問題提出： 根據人們生活常識，我們到商店里買東西需要找零錢時，收銀員總是先給我們最大面值的，要是不夠再找面值小一點的，直到找完為止。這就是一個典型的貪心選擇問題。問題描述： 當前有面值分別為100 元、50 元、20 元、10 元、5元、1元, 5角, 2角、1角的人民幣。證明人民幣在找零時（1-99元）符合貪心算法，即證明此問題滿足貪心算法的兩個基本要素：即最優子結構性質和貪心選擇性質。 問題證明： 當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。在人民幣找零問題中，其最優子結構性質表現為： 設c[i]是各面額人民幣使用的數量，S[i]是商品價格為n時的最優解，數量為K。現在設某面值的人民幣數量減一：S[j]=S[j]-1，則新的S[i]為n-c[j]的最優解，紙幣數K-1.否則，設T[i]是n-c[j]的最優解，紙幣數為m，即m 設紙幣面額100,50,20,10,5,2,1元的數量依次為A,B,C,D,E,F,G，則根據貪心算法思想得到的解應依次保證max（A），max（B），max（C），max（D），max（E），max（F），max（G）。假設存在更優的算法，使得所用的紙幣數更少，即數量至少小于或等于A+B+C+D+E+F+G-1。那么在紙幣總數減少的情況下保證總額不變只能增大相對大面額紙幣的數量并減少小面額紙幣數量。而由貪心算法知max（A）已經是最大的了，以此類推，max（B），max（C），max（D），max（E），max（F）均應為最大數量了，所以貪心算法得到的解是最優解，即滿足貪心選擇性質。 綜上所述，人民幣找零問題滿足貪心算法。第三篇：用貪心算法求解Prim算法上機實驗報告書
第四篇：貪心實驗美文摘抄
第五篇：證明人民幣找零問題貪心算法正確性（范文模版）
點擊咨詢 