分治算法實(shí)驗(yàn)(用分治法查找數(shù)組元素的最大值和最小值)(已修改)
2025-04-28 23:42 本頁(yè)面
【正文】 算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告第 一 次實(shí)驗(yàn)姓名學(xué)號(hào)班級(jí)時(shí)間地點(diǎn)工訓(xùn)樓309 實(shí)驗(yàn)名稱分治算法實(shí)驗(yàn)（用分治法查找數(shù)組元素的最大值和最小值）實(shí)驗(yàn)?zāi)康耐ㄟ^上機(jī)實(shí)驗(yàn)，要求掌握分治算法的問題描述、算法設(shè)計(jì)思想、程序設(shè)計(jì)。實(shí)驗(yàn)原理使用分治的算法，根據(jù)不同的輸入用例，能準(zhǔn)確的輸出用例中的最大值與最小值。并計(jì)算出程序運(yùn)行所需要的時(shí)間。程序思路：利用分治法，將一個(gè)數(shù)組元素大于2的數(shù)組分成兩個(gè)子數(shù)組，然后對(duì)每一個(gè)子數(shù)組遞歸調(diào)用，直到最小的子數(shù)組的元素個(gè)數(shù)為1個(gè)或者是2個(gè)，此時(shí)直接就能得出最大值與最小值，然后合并子數(shù)組，比較2個(gè)子數(shù)組的最大值與最小值，依次進(jìn)行下去，知道找到整個(gè)數(shù)組的最大值與最小值。實(shí)驗(yàn)步驟1. 先解決小規(guī)模的問題， 如數(shù)組中只有 1 個(gè)元素或者只有兩個(gè)元素時(shí)候 的情況。2. 將問題分解，如果數(shù)組的元素大于等于 3 個(gè)，將數(shù)組分為兩個(gè)小的數(shù) 組。3. 遞歸的解各子問題，將中分解的兩個(gè)小的數(shù)組再進(jìn)行以上兩個(gè)步驟最后都化為小規(guī)模問題。4. 將各子問題的解進(jìn)行比較最終得到原問題的解。關(guān)鍵代碼//分治法處理整個(gè)數(shù)組，求出最大值與最小值void merge(int a[],int left,int right,int amp。Max,int amp。Min){ int max1=0,min1=0,max2=0,min2=0。 if(rightleft2) //當(dāng)數(shù)組中元素個(gè)數(shù)大于3時(shí)，才實(shí)行分治法 { int mid=(right+left)/2。 merge(a,left,mid,max1,min1)。 //左半邊遞歸調(diào)用自身，求出最大值與最小值，分別保存在max1,min1中 merge(a,mid+1,right,max2,min2)。//右半邊遞歸調(diào)用自身，求出最大值與最小值，分別
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1