算法實驗報告

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

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