資源描述:
《算法分析與設(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?實驗源程序代碼#include5、>#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*