答案及解析：[问答题]阅读下列说明和C代码，回答问题1和问题2，将解答填入答题纸的对应栏内。[说明]凸多边形是指多边形的任意两点的连线均落在多边形的边界或者内部。相邻的点连线落在多边形边上，称为边，不相邻的点连线落在多边形

问题：

[问答题] 阅读下列说明和C代码，回答问题1和问题2，将解答填入答题纸的对应栏内。[说明]凸多边形是指多边形的任意两点的连线均落在多边形的边界或者内部。相邻的点连线落在多边形边上，称为边，不相邻的点连线落在多边形内部。称为弦。假设任意两点连线上均有权重，凸多边形最优三帮剂分问题定义为：求将凸多边形划分为不相交的三角形集合，且各三角形权重之和最小的剖分方案。每个三角形的权重为三条边权重之和。假设N个点的凸多边形点编号为V1,V2,……,VN,若在VK处将原凸多边形划分为一个三角形V1VkVN，两个子多边形V1,V2,…,Vk和Vk,Vk+1,…VN，得到一个最优的剖分方案，则该最优剖分方案应该包含这两个子凸边形的最优剖分方案。用m[i][j]表示带你Vi-1,Vi,…Vj构成的凸多边形的最优剖分方案的权重，S[i][j]记录剖分该凸多边形的k值。中级软件设计师,历年真题,2021年上半年（下午）《软件设计师》真题

其中：Wj,i-1分别为该三角形三条边的权重。求解凸多边形的最优剖分方案，即求解最小剖分的权重及对应的三角形集。[C代码]#include#define N 6//凸多边形规模int m[N+1] [N+1]; //m[i][j]表示多边形Vi-1到Vj最优三角剖分的权值int S[N+1] [N+1]; //S[i][j]记录多边形Vi-1 到Vj最优三角剖分的k值int W[N+1] [N+1]; //凸多边形的权重矩阵，在main函数中输入/*三角形的权重a，b，c，三角形的顶点下标*/int get_ triangle_weight(int a，int b，int c){return W[a][b]+W[b][c]+W[c][a];}/*求解最优值*/void triangle_partition(){int i,r,k,j;int temp;/*初始化*/for(i=1;i＜=N;i++){m[i][i]=0;}/*自底向上计算m，S*/for(r=2;(1);r++){/*r为子问题规模*/ //r＜=Nfor(i=1;k＜=N-r+1;i++){(2); //int j=i+r-1m[i][j]= m[i][j]+m[i+1][j]+get_triangle_weight(i-1,i,j); /*k=j*/S[i][j]=i;for(k=j+1;ktemp=m[i][k]+m[k+1][j]+ge_triangle_ weight(i-1,k,j);if((3)){/*判断是否最小值*/ //tempm[i][j]=temp;S[i][j]=k;}}}}}/*输出剖分的三角形i，j：凸多边形的起始点下标*/void print_triangle(int i,int j){if(i==j) return;print_triangle(i,S[i][j]);print_triangle((4)); //s[i][j]+1,jprint(“V%d- -V%d--V%d\n“,i-1,S[i][j],j);}[问题1] (8分)根据说明和C代码，填充C代码中的空(1) ~ (4)。[问题2] (7分)根据说明和C代码，该算法采用的设计策略为(5)，算法的时间复杂度为(6)，空间复杂度为(7) (用0表示)。

Tags：软件水平考试中级软件设计师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题