实验七 凸多边形最优三角剖分和图像压缩算法信科 06 李婕

《实验七 凸多边形最优三角剖分和图像压缩算法信科 06 李婕》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、宁夏师范学院数学与计算机科学学院《算法分析与设计》实验报告实验序号：7　　实验项目名称：凸多边形最优三角剖分和图像压缩算法学　号23姓　名专业、班10级信科实验地点318指导教师惠云时间2010.5.15一、实验目的及要求（1）掌握使用动态规划方法设计凸多边最优三角剖分问题的算法；（2）掌握使用动态规划方法设计图像压缩问题的算法；二、实验设备（环境）及要求1、环境要求：硬件：PC（PII以上，128M以上内存）、因特网接入；软件：WindowsXP操作系统、VC++6.0编程环境。2、实验要求：(1)独立完成实验，源代码书写

2、规范；(2)程序运行结果以屏幕截图的方式粘贴在对应位置，截图必须清晰准确；(3)实验完成后必须有实验结果的分析及本次实验的总结。三、实验内容与步骤(1)设计求解凸多边形最优三角剖分问题的程序，并将凸多边形最优三角剖分所对应的的弦的集合在屏幕上显示。#include#defineN5voidminWeight(intp[],intm[][N],ints[][N]);intw(inti,intj,ints[N][N]);voidminWeight(intp[],intm[][N],ints[][N]){intn

3、=N-1;inti,j,k,r,t;for(i=1;i<=n;i++)m[i][i]=0;for(r=2;r<=n;r++)for(i=1;i<=n-r+1;i++){j=r+i-1;m[i][j]=m[i+1][j]+w(i+1,i,j);s[i][j]=i;for(k=i+1;k

4、;if(i+1==j)return;w(i,s[i][j],s);w(s[i][j]+1,j,s);if(i+1!=k)printf("V%d-V%d",i,k);if(k+1!=j)printf("V%d-V%d",k,j)}intmain(){inti,j;ints[N][2],p[N],m[N][N];for(i=0;i

5、-1]);w(1,N-1,s);}(2).设计求解图像压缩问题的程序，并将划分的每个像素段所包含的像素个数、存储每位像素的位数在屏幕上显示。四、实验结果与数据处理1的结果：五、分析与讨论1、分析凸多边形最优三角剖分问题相应算法的时间复杂度。凸多边形最优三角剖分问题相应算法的时间复杂度为O(n)。2.分析图像压缩问题相应算法的时间复杂度。图像压缩问题相应算法的时间复杂度为O(n)。六、教师评语签名：日期：年月日成绩