算法 遞歸及分治 實驗

《算法 遞歸及分治 實驗》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、實驗一、遞規(guī)與分治算法班級：計072學號：3070911052姓名：趙凱一、實驗目的與實驗內容1．掌握遞歸與分治方法的基本設計思想與原則。2．二分法，漢諾塔問題，給定a，用二分法設計出求an的算法。二、實驗要求1．C++/C完成算法設計和程序設計并上機調試通過。2．撰寫實驗報告，提供實驗結果和數(shù)據(jù)。3．分析算法，要求給出具體的算法分析結果，包括時間復雜度和空間復雜度，并簡要給出算法設計小結和心得。三、程序實現(xiàn)二分法：在數(shù)組a[n]中找x，將n個元素分成個數(shù)大致相同的兩半，取an與x作比較。如果x=a，則找到x，算法中止；如果

2、xa[n/2]，則只要在數(shù)組a的右半部繼續(xù)搜索x。漢諾塔：n個盤子從a到b，可經由c。當n=1時，直接從a到b。當n>1時，將上邊n-1個盤子看成一個整體，從a移到輔助c上，最后一個移到b上。如此，對n-1個盤子使用同樣的移動規(guī)則從c移到b。至此，n個盤子的移動可以看成兩個n-1個圓盤移動的問題，這有可以遞歸使用上面的方法來做。a的n次冪：將指數(shù)n分解為n/2與n/2t同時遞歸的調用直至將n分解為一時返回時間復雜度：二分法：由于每執(zhí)行一次while循環(huán)，待搜索數(shù)組的長

3、度減少了一般，所以，在最壞情況下while被執(zhí)行了0(㏒n)次，循環(huán)體內運算需要0(1)次,因此整個算法在最壞情況下的時間復雜性為（㏒n）。漢諾塔：規(guī)模為n問題，可以分解為兩個規(guī)模為n-1的問題。所以T(n)=2*T(n-1)+1,所以漢諾塔的時間復雜度為0(2n)。a的n次冪：規(guī)模為n問題，可以分解為兩個規(guī)模為n/2的問題。所以T(n)=2*T(n/2)+1,所以漢諾塔的時間復雜度為0(n*㏒n)。四、心得體會這次的三個實驗總總體上來說，還是比較簡單。實驗過程比較簡單，然而前期工作卻不少，我認為這次試驗的關鍵就是如何分解問

4、題，如果相通了這個問題，那實驗就比較容易了。五、源程序清單（見附錄：源程序）。二分法：#includeusingnamespacestd;intbinarySearch(inta[],intx,intn);intmain(){intn;cout<<"inputthelengthofarry:";cin>>n;int*a=newint[n];cout<<"input"<>a[i];for(i=0;

5、i>x;if(binarySearch(a,x,n)!=-1)調用二分查找cout<

6、ight=n-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;//未找到x}漢諾塔：#include#includeusingnamespacestd;voidmove(chare,charf)//定義方向移動函數(shù){cout<"<

7、表示從e柱移動一個盤子到f柱}voidhanoi(intn,chara,charb,charc)//a初始柱，b目標柱，c中轉柱{if(n>0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,b,a,c);}}intmain(){intt;cout<<"輸入您要測試的次數(shù)t:";cin>>t;//測試次數(shù)for(intq=0;q>d;hanoi(d,'a','b','c');cout<<"TotalSteps:"<

8、(2.0,d)-1<usingnamespacestd;intpow(int,int);intmain(){inta,n,an,t;for(t=0;t<4;t++){cout<<"輸入底數(shù)a:"<