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

《算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告學(xué)院：　信息科學(xué)與工程學(xué)院專業(yè)班級(jí)：　物聯(lián)網(wǎng)工程1201班　指導(dǎo)老師：　　　李敏學(xué)號(hào)：　　090912090241姓名：　　　姚洪齊目錄實(shí)驗(yàn)一遞歸與分治.............................3二分查找..........................3快速排序..........................9實(shí)驗(yàn)二回溯算法................................1301背包問題......................13實(shí)驗(yàn)三動(dòng)態(tài)規(guī)劃....................

2、...........2441最長(zhǎng)子序列問題......................24矩陣連乘問題........................2741實(shí)驗(yàn)一遞歸與分治l實(shí)驗(yàn)?zāi)康睦斫膺f歸算法的思想和遞歸程序的執(zhí)行過程，并能熟練編寫遞歸程序。掌握分治算法的思想，對(duì)給定的問題能設(shè)計(jì)出分治算法予以解決。l實(shí)驗(yàn)預(yù)習(xí)內(nèi)容編程實(shí)現(xiàn)講過的例題：二分搜索、合并排序、快速排序。對(duì)本實(shí)驗(yàn)中的問題，設(shè)計(jì)出算法并編程實(shí)現(xiàn)。l試驗(yàn)內(nèi)容和步驟1.二分查找?實(shí)驗(yàn)內(nèi)容在對(duì)線性表的操作中，經(jīng)常需要查找某一個(gè)元素在線性表中的位置。此問題的輸入是待查元素x和線性表L，輸出為x在

3、L中的位置或者x不在L中的信息。?實(shí)驗(yàn)要求二分搜索方法充分利用了元素間的次序關(guān)系，采用分治策略，可在最壞情況下用O(logn)時(shí)間完成搜索任務(wù)。?算法分析二分查找的基本思路是將n個(gè)元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x，算法終止；如果xa[n/2]，則只要在數(shù)組a的右半部分繼續(xù)搜索x。由于二分查找的數(shù)組不一定是一個(gè)整數(shù)數(shù)組，所以我采用了C++中的模板函數(shù)，將排序函數(shù)Sort和二分查找函數(shù)BinarySort寫為了模板函數(shù)，這樣不盡可以查找整數(shù)數(shù)組

4、，也可以查找小數(shù)數(shù)組。由于查找的數(shù)組的長(zhǎng)度不固定，所以我用了C語言中的malloc和realloc函數(shù)，時(shí)，在用realloc函數(shù)為數(shù)組再次分配空間。由于在隨機(jī)輸入一組數(shù)時(shí)不知在什么位置停止，所以在輸入完一組數(shù)之后，按Ctrl+Z鍵結(jié)束輸入，然后再用cin.clear()將輸入恢復(fù)，再繼續(xù)輸入。41?該算法的流程圖如下：41?調(diào)試結(jié)果41?實(shí)驗(yàn)源程序代碼#include#include#includeusingnamespacestd;#defineN10//初始空間大小#definen10

5、//增加空間大小templatevoidsort(Typea[],intnum){doubletemp;for(inti=1;i<=num-1;i++){for(intj=0;ja[j+1]){41temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}templateintBinarySearch(Type*a,Typex,intm){intleft=0;intright=m-1;while(left<=right){intmiddle=(le

6、ft+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;}41intmain(){int*a,num,length,i=0;a=(int*)malloc(sizeof(int)*N);cout<<"請(qǐng)輸入一組數(shù)(Ctrl+z停止輸入)"<>a[i]){i++;if(i>=N){a=(int*)realloc(a,sizeof(int)*(length+n));length+=n

7、;}}sort(a,i);for(intj=0;j>num;if(BinarySearch(a,num,i)!=-1){41cout<

8、le)*N);cout<<"請(qǐng)輸入一組數(shù)"<>b[i1]){i1++;if(i1>=N){