實(shí)驗(yàn)七 凸多邊形最優(yōu)三角剖分和圖像壓縮算法信科 李婕

實(shí)驗(yàn)序號：7

寧夏師范院數(shù)學(xué)與計(jì)機(jī)科學(xué)學(xué)院《計(jì)實(shí)驗(yàn)報(bào)實(shí)驗(yàn)項(xiàng)目名稱：凸多邊形最優(yōu)三角剖分和圖像壓縮算法學(xué)

號

23

姓

名

專業(yè)、

級科實(shí)驗(yàn)地318點(diǎn)

指導(dǎo)惠云師

時(shí)間

2010.5.15一、實(shí)目的及要求（1（2

掌握使用動(dòng)態(tài)規(guī)劃方法設(shè)計(jì)凸多邊最優(yōu)三角剖分問題的算法；掌握使用動(dòng)態(tài)規(guī)劃方法設(shè)計(jì)圖像壓縮問題的算法；二、實(shí)設(shè)備（環(huán)境及要求、環(huán)境要求：硬件：（PII以，以內(nèi)存特網(wǎng)接入；軟件：WindowsXP操系、VC++6.0編環(huán)境。、實(shí)驗(yàn)要求：獨(dú)完成實(shí)驗(yàn)，源代碼書寫規(guī)范；程運(yùn)行結(jié)果以屏幕截圖的方式粘貼在對應(yīng)位置，截圖必須清晰準(zhǔn)確；實(shí)完成后必須有實(shí)驗(yàn)結(jié)果的分析及本次實(shí)驗(yàn)的總結(jié)。三、實(shí)內(nèi)容與步驟(1)

設(shè)計(jì)求解凸多邊形最優(yōu)三角剖分問題的程序，并將凸多邊形最優(yōu)三角剖分所對應(yīng)的的弦的集合在屏幕上顯示。NminWeight(intm[][N],intintw(inti,intminWeight(intm[][N],ints[][N]){intn=N-1;inti,j,k,r,t;for(i=1;i<=n;i++)m[i][i]=0;for(for({/

jr+i-1;s[i][j]=i;for(k=i+1;k<j;k++){t=m[i][k]+m[k+1][j]+w(i-1,k,j);if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}intw(inti,ints[N][N]){intk;if(i==j);if(i+1==j);intmain(){inti,j;intV個(gè)頂點(diǎn)的坐標(biāo)",i);scanf("%d%d",&s[i][2]);}/

minWeight(p,m,s);最優(yōu)值:%d\n",m[1][N-1]);(2).設(shè)計(jì)求解圖像壓縮問題的程序，并將劃分的每個(gè)像素段所包含的像素個(gè)數(shù)、存儲(chǔ)每位像素的位數(shù)在屏幕上顯示。四、實(shí)結(jié)果與數(shù)據(jù)理1的果：五、分與討論1、分析凸多邊形最優(yōu)三角剖分問題相應(yīng)算法的時(shí)間復(fù)雜度。凸多邊形最優(yōu)三角剖分問題相應(yīng)算法的時(shí)間復(fù)雜度為O(n)。2.分析圖像壓縮問題相應(yīng)算法的時(shí)間復(fù)