動態(tài)規(guī)劃算法實驗報告(編輯修改稿)
2025-08-18 00:25 本頁面
【文章內(nèi)容簡介】 a,c)。}bool JudgeInput()//判斷是否能構(gòu)成凸多邊形{ point *v。 //記錄凸多邊形各頂點坐標 int *total。 //記錄坐標在直線方程中的值 int m,a,b,c。 cout請輸入凸多邊形頂點個數(shù)：。 cinm。 int M = m1。 for(int i=0 。 im 。 i++) { cout輸入頂點vi的坐標：。 cinv[i].xv[i].y。 } //根據(jù)頂點坐標判斷是否能構(gòu)成一個凸多邊形 for(int j=0 。 jm 。 j++) { int p = 0。 int q = 0。 if(m1 == j) { a = v[m1].y v[0].y。 b = v[m1].x v[0].y。 c = b * v[m1].y a * v[m1].x。 } else { a = v[j].y v[j+1].y。 b = v[j].x v[j+1].x。 c = b * v[j].y a * v[j].x。 } for(int k=0 。 km 。 k++) { total[k] = a * v[k].x b * v[k].y + c。 if(total[k] 0) { p = p+1。 } else if(total[k] 0) { q = q+1。 } } if((p0 amp。amp。 q0) || (p==0 amp。amp。 q==0)) { cout無法構(gòu)成凸多邊形！endl。 exit(1)。 } }}bool minWeightTriangulation()//計算最優(yōu)值算法{ int M。 int **t, **s。 point *v。 for(int i=1 。 i=M 。 i++) t[i][i] = 0。 for(int r=2 。 r=M 。 r++) for(int i=1 。 i=Mr+1 。 i++) { int j = i+r1。 t[i][j] = t[i+1][j] + w(v[i1],v[i],v[j])。 s[i][j] = i。 for(int k=i+1 。 ki+r1 。 k++) { int u = t[i][k] + t[k+1][j] + w(v[i1],v[k],v[j])。 if(u t[i][j]) { t[i][j] = u。 s[i][j] = k。 } } } return true。}void Traceback(int i, int j, int **s){ if(i == j) return。 Traceback(i,s[i][j],s)。 Traceback(s[i][j]+1,j,s)。 cout三角形：vi1vs[i][j]vjendl。}int main(){ int **s。 //記錄最優(yōu)三角剖分中所有三角形信息 int **t。 //記錄最優(yōu)三角剖分所對應的權(quán)函數(shù)值 point *v。 //記錄凸多邊形各頂點坐標 int *total。 //記錄坐標在直線方程中的值 int M=0。 t = new int *[N]。 s = new int *[N]。 for(int i=0 。 iN 。 i++) { t[i] = new int[N]。 s[i] = new int[N]。 } v = new point[N]。 total = new int[N]。 if(JudgeInput()) { if(minWeightTriangulation()) { Traceback(1,M,s)。 coutendl。 cout最優(yōu)權(quán)值之和為：t[1][M]endl。 } }
公司管理相關(guān)推薦
鄂ICP備17016276號-1