實(shí)驗(yàn) 分治法算法設(shè)計(jì)

《實(shí)驗(yàn) 分治法算法設(shè)計(jì)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、《算法分析與設(shè)計(jì)》實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)2分治法算法設(shè)計(jì)姓名XXX學(xué)號(hào)XXX班級(jí)XXXXXX時(shí)間：XXXX-XX-XX地點(diǎn)：XXX同組人：無(wú)指導(dǎo)教師：XXX實(shí)驗(yàn)?zāi)康腶)掌握分治法算法設(shè)計(jì)的一般思想和方法。b)理解并掌握二分查找、歸并分類(lèi)、快速分類(lèi)算法。c)能熟練運(yùn)用分治法求解問(wèn)題。d)實(shí)驗(yàn)中所準(zhǔn)備的數(shù)據(jù)是有代表性的。實(shí)驗(yàn)內(nèi)容a)寫(xiě)一個(gè)順序查找算法，將其與二分查找算法一起轉(zhuǎn)換成程序，上機(jī)驗(yàn)證。b)選擇不同規(guī)模的數(shù)據(jù)集運(yùn)行上二程序，統(tǒng)計(jì)它們的時(shí)間開(kāi)銷(xiāo)并比較。c)歸并分類(lèi)、快速分類(lèi)算法轉(zhuǎn)換成程序并驗(yàn)證之。d)選擇不同規(guī)模的數(shù)據(jù)集運(yùn)行上二程序，統(tǒng)計(jì)它們的時(shí)間開(kāi)銷(xiāo)并比較。e

2、)準(zhǔn)備一定規(guī)模的數(shù)據(jù)集用于實(shí)驗(yàn)。此數(shù)據(jù)集越大越有得于驗(yàn)證算法，可以考慮最終的數(shù)據(jù)個(gè)數(shù)超過(guò)10000個(gè)。f)編寫(xiě)歸并分類(lèi)、快速分類(lèi)程序，將上數(shù)據(jù)集中的數(shù)據(jù)分類(lèi)?？梢允褂幂^少的數(shù)據(jù)調(diào)試程序時(shí)。g)用規(guī)模從小到大的數(shù)據(jù)集運(yùn)行上述程序，統(tǒng)計(jì)它們的運(yùn)行時(shí)間，并作對(duì)比分析。h)編寫(xiě)順序查找、二分查找程序。i)將查找程序與分類(lèi)程序結(jié)合起來(lái)，用不同規(guī)模的數(shù)據(jù)集運(yùn)行，統(tǒng)計(jì)程序運(yùn)行時(shí)間。實(shí)驗(yàn)環(huán)境硬件：Intel(R)Pentium(R)CPURAM:4G軟件：Myeclipse2013實(shí)驗(yàn)前準(zhǔn)備1、算法設(shè)計(jì)：（1）分治策略的抽象化控制ProcedureDANDC(p,q)1

3、8Globaln,A(1:n);integerm,p,q//1≤p≤q≤n//IfSMALL(p,q)Thenreturn(G(p,q))Elsem←DIVIDE(p,q)//p≤m＜q//Return(COMBINE(DANDC(p,m),DANDC(m+1,q)))EndifendDANDC（2）二分檢索算法ProcedureBINSRCH(A,n,x,j)//給定一個(gè)按非降次序排列的元素?cái)?shù)組A(1:n)，n≥1，判斷x是否出現(xiàn)。////若是，置j，使得x=A(j)，若非，j=0//Integerlow,high,mid,j,n;low←1;high

4、←nwhilelow≤highdomid←int((low+high)/2)case:xA(mid):low←mid+1:else:j←mid;returnEndcaseRepeatj←0endBINSRCH（3）歸并分類(lèi)算法ProcedureMERGESORT(low,high)//A(low:high)是一個(gè)全程數(shù)組，它含有high-low+1≥0個(gè)待分類(lèi)的元素//Integerlow,high;Iflow

5、SORT(low,mid)//將一個(gè)子集合分類(lèi)//callMERGESORT(mid+1,high)//將另一個(gè)子集合分類(lèi)//CALLMERGE(low,mid,high)//歸并兩個(gè)已分類(lèi)的子集合//EndifendMERGESORTProcedureMERGE(low,mid,high)//A(low:high)是一個(gè)全程數(shù)組，它含有兩個(gè)放在A（low:mid）和A（mid+1:high）中的已分類(lèi)的子集合。目標(biāo)是將這兩個(gè)已分類(lèi)的集合歸并成一個(gè)集合，并存放到A(low:high)中////使用一個(gè)輔助數(shù)組B(low:high)//Integerh,I

6、,j,k,low,mid,high;//low≤midmidthenfork←jtohighdo//處理剩余的元素//B(i)←A(k);i←i+1repeatElsefork←htomiddoB(i)←A(k);i←i+1

7、repeatendiffork←lowtohighdo//將已歸并的集合復(fù)制到A//A(k)←B(k)repeatendMERGE（4）改進(jìn)的歸并分類(lèi)算法ProcedureMERGESORT1(low,high,p)//利用輔助數(shù)組LINK(low:high)將全程數(shù)組A(low:high)按降序分類(lèi)。LINK中的值表示按分類(lèi)次序給出A的下標(biāo)的表，并把p置于指示這表的開(kāi)始處//GlobalA(low:high),LINK(low:high)Ifhigh-low+1<16ThencallINSERTIONSORT(A,LONK,low,high,p)Els

8、emid←int((low+high)/2)callMERGESORT(low,