算法分析與設(shè)計實驗報告

《算法分析與設(shè)計實驗報告》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

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

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

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

4、采用了C++中的模板函數(shù)，將排序函數(shù)Sort和二分查找函數(shù)BinarySort寫為了模板函數(shù)，這樣不盡可以查找整數(shù)數(shù)組，也可以查找小數(shù)數(shù)組。由于查找的數(shù)組的長度不固定，所以我用了C語言中的malloc和realloc函數(shù)，時，在用realloc函數(shù)為數(shù)組再次分配空間。由于在隨機輸入一組數(shù)時不知在什么位置停止，所以在輸入完一組數(shù)之后，按Ctrl+Z鍵結(jié)束輸入，然后再用cin.clear()將輸入恢復(fù)，再繼續(xù)輸入。44?該算法的流程圖如下：44?調(diào)試結(jié)果44?實驗源程序代碼#include

5、>#include#includeusingnamespacestd;#defineN10//初始空間大小#definen10//增加空間大小templatevoidsort(Typea[],intnum){doubletemp;for(inti=1;i<=num-1;i++){for(intj=0;ja[j+1]){44temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}temp

6、lateintBinarySearch(Type*a,Typex,intm){intleft=0;intright=m-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;44}intmain(){int*a,num,length,i=0;a=(int*)malloc(s

7、izeof(int)*N);cout<<"請輸入一組數(shù)(Ctrl+z停止輸入)"<>a[i]){i++;if(i>=N){a=(int*)realloc(a,sizeof(int)*(length+n));length+=n;}}sort(a,i);for(intj=0;j>num;44if(BinarySearch(a,num,i)!

8、=-1){cout<>b[i1]){i1++;if(i1>=N){b=(double*