分治與遞歸算法實驗

1、實驗二 分治與遞歸算法的應用 一、實驗目的1掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。2熟練掌握用遞歸設計分治算法的基本步驟（基準與遞歸方程）。3學會利用分治算法解決實際問題。二、實驗內(nèi)容 1.問題描述：題目一：線性時間選擇給定n個元素和一個整數(shù)k，要求用O(n)時間找出這n個元素中第k小元素。題目二：金塊問題老板有一袋金塊（共n塊，n是2的冪（n2）,最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設有一臺比較重量的儀器，希望用最少的比較次數(shù)找出最重和最輕的金塊。并對自己的程序進行復雜性分析?！据斎胼敵鰳永款}目三：求最大兩個數(shù)和最小兩個數(shù)利用分治法求一組數(shù)據(jù)

2、中最大的兩個數(shù)和最小的兩個數(shù)。2.數(shù)據(jù)輸入：個人設定，由鍵盤輸入。3.要求：1）上述題目任選其二。上機前，完成程序代碼的編寫2）獨立完成實驗及實驗報告三、實驗步驟1.理解算法思想和問題要求；2.編程實現(xiàn)題目要求；3.上機輸入和調(diào)試自己所編的程序；4.驗證分析實驗結(jié)果；5.整理出實驗報告。一實驗目的二問題描述三算法設計包含：數(shù)據(jù)結(jié)構(gòu)與核心算法的設計描述、函數(shù)調(diào)用及主函數(shù)設計、主要算法流程圖等1. 金塊問題： 考慮到可能輸入數(shù)據(jù)有一個或者兩個這種情況，所以解決問題時分三種情況考慮，然后通過函數(shù)調(diào)用來實現(xiàn)尋找最大最小的數(shù)值。 復雜性分析：當n是2的冪時，即對于某個正整數(shù)k，n等于2的k次方，可以證明

3、，任何以元素比較為基礎的找最大和最小元素的算法，其元素比較下界均為3n/2-2次。因此，過程maxmin在這種意義上是最優(yōu)的。T(n)=2T(n/2)+2Main函數(shù)循環(huán)讀入數(shù)據(jù)輸入金塊數(shù)量調(diào)用maxmin函數(shù)輸出結(jié)果2. 最大最小兩個數(shù)：與金塊問題類似，這是尋找最大最小的兩個數(shù)。利用循環(huán)嵌套條件語句進行判斷，選擇出最大最小的兩個數(shù)。Main函數(shù)輸入相關(guān)數(shù)據(jù)調(diào)用_maxmin函數(shù)利用條件語句進行判斷返回max min輸出結(jié)果四.程序調(diào)試及運行結(jié)果分析1) 有五個金塊，其重量分別為2.3，1.3 ，6.9， 2， 1成功運行程序后輸出最重和最輕的金塊的重量。2) 如下圖所示，輸入六個數(shù)分別為：5

4、,9,12,3,16,2 成功運行后，輸出最大的2個元素16，12最小的2個元素2,3。五.實驗總結(jié)通過本次實驗，我學會了如何運用分治法將整個問題分解成若干個小問題后分而治之，使其產(chǎn)生出方便求解的子問題，必要時逐步合并這些子問題的解，從而得到問題的解。在實驗中我觀察了相關(guān)算法結(jié)合老師上課講解的，我覺得這類問題實際可以用一個遞歸方程來表示，通過遞歸逐步求解問題。同時，通過本次實驗我也發(fā)現(xiàn)遞歸算法的重要性，自己對遞歸算法還不能熟練的應用。所以，在課下我會繼續(xù)努力掌握這種算法，以便能在以后熟練的應用它。通過第三題明白了眼過千變不如手動一遍,上課是聽懂了.課下我又仔細的上網(wǎng)看了研究了一下,但是今天敲出

5、來還是有一些問題,我覺得一些問題是值得注意的.附錄：程序清單 （程序過長，可附主要部分）1) 金塊問題程序如下：#include<iostream>using namespace std;int i,n;float a100;void maxmin(int i,int j,float &fmax,float &fmin) int mid;float lmax,lmin,rmax,rmin;if(i=j)fmax=ai;fmin=ai;else if(i=j-1)if(ai<aj)fmax=aj;fmin=ai;else fmax=ai;fmin=aj;else

6、mid=(i+j)/2;maxmin(i,mid,lmax,lmin);maxmin(mid+1,j,rmax,rmin);if(lmax>rmax)fmax=lmax;elsefmax=rmax;if(lmin>rmin)fmin=rmin;elsefmin=lmin;int main()cout<<"請輸入金塊的數(shù)量："<<endl;cin>>n;cout<<"請輸入"<<n<<"塊金子的重量"<<endl;for(i=1;i<=

7、n;i+)cin>>ai;float max,min;maxmin(1,n,max,min);cout<<"最重金塊是"<<max<<" "<<"最輕金塊是"<<min<<endl;return 0;2) 求最大兩個數(shù)和最小兩個數(shù)#include<iostream>using namespace std; int a100; void _maxmin(int i,int j,int *max1,int *min1,int *max2,int

8、 *min2) int max,min,minmax,minmin; if(i=j) *max1=*min1=*min2=*max2=ai; else if(i=j-1) if(ai<aj) *max1=*min2=aj;*min1=*max2=ai; else *max1=*min2=ai;*min1=*max2=aj; else int m=(i+j)/2; _maxmin(i,m,max1,min1,max2,min2);_maxmin(m+1,j,&max,&min,&minmax,&minmin);if(*max1<max) *max2=*

9、max1;*max1=max;if(max!=minmax) if(*max2<minmax) *max2=minmax; else if(*max2<max) *max2=max; if(*min1>min) *min2=*min1; *min1=min; if(min!=minmin) if(*min2>minmin) *min2=minmin; else if(*min2>min) *min2=min; int main() int n,i,m,max2,min2; cout<<"你要輸入幾個數(shù)？"<<endl;cin>>n; cout<<"請分別輸入："<<endl;for(i=0;i<n;i+) cin>>m; ai=m; _maxmin(0,n-1,&max0,&min0,&max1,&min1); cout<<"輸入的數(shù)中最大的2個元素為："<<max0