試驗二貪心算法_第1頁
試驗二貪心算法_第2頁
試驗二貪心算法_第3頁
試驗二貪心算法_第4頁
試驗二貪心算法_第5頁
已閱讀5頁,還剩4頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)

文檔簡介

1、華東師范大學(xué)計算機科學(xué)技術(shù)系學(xué)生上機實踐報告華東師范大學(xué)計算機科學(xué)技術(shù)系上機實踐報告第9頁共9頁課程名稱:算法設(shè)計與分析指導(dǎo)教師:柳銀萍上機實踐名稱:貪心算法上機實踐編號:NO.2年級:05姓名:張翡翡學(xué)號:組號:05上機實踐成績:10052130119 上機實踐日期:2007-4-10上機實踐時間:10:00-11:30、目的了解熟悉掌握貪心算法實質(zhì)并學(xué)會靈活運用,從而解決生活中一些實際問題。二、內(nèi)容與設(shè)計思想1. 超市的自動柜員機(POS)要找給顧客各種數(shù)值的現(xiàn)金,表面上看,這是一個很簡單的任 務(wù),但交給機器辦就不簡單了。你作為一個計算機專家,要求寫一個程序來對付這個“簡 單”的問題。你的

2、自動柜員機有以下的幣種:100元,50元,20元,10元,5元,2元,1元。你可以 假設(shè)每種錢幣的數(shù)量是無限的?,F(xiàn)在有一筆交易,需要找個客戶m元,請你設(shè)計一個算法,使得找給顧客的錢幣張數(shù)最少。要求:輸入:第一行僅有一個整數(shù)n(0<n<=10000),表示有幾組測試數(shù)據(jù)。每組測試數(shù)據(jù)僅有一 行,每行只有一個整數(shù) m(0<m<2000000000),表示需要找的錢幣數(shù)。(提示:對丁大量的輸出,請使用 scanf不要使用cin)輸出:每組測試數(shù)據(jù)輸出一行,每行有7個整數(shù)(兩兩之間有一個空格,結(jié)尾不能有空 格),表示100元,50元,20元,10元,5元,2元,1元所需要的張數(shù)

3、。1.1其思路是:1) 定義相關(guān)變量;2) 接收相關(guān)數(shù)據(jù),如測試數(shù)據(jù)組數(shù) n和要找的錢幣數(shù);3) 依次考慮100, 50, 20, 10, 5, 2, 1的需要找的錢幣張數(shù),用最簡單的加減乘除;4) 輸出其值。1.2具體算法是:while(n-)m 輸入a=m/100b=(m-100*a)/50c=(m-100a-50b)/20d=(m-100a-50b-20c)/10e=(m-100a-50b-20c-10d)/5f=(m-100a-50b-20c-10d-5e)/2g=m-100a-50b-20c-10d-5e-2fend while2. 若在0-1背包問題中各物品是依重量遞增排列時,其價

4、值恰好依遞減序排列。對這個特殊 的0-1背包問題,請設(shè)計一個有效算法找出最優(yōu)解,并證明算法的正確性。要求:輸入:輸入只有四行,第一行有一個正數(shù) n (n <= 10000)為物品的數(shù)量。第二行有n 個遞增的整數(shù)表示每一個物品的重量。第三行有 n個遞減的整數(shù),表示每個物品的價值。最 后一行有一個整數(shù)w表示背包的容量。所有數(shù)據(jù)均小于 1000000。輸出:輸出背包可帶走物品的最大價值。2.1其思路是:1)定義相關(guān)變量及賦初值;2)接收相關(guān)數(shù)據(jù)如物品的數(shù)量,每個物品的重量及每個物品的價值,以及背包的容量;3)寫兩個排序函數(shù),一個遞增一個遞減;4)用一個循環(huán)判斷裝進的重量是否超過背包容量;5)最

5、后輸出所裝下的容量大小。2.2具體算法是:n輸入for i 0 to nai輸入for i 0 to nbi輸入w輸入k ifor i 0 to nfor j i+1 to n if ak>aj then k=j t=ai ai=ak ak=tk ifor i 0 to nfor j i+1 to n if bk<bj then k=j t=bi bi=bk bk=tfor i 0 to nmax+=aiif max<=w then sum+=bi return(0)2.3算法的正確性證明:3. 一輛汽車加滿油后可行駛 n公里。旅途中有若十個加油站。設(shè)計一個有效算法,指出應(yīng)

6、在哪些加油站??考佑?,使沿途加油次數(shù)最少。對于給定的 n(n <= 5000)和k(k <= 1000)個 加油站位置,編程計算最少加油次數(shù)。要求:輸入:第一行有2個正整數(shù)n和k,表示汽車加滿油后可行駛n公里,且旅途中有k個 加油站。接下來的1行中,有k+1個整數(shù),表示第k個加油站與第k-1個加油站之間的距 離。第0個加油站表示出發(fā)地,汽車已加滿油。第 k+1個加油站表示目的地。輸出:輸出編程計算出的最少加油次數(shù)。如果無法到達目的地,貝U輸出” NoSolution?!?.1其思路是:1) 定義相關(guān)變量及賦初值;2) 接收相關(guān)數(shù)據(jù)如加滿油能行駛的距離,加油站個數(shù)和各加油站之間的距離

7、;3) 考慮特殊情況:(1) 如果起點到第一個加油站距離大于加滿油時能行駛距離,則輸出“No Solution!"(2) 如果七次加滿油和起始站加滿油之和能行駛距離小于起點到終點距離,貝U輸出“ No Solution"4) for循環(huán)處理各個站情況,如果剩余的油能行駛的距離大于到下一個站的距離,則不用再 加低如果剩余的油能行駛的距離小于到下一個站的距離,則加滿油,如果加滿油還是小于 則輸出“No Solution”,否則使計數(shù)m加一;5) 最后輸出m的值。3.2具體算法是:n輸入k輸入for i 0 to kai輸入sum+=aiif n<a0 then print

8、f(No Solution!)else if n*(k+1)<sum then printf(No Solution!)elseleft=n-a0for i 1 to kif left>ai then left-=ai elset=n+leftif t<ai then printf(No Solution!) elseleft=t-ai m+=1 printf(m)return(0)三、使用環(huán)境Microsoft visual C+ 6.0四、調(diào)試過程1. 有時候太大意,第一次調(diào)試時居然忘了打“ * ”符號,導(dǎo)致出現(xiàn)一大堆錯誤,我用的 是最笨的辦法來算錢幣數(shù),其實知道還有更優(yōu)

9、的方法去解決,之后還可以再研究研究,還出現(xiàn)一個問題就是粗心,“ /”號打成“”號導(dǎo)致結(jié)果錯誤甚至出現(xiàn)一堆亂碼 類東西。2. 做第二個程序基本沒什么大問題,只是剛開始的時候排序函數(shù)沒有單獨寫出來導(dǎo)致測 試不正確,還有一開始沒有在 main()函數(shù)中定義調(diào)用的兩個排序函數(shù),最粗心的是將 兩個函數(shù)相反了一下,即把重量按升序排,價值按減序排導(dǎo)致結(jié)果很離譜。還有一個 問題是最后一個for語句判斷重量有沒有超過背包總重量時只是加出來總重量,即在 bi的地方寫成了 ai,不過好在都是小錯誤。3. 第三個程序很順利,只是在審題的時候考慮地太過復(fù)雜,考慮了比如現(xiàn)在第一個站它能開到第二個站,但是第二個站到第三個站

10、即使加滿油也不能開到的時候,我再考慮 是不是該在第一個站加上油這樣就能夠從第二站到第三站,問題就變得復(fù)雜多了。調(diào) 試過程只有一個地方出現(xiàn)問題就是考慮了剩余油能行駛距離如果小于接下來要行駛的 距離,而忘了處理如果剩余油大于接下來能行駛距離情況下的left的值的改變。經(jīng)過一步一步調(diào)試而處理好。五、總結(jié)基礎(chǔ)雖然簡單但有時候還是要掌握牢固才好,粗心有時候會耽誤很多不必要的時 間要盡量克服,在寫程序的時候認(rèn)真才行。有時候還是不能偷懶,要盡量想想其他更優(yōu)的方法,比如第一個程序我用的就是 最笨最原始的方法,很顯然復(fù)雜度可能就大了?;A(chǔ)不扎實,在調(diào)用函數(shù)的時候在開頭沒有定義,不過經(jīng)同學(xué)指點就可以改,應(yīng) 該學(xué)會

11、更深一層思考以及用多種不同的方法實現(xiàn),比如排序方法有很多種,可以 借此機會多思考采用各種排序方法,從而鞏固了以前的知識。考慮問題要全面,雖然有時候會將問題復(fù)雜化但是至少思考過程能學(xué)到很多東 西,這樣會使邏輯越來越嚴(yán)謹(jǐn)。六、附錄1.找零錢問題的程序:(此處放程序)#include<stdio.h>int main()(int a,b,c,d,e,f,g,n,m;scanf("%d",&n);while(n-)(scanf("%d",&m);a=m/100;b=(m-100*a)/50;c=(m-100*a-50*b)/20;d=

12、(m-100*a-50*b-20*c)/10;e=(m-100*a-50*b-20*c-10*d)/5;f=(m-100*a-50*b-20*c-10*d-5*e)/2;g=m-100*a-50*b-20*c-10*d-5*e-2*f;printf("%d %d %d %d %d %d %dn”,a,b,c,d,e,f,g);return(0);運行結(jié)果:-飛:羽淇的艾檔'算法設(shè)計與分析'程序作業(yè)Delm八1103.即/口 xL6s e i 1 s i湖fpess Itey to continue2. 0-1背包問題的程序:(此處放程序)#include<std

13、io.h> int main() (void sort1(int a10000,int n); void sort2(int b10000,int n); int a10000,b10000;int w,i,n;int max=0;int sum=0;scanf("%d”,&n);for(i=0;i<n;i+)scanf("%d",&ai);for(i=0;i<n;i+) scanf("%d",&bi);scanf("%d",&w);sort1(a,n);sort2(b,n)

14、;for(i=0;i<n;i+)(max+=ai;if(max<=w) sum+=bi;printf("%dn”,sum); return(0);void sort1(int a10000,int n)(int i,j,k;int t;for(i=0;i<n;i+)(k=i;for(j=i+1;j<n;j+) if(ak>aj)k=j; t=ai;ai=ak; ak=t;void sort2(int b10000,int n)(int i,j,k;int t;for(i=0;i<n;i+)(k=i;for(j=i+1;j<n;j+) if(b

15、k<bj)k=j; t=bi; bi=bk; bk=t;運行結(jié)果:二羽淇的文檔'算法云計與分析'程序作業(yè)312 33 2 145Pi'ess k號y to continue3.汽車加油問題的程序:(此處放程序)#include<stdio.h> int main() (int n,k,i,left;int a1025;int sum=0;int m=0;int t=0;scanf("%d",&n);scanf("%d",&k);for(i=0;i<=k;i+)(scanf("%d",&ai);sum+=ai;if(n<a0)printf("No Solution!");elseif(n*(k+1)<sum)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論