第一篇：實(shí)驗(yàn)3 貪心算法（定稿）

《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)3貪心算法

姓名 學(xué)號班級 實(shí)驗(yàn)日期實(shí)驗(yàn)地點(diǎn)

一、實(shí)驗(yàn)?zāi)康?/p>

1、掌握貪心算法的設(shè)計(jì)思想。

2、理解最小生成樹的相關(guān)概念。

二、實(shí)驗(yàn)環(huán)境

1、硬件環(huán)境 CPU：酷睿i5 內(nèi)存：4GB 硬盤：1T

2、軟件環(huán)境

操作系統(tǒng)：Windows10 編程環(huán)境：jdk 編程語言：Java

三、實(shí)驗(yàn)內(nèi)容：在Prim算法與Kruskal算法中任選一種求解最小生成樹問題。

1、你選擇的是：Prim算法

2、數(shù)據(jù)結(jié)構(gòu)

（1）圖的數(shù)據(jù)結(jié)構(gòu)——圖結(jié)構(gòu)是研究數(shù)據(jù)元素之間的多對多的關(guān)系。在這種結(jié)構(gòu)中，任意兩個元素之間可能存在關(guān)系，即結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意元素之間都可能相關(guān)。

圖形結(jié)構(gòu)——多個對多個，如

（2）樹的數(shù)據(jù)結(jié)構(gòu)——樹結(jié)構(gòu)是研究數(shù)據(jù)元素之間的一對多的關(guān)系。在這種結(jié)構(gòu)中，每個元素對下(層)可以有0個或多個元素相聯(lián)系，對上(層)只有唯一的一個元素相關(guān)，數(shù)據(jù)元素之間有明顯的層次關(guān)系。樹形結(jié)構(gòu)——一個對多個，如

3、算法偽代碼 Prim(G,E,W)輸入：連通圖G 輸出：G的最小生成樹T 1.S←{1};T=? 2.While V-S ≠? do

3.從V-S中選擇j使得j到S中頂點(diǎn)的邊e的權(quán)最小；T←T∪{e} 4.S←S∪{j}

3、算法分析 時(shí)間復(fù)雜度：O(n)空間復(fù)雜度：O(n^2)

4、關(guān)鍵代碼（含注釋）

package Prim;

import java.util.*;publicclass Main { staticintMAXCOST=Integer.MAX_VALUE;

staticint Prim(intgraph[][], intn){ /* lowcost[i]記錄以i為終點(diǎn)的邊的最小權(quán)值，當(dāng)lowcost[i]=0時(shí)表示終點(diǎn)i加入生成樹 */

intlowcost[]=newint[n+1];

/* mst[i]記錄對應(yīng)lowcost[i]的起點(diǎn)，當(dāng)mst[i]=0時(shí)表示起點(diǎn)i加入生成樹 */ intmst[]=newint[n+1];

intmin, minid, sum = 0;

/* 默認(rèn)選擇1號節(jié)點(diǎn)加入生成樹，從2號節(jié)點(diǎn)開始初始化 */ for(inti = 2;i<= n;i++){

/* 標(biāo)記1號節(jié)點(diǎn)加入生成樹 */ mst[1] = 0;

/* n個節(jié)點(diǎn)至少需要n-1條邊構(gòu)成最小生成樹 */ for(inti = 2;i<= n;i++){

/* 找滿足條件的最小權(quán)值邊的節(jié)點(diǎn)minid */ for(intj = 2;j<= n;j++){

/* 輸出生成樹邊的信息:起點(diǎn)，終點(diǎn)，權(quán)值 */

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、實(shí)驗(yàn)結(jié)果（1）輸入

（2）輸出

最小生成樹的權(quán)值為： 生成過程：

(a)

(b)

(d)

(e)

(c)

四、實(shí)驗(yàn)總結(jié)（心得體會、需要注意的問題等）

這次實(shí)驗(yàn)，使我受益匪淺。這次實(shí)驗(yàn)我選擇了Prim算法來求出樹的最小生成樹，在編寫代碼的過程中，我對Prim算法有了更深的了解，也使我對算法設(shè)計(jì)與分析更有興趣，今后一定要更努力的學(xué)習(xí)這門課。

第二篇：貪心算法實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)報(bào)告題目 實(shí)驗(yàn)四 貪心算法

開課實(shí)驗(yàn)室：數(shù)學(xué)實(shí)驗(yàn)室

指導(dǎo)老師：韓逢慶

時(shí)間：2011.12 學(xué)院：理學(xué)院

專業(yè)：信息與計(jì)算科學(xué)

班級：2009級2班 姓名：古 月

學(xué)號：09180230

一、實(shí)驗(yàn)?zāi)康?1．加深學(xué)生對貪心算法設(shè)計(jì)方法的基本思想、基本步驟、基本方法的理解與掌握；

2．提高學(xué)生利用課堂所學(xué)知識解決實(shí)際問題的能力；

3．提高學(xué)生綜合應(yīng)用所學(xué)知識解決實(shí)際問題的能力。

二、實(shí)驗(yàn)內(nèi)容

題目見P143:4-16,4-23.三、實(shí)驗(yàn)要求

（1）用分治法求解最少加油次數(shù)和最少硬幣個數(shù)問題；

（2）再選擇自己熟悉的其它方法求解本問題；

（3）上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的所有算法；

四、實(shí)驗(yàn)過程設(shè)計(jì)（算法設(shè)計(jì)過程）（1）最少加油次數(shù) 實(shí)驗(yàn)題目

一輛汽車加滿油以后可以行使n公里，旅途中有若干個加油站，設(shè)計(jì)一個有效算法，指出應(yīng)在哪些加油站停靠加油，使沿路加油次數(shù)最少。并證明算法能產(chǎn)生一個最優(yōu)解。過程設(shè)計(jì)

貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。比如說最少加油次數(shù)的問題。在這個算法中，我采用的貪心算法的策略。首先人機(jī)互動的設(shè)定加滿油以后最長能夠行使的距離，然后輸入了各個站點(diǎn)之間的距離，在程序的設(shè)計(jì)中，首先檢查了程序的可行性。要是遇到當(dāng)某兩個站點(diǎn)之間的距離大于汽車一次加油以后所能夠行使的最大距離時(shí)，我們認(rèn)為此問題是不可行的。這個在實(shí)際情況中也是很容易理解的。然后在滿足可行性條件下，依次采用貪心算法對問題得以實(shí)現(xiàn)。采用s這個來保存現(xiàn)在車?yán)锩媪粝碌挠?，?dāng)此時(shí)留下的有能夠行駛完這一站點(diǎn)到下一站點(diǎn)之間的距離是，在這一站點(diǎn)的時(shí)候就不加油。但是若不能行使完這一段路程的時(shí)候，就加滿油。核心算法如下：

for(i=0,s=0;i

{

s=s+a[i];

if(s>n)

{

sum++;

s=a[i];

}

}（2）最少硬幣個數(shù)問題 實(shí)驗(yàn)題目

考慮下面的用最少硬幣個數(shù)找出n分錢的問題：

當(dāng)使用2角5分，1角，5分和1分四種硬幣面值時(shí)，設(shè)計(jì)一個找n分錢的貪心算法，并證明算法能產(chǎn)生最優(yōu)解。過程設(shè)計(jì)

貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。比如說找最少硬幣個數(shù)的問題。在算法的實(shí)現(xiàn)過程中，當(dāng)剩余的錢數(shù)大于2角5分時(shí)，我們在記錄找2角5分硬幣的個數(shù)的變量里面加一，同時(shí)把剩余所找的錢的總數(shù)目也減2角5分。不斷重復(fù)這個過程，直到剩余所需找的錢的數(shù)目小于2角5分時(shí)，在記錄找1角硬幣的個數(shù)的變量里面加一，同時(shí)把剩余所找的錢的總數(shù)目也減1角，不斷重復(fù)這個過程，直到剩余所需找的錢的數(shù)目小于1角。5分和1分的硬幣實(shí)現(xiàn)過程同上述過程一樣，一直執(zhí)行到所剩的錢的數(shù)目為0，此時(shí)停止計(jì)算，得到最優(yōu)解。

五、實(shí)驗(yàn)結(jié)果分析（1）最少加油次數(shù)

當(dāng)加油后行駛的最大距離小于相鄰站點(diǎn)的最小值時(shí)，此時(shí)，可行，求解結(jié)果如下：

當(dāng)加油后行駛的最大距離大于相鄰站點(diǎn)的最小值時(shí)，此時(shí)，沒用可行性，為邊沿情況，求解結(jié)果如下：

（分析時(shí)空復(fù)雜性，設(shè)計(jì)測試用例及測試結(jié)果）時(shí)間復(fù)雜性：該算法的時(shí)間復(fù)雜度為O(n)空間復(fù)雜性分析：該算法的空間復(fù)雜度為O(1)（2）最少硬幣問題 當(dāng)輸入的找零錢數(shù)為正常的時(shí)候的運(yùn)行情況如下：

當(dāng)輸入的找零錢數(shù)為不正常的時(shí)候（為負(fù)）的運(yùn)行情況如下：

（分析時(shí)空復(fù)雜性，設(shè)計(jì)測試用例及測試結(jié)果）時(shí)間復(fù)雜性：該算法的時(shí)間復(fù)雜性為O(n)空間復(fù)雜性分析：該算法的空間復(fù)雜性為O(1)

六、實(shí)驗(yàn)體會

貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題，相容活動安排問題等。這樣和采用動態(tài)規(guī)劃的算法相比，算法的思想更加的簡單，實(shí)現(xiàn)起來更加的容易。

但是也要明確貪心算法和動態(tài)規(guī)劃的主要區(qū)別。及0-1背包問題可以用動態(tài)規(guī)劃算法求解，但是貪心選擇算法卻不能用動態(tài)規(guī)劃算法求解。因?yàn)樨澬乃惴o法最終將背包裝滿，部分閑置的背包空間使得每公斤背包空間的價(jià)值降低了。

七、附錄：（源代碼）（1）最少加油次數(shù) 具體算法的實(shí)現(xiàn)如下：

#include void main(){ int n,m,a[100],i,s,sum=0,j;cout<<“請輸入沿途的站點(diǎn)數(shù)和每一次加油以后可以行使的路程數(shù)”<>n;cin>>m;cout<<“沿途的站點(diǎn)數(shù)為：”<

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 main(){ double n,m,a,b,c,d,f;a=b=c=d=0;cout<<“請輸入應(yīng)找的錢!”<>n;if(n<=0)

cout<<“ 您輸入的數(shù)據(jù)有錯!”<=2.5){

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<<“應(yīng)找的最少的硬幣個數(shù)為：”<

第三篇：用貪心算法求解Prim算法上機(jī)實(shí)驗(yàn)報(bào)告書

算法分析與設(shè)計(jì)

實(shí)驗(yàn)報(bào)告

班級：學(xué)號：姓名：上機(jī)時(shí)間：

一、實(shí)驗(yàn)?zāi)康呐c要求：

1、熟悉貪心算法的基本原理和適用范圍；

2、使用貪心算法編程，求解最小生成樹問題。

二、實(shí)驗(yàn)題目：

用貪心算法求解Prim算法

三、實(shí)驗(yàn)內(nèi)容：

任選一種貪心算法（prim或Kruskal），求解最小生成樹。對算法進(jìn)行

描述和復(fù)雜性分析。編程實(shí)現(xiàn)。

四、問題描述：

設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n}。構(gòu)造G的最小生成樹的Prim

算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如

下的貪心選擇：選取滿足條件i∈s，j∈V-S，且c[i][j]最小的邊，將頂

點(diǎn)j添加到S中。這個過程一直進(jìn)行到S=V時(shí)為止。在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。

五、問題分析與算法設(shè)計(jì)

六、實(shí)驗(yàn)結(jié)果及分析

七、實(shí)驗(yàn)總結(jié)

八、程序代碼

#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(“請輸入頂點(diǎn)個數(shù):”);

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(“輸入頂點(diǎn)間的權(quán)值(自己到自己為0，沒有路的為大于其他任何值的數(shù)):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(“頂點(diǎn)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);

}

第四篇：貪心實(shí)驗(yàn)美文摘抄

一次，有黑、紅、白三只老鼠幫助土地神逃過了滅頂之災(zāi)。為了表示感激之情，土地神答應(yīng)給這三只老鼠一個特殊的獎賞：你能將土挖多深，那多么深的土層就屬于你的領(lǐng)地。

土地神警告它們，不要過于貪心，如果挖得過深，你們將難以返回地面而葬身地下。

這種獎賞令三只老鼠高興萬分，于是它們都使盡了全身的力氣去挖洞，至于挖多深的洞才是安全的，它們并不清楚，它們只能憑感覺。在它們看來，挖洞是自己的特長，它們可以用一半的力氣挖到很深的地方，再用剩下一半的力氣安全地返回地面。

黑老鼠挖洞的速度很快。沒過多久，它已經(jīng)挖到了很深的地方。它十分興奮，一想到它所挖的深度就是它的領(lǐng)地，它的力量就源源不斷地涌出來。不知過了多久，它覺得自己的力氣已經(jīng)用去了一半，它決定休息一會兒，然后返回地面。對它來說，這么深的土層已經(jīng)足夠用了。

不一會兒，它的體力恢復(fù)了許多。它想，再挖一會兒也不會有什么危險(xiǎn)，這樣返回去太可惜了。于是，它又挖了許久。當(dāng)它覺得有些累了的時(shí)候，開始提醒自己：不要再向下面挖了，如果不能返回地面，一切就都完了。于是，它想沿著原來挖的路線向地面方向返回。

但此時(shí)，它又猶豫了，也許現(xiàn)在紅老鼠和白老鼠正全力向地下挖土呢，如果自己這樣返回去，可能是挖得最淺的一只老鼠，那么獲得的領(lǐng)地也是最少的，也就最沒有面子了。

想到這，它決定冒險(xiǎn)再向下挖一陣子。又挖了許久后，黑老鼠覺得身體很疲乏，有些吃不消了。它明白，現(xiàn)在已經(jīng)很危險(xiǎn)了。不過，它又咬了咬牙，心想：反正已經(jīng)冒險(xiǎn)了，索性就再冒一步險(xiǎn)，將土層挖得更深一些。

盡管它時(shí)時(shí)感覺到危險(xiǎn)，但是，黑老鼠總是能找到各種理由激勵自己向更深的土層挖下去。

不知過了多久，它失去了知覺，累死了。

紅老鼠的經(jīng)歷與黑老鼠大致相同。它也累死了。

只有白老鼠活了下來。

土地神覺得十分傷感的同時(shí)，也感到一絲安慰。原來，這個世界上到底還是有不貪心的老鼠呀！它決定大力宣傳白老鼠的事跡，告訴大家不貪心才是正確的生活態(tài)度。

事后，土地神問白老鼠的想法。

白老鼠冷冷地回答道：“難道你沒有發(fā)現(xiàn)我的兩只爪子是殘廢的嗎？”

貪心是人的一大弱點(diǎn)，如果控制不了自己的貪欲，那真是一件十分危險(xiǎn)的事情。

第五篇：證明人民幣找零問題貪心算法正確性（范文模版）

證明人民幣找零問題貪心算法的正確性

問題提出：

根據(jù)人們生活常識，我們到商店里買東西需要找零錢時(shí)，收銀員總是先給我們最大面值的，要是不夠再找面值小一點(diǎn)的，直到找完為止。這就是一個典型的貪心選擇問題。問題描述：

當(dāng)前有面值分別為100 元、50 元、20 元、10 元、5元、1元, 5角, 2角、1角的人民幣。證明人民幣在找零時(shí)（1-99元）符合貪心算法，即證明此問題滿足貪心算法的兩個基本要素：即最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)。

問題證明：

當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。在人民幣找零問題中，其最優(yōu)子結(jié)構(gòu)性質(zhì)表現(xiàn)為：

設(shè)c[i]是各面額人民幣使用的數(shù)量，S[i]是商品價(jià)格為n時(shí)的最優(yōu)解，數(shù)量為K?，F(xiàn)在設(shè)某面值的人民幣數(shù)量減一：S[j]=S[j]-1，則新的S[i]為n-c[j]的最優(yōu)解，紙幣數(shù)K-1.否則，設(shè)T[i]是n-c[j]的最優(yōu)解，紙幣數(shù)為m，即m

設(shè)紙幣面額100,50,20,10,5,2,1元的數(shù)量依次為A,B,C,D,E,F,G，則根據(jù)貪心算法思想得到的解應(yīng)依次保證max（A），max（B），max（C），max（D），max（E），max（F），max（G）。假設(shè)存在更優(yōu)的算法，使得所用的紙幣數(shù)更少，即數(shù)量至少小于或等于A+B+C+D+E+F+G-1。那么在紙幣總數(shù)減少的情況下保證總額不變只能增大相對大面額紙幣的數(shù)量并減少小面額紙幣數(shù)量。而由貪心算法知max（A）已經(jīng)是最大的了，以此類推，max（B），max（C），max（D），max（E），max（F）均應(yīng)為最大數(shù)量了，所以貪心算法得到的解是最優(yōu)解，即滿足貪心選擇性質(zhì)。

綜上所述，人民幣找零問題滿足貪心算法。