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

實(shí)驗(yàn)一分治與遞歸算法的應(yīng)用一、實(shí)驗(yàn)?zāi)康恼莆辗种嗡惴ǖ幕舅枷耄ǚ?治-合）、技巧和效率分析方法。熟練掌握用遞歸設(shè)計(jì)分治算法的基本步驟（基準(zhǔn)與遞歸方程）。學(xué)會(huì)利用分治算法解決實(shí)際問(wèn)題。實(shí)驗(yàn)內(nèi)容金塊問(wèn)題老板有一袋金塊（共n塊，n是2的幕（nN2）），最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設(shè)有一臺(tái)比較重量的儀器，希望用最少的比較次數(shù)找出最重和最輕的金塊。并對(duì)自己的程序進(jìn)行復(fù)雜性分析。問(wèn)題分析：一般思路：假設(shè)袋中有n個(gè)金塊?？梢杂煤瘮?shù)Max（程序1-31）通過(guò)n-1次比較找到最重的金塊。找到最重的金塊后，可以從余下的n-1個(gè)金塊中用類(lèi)似法通過(guò)n-2次比較找出最輕的金塊。這樣，比較的總次數(shù)為2n-3。分治法：當(dāng)n很小時(shí)，比如說(shuō)，nW2,識(shí)別出最重和最輕的金塊，一次比較就足夠了。當(dāng)n較大時(shí)（n〉2），第一步，把這袋金塊平分成兩個(gè)小袋A和B。第二步，分別找出在A和B中最重和最輕的金塊。設(shè)A中最重和最輕的金塊分別為HA與LA，以此類(lèi)推，B中最重和最輕的金塊分別為HB和LB。第三步，通過(guò)比較HA和HB，可以找到所有金塊中最重的；通過(guò)比較LA和LB，可以找到所有金塊中最輕的。在第二步中，若n〉2,則遞歸地應(yīng)用分而治之方法程序設(shè)計(jì)據(jù)上述步驟，可以得出程序14-1的非遞歸代碼。該程序用于尋找到數(shù)組w[0:n-1]中的最小數(shù)和最大數(shù)，若n<1，則程序返回false，否則返回true。當(dāng)nN1時(shí)，程序14-1給Min和Max置初值以使w[Min]是最小的重量，w[Max]為最大的重量。首先處理nW1的情況。若n>1且為奇數(shù)，第一個(gè)重量w[0]將成為最小值和最大值的候選值，因此將有偶，數(shù)個(gè)重量值w[1:n-1]參與for循環(huán)。當(dāng)n是偶數(shù)時(shí)，首先將兩個(gè)重量值放在for循環(huán)外進(jìn)行比較，較小和較大的重量值分別置為Min和Max，因此也有偶數(shù)個(gè)重量值w[2:n-1]參與for循環(huán)。在for循環(huán)中，外層if通過(guò)比較確定（w[i],w[i+1]）中的較大和較小者。此工作與前面提到的分而治之算法步驟中的2）相對(duì)應(yīng)，而內(nèi)層的if負(fù)責(zé)找出較小重量值和較大重量值中的最小值和最大值，這個(gè)工作對(duì)應(yīng)于3）。for循環(huán)將每一對(duì)重量值中較小值和較大值分別與當(dāng)前的最小值w[Min]和最大值w[Max]進(jìn)行比較，根據(jù)比較結(jié)果來(lái)修改Min和Max（如果必要）。源程序#include<iostream>#include<string.h>#include<algorithm>usingnamespacestd;0floatmax(floatg1,floatg2)//比較找大值(return(g1>g2?g1:g2);}floatmin(floatg1,floatg2)//比較找小值(return(g1<g2?g1:g2);}floatSearch_Max(floatg[],intleft,intright)//用二分法遞歸找最大值(if(left==right)〃當(dāng)只有一個(gè)數(shù)時(shí)，直接返回該值(floatmax;max=g[right];returnmax;}if(right-left==1)(floatLM,RM;LM=g[left];RM=g[right];return(max(LM,RM));}if(right-left>1)(floatLM,RM;intmid=(left+right)/2;//取中點(diǎn)LM=Search_Max(g,left,mid);RM=Search_Max(g,mid,right);//左半部分，右半部分的最大值比較找最大return(max(LM,RM));}floatSearch_Min(floatg[],intleft,intright)//用二分法遞歸找最小值(if(left==right)(floatmin;min=g[right];returnmin;}if(right-left==1)(floatLM,RM;LM=g[left];RM=g[right];return(min(LM,RM));}if(right-left>1)(floatLM,RM;intmid=(left+right)/2;LM=Search_Min(g,left,mid);RM=Search_Min(g,mid,right);//左半部分，右半部分的最小值比較找最小return(min(LM,RM));}}intmain()(floatgold[100];intn;cout<<"請(qǐng)輸入金塊的數(shù)目：";cin>>n;cout<<"請(qǐng)輸入各金塊的重量：";for(inti=0;i<n;i++)(cin>>gold[i];}cout<<"最重的金塊："<<Search_Max(gold,0,n-1)<<endl;cout<<"最輕的金塊："<<Search_Min(gold,0,n-1)<<endl;return0;實(shí)驗(yàn)結(jié)果輸入金塊數(shù)量：5得到最輕和最重的金塊?■Ei'dtl^WSXDebug\005."=E4RA7RilBt:Pressany夫七廿tocontinue.實(shí)驗(yàn)總結(jié)通過(guò)這次實(shí)驗(yàn)，我深刻了解到分治法的實(shí)用性，有效性。當(dāng)遇到規(guī)模較大的問(wèn)題，用我們以前學(xué)過(guò)的方法就太不明智了。將原問(wèn)題劃分成若干個(gè)較小規(guī)模的子問(wèn)題，再繼續(xù)求解，劃分，能夠簡(jiǎn)化問(wèn)題。遞歸法，是一個(gè)很重要的方法，具有結(jié)構(gòu)自相似的特性，剛開(kāi)始學(xué)習(xí)編寫(xiě)的時(shí)候遇到了很多問(wèn)題，不知道要找邊界，不知道如何劃分問(wèn)題。關(guān)于這次算法，我覺(jué)得，類(lèi)的部分還是一個(gè)難點(diǎn)，也就是說(shuō)，不會(huì)將問(wèn)題分解成抽象的概念，這也是我以后需要重點(diǎn)學(xué)習(xí)的地方。實(shí)驗(yàn)二動(dòng)態(tài)規(guī)劃算法的應(yīng)用一、實(shí)驗(yàn)?zāi)康恼莆談?dòng)態(tài)規(guī)劃算法的基本思想，包括最優(yōu)子結(jié)構(gòu)性質(zhì)和基于表格的最優(yōu)值計(jì)算方法。熟練掌握分階段的和遞推的最優(yōu)子結(jié)構(gòu)分析方法。學(xué)會(huì)利用動(dòng)態(tài)規(guī)劃算法解決實(shí)際問(wèn)題。二、實(shí)驗(yàn)內(nèi)容最長(zhǎng)單調(diào)遞增子序列問(wèn)題設(shè)計(jì)一個(gè)O(n2)復(fù)雜度的算法，找出由n個(gè)數(shù)組成的序列的最長(zhǎng)單調(diào)遞增子序列。思路分析1、把a(bǔ)1,a2,...,an排序，假設(shè)得到a'1,a'2,...,a'n,然后求a的a'的最長(zhǎng)公共子串，這樣總的時(shí)間復(fù)雜度為o(nlg(n))+o(nA2)=o(nA2)；2、動(dòng)態(tài)規(guī)劃的思路：另設(shè)一輔助數(shù)組b,定義b[n]表示以a[n]結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度，則狀態(tài)轉(zhuǎn)移方程如下：b[k]=max(max(b[j]la[j]<a[k],j<k)+1,1);(見(jiàn)狀態(tài)轉(zhuǎn)移方程)狀態(tài)轉(zhuǎn)移方程設(shè)輔助數(shù)組b[]，定義b[n]表示以a[n]結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度，狀態(tài)轉(zhuǎn)移方程表示為：b[k]=max(max(b[j]la[j]<a[k],j<k)+1,1)其中0<=k<=n-1，在a[k]前面找到滿足a[j]<a[k]的最大b[j]，a[k]作為后繼，得到a[k]的最長(zhǎng)遞增子序列的長(zhǎng)度，如果a[k]前面沒(méi)有更小的a[j]，此時(shí)a[k]形成序列，長(zhǎng)度為1，繼續(xù)計(jì)算，最后整個(gè)序列的最長(zhǎng)遞增子序列：max(b[k]|0<=k<=n-1)，此時(shí)時(shí)間復(fù)雜度仍為O(nA2)o另外定義一數(shù)組c，c中元素滿足c[b[k]]=a[k]，即當(dāng)遞增子序列的長(zhǎng)度為b[k]時(shí)子序列的末尾元素為c[b[k]]=a[k]o實(shí)現(xiàn)代碼第一種思路：#include<stdio.h>〃時(shí)間復(fù)雜度O(nA2)intmain()inti,j,k,n,a[100],b[100],c[100],max;while(scanf("%d",&n)!=EOF)(for(i=0;i<n;i++)scanf("%d",&a[i]);b[0]=1;//初始化，以a[0]結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度為1c[0]=a[0];k=1;for(i=1;i<n;i++)(b[i]=1;//b[i]最小值為1for(j=0;j<i;j++)if(a[i]>a[j]&&b[j]+1>b[i])(b[i]=b[i]+1;}}for(max=i=0;i<n;i++)//求出整個(gè)序列的最長(zhǎng)遞增子序列的長(zhǎng)度if(b[i]>max)max=b[i];printf("%d\n",max);

return0;}運(yùn)行結(jié)果實(shí)驗(yàn)總結(jié)通過(guò)實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的這個(gè)題目，對(duì)動(dòng)態(tài)規(guī)劃算法有了進(jìn)一步的了解。先分析問(wèn)題，判斷是否具有最優(yōu)子結(jié)果和重疊字問(wèn)題的性質(zhì)實(shí)驗(yàn)三貪心算法的應(yīng)用一、實(shí)驗(yàn)?zāi)康恼莆肇澬乃惴ǖ幕靖拍詈蛢蓚€(gè)基本要素熟練掌握貪心算法解決問(wèn)題的基本步驟。學(xué)會(huì)利用貪心算法解決實(shí)際問(wèn)題。二、實(shí)驗(yàn)內(nèi)容題目三：程序存儲(chǔ)問(wèn)題設(shè)有n個(gè)程序｛1,2,3,…,n｝要存放在長(zhǎng)度為L(zhǎng)的磁帶上。程序i存放在磁帶上的長(zhǎng)度是IflWiWn。要求確定這n個(gè)程序在磁帶上的一個(gè)存儲(chǔ)方案，使得能夠在磁帶上存儲(chǔ)盡可能多的程序。輸入數(shù)據(jù)中，第一行是2個(gè)正整數(shù)，分別表示程序文件個(gè)數(shù)和磁帶長(zhǎng)度L。接下來(lái)的1行中，有n個(gè)正整數(shù)，表示程序存放在磁帶上的長(zhǎng)度。輸出為最多可以存儲(chǔ)的程序個(gè)數(shù)。輸入數(shù)據(jù)示例650231388020輸出數(shù)據(jù)5三.題目分析：題目要求計(jì)算給定長(zhǎng)度的磁帶最多可存儲(chǔ)的程序個(gè)數(shù)，先對(duì)程序的長(zhǎng)度從小到大排序，再采用貪心算法求解。3、算法設(shè)計(jì)：定義數(shù)組a[n]存儲(chǔ)n個(gè)程序的長(zhǎng)度，s為磁帶的長(zhǎng)度；調(diào)用庫(kù)函數(shù)sort（a，a+n）對(duì)程序的長(zhǎng)度從小到大排序；函數(shù)most（）計(jì)算磁帶最多可存儲(chǔ)的程序數(shù)，采用while循環(huán)依次對(duì)排序后的程序長(zhǎng)度進(jìn)行累加，用i計(jì)算程序個(gè)數(shù)，用sum計(jì)算程序累加長(zhǎng)度（初始i=0，sum=0）：sum=sum+a[i]；若sum<=s，i加1，否則i為所求；i=n時(shí)循環(huán)結(jié)束；若while循環(huán)結(jié)束時(shí)仍有sum<=s，則n為所求。源程序：#include<iostream>usingnamespacestd；#include<algorithm>inta[1000000]；intmost(int*a,intn,ints){inti=0,sum=0；while(i<n){sum=a[i]+sum；if(sum<=s)i++；elsereturni；}returnn；}main(){inti,n,s；scanf("%d%d\n",&n,&s)；for(i=0；i