《实验七 凸多边形最优三角剖分和图像压缩算法信科 06 李婕》由会员分享，可在线阅读，更多相关《实验七 凸多边形最优三角剖分和图像压缩算法信科 06 李婕（3页珍藏版）》请在金锄头文库上搜索。
1、宁夏师范学院数学与计算机科学学院算法分析与设计实验报告实验序号：7 实验项目名称：凸多边形最优三角剖分和图像压缩算法学号 23 姓名 专业、班 10 级信科实验地点318 指导教师惠云 时间 2010.5.15一、实验目的及要求（1） 掌握使用动态规划方法设计凸多边最优三角剖分问题的算法；（2） 掌握使用动态规划方法设计图像压缩问题的算法；二、实验设备（环境）及要求1、环境要求：硬件：PC （PII 以上，128M 以上内存） 、因特网接入；软件：Windows XP 操作系统、VC+6.0 编程环境。2、实验要求：(1) 独立完成实验，源代码书写规范；(2) 程序运行结果以屏幕截图的方式粘贴
2、在对应位置，截图必须清晰准确；(3) 实验完成后必须有实验结果的分析及本次实验的总结。三、实验内容与步骤(1) 设计求解凸多边形最优三角剖分问题的程序，并将凸多边形最优三角剖分所对应的的弦的集合在屏幕上显示。#include#define N 5void minWeight(int p,int mN,int sN);int w(int i,int j,int sNN);void minWeight(int p,int mN,int sN) int n=N-1;int i,j,k,r,t;for( i=1;i=n;i+) mii=0; for( r=2;r=n;r+)for( i=1;i=n-r
3、+1;i+) j = r+i-1; mij=mi+1j+w(i+1,i,j); sij=i; for( k = i+1;kj;k+) t=mik+mk+1j+w(i-1,k,j); if(tmij) mij=t;sij=k; int w(int i,int j,int sNN) int k;if(i=j) return ;if(i+1=j)return ;w(i,sij,s);w(sij+1,j,s);if(i+1!=k)printf(V%d-V%dn,i,k);if(k+1!=j)printf(V%d-V%dn,k,j)int main()int i,j;int sN2,pN,mNN;for(i=0;iN;i+)printf(第V%d个顶点的坐标 :,i);scanf(%d%d,printf(最优值:%dn,m1N-1);w(1,N-1,s);(2). 设计求解图像压缩问题的程序，并将划分的每个像素段所包含的像素个数、存储每位像素的位数在屏幕上显示。四、实验结果与数据处理1的结果：五、分析与讨论1、分析凸多边形最优三角剖分问题相应算法的时间复杂度。凸多边形最优三角剖分问题相应算法的时间复杂度为 O(n)。2. 分析图像压缩问题相应算法的时间复杂度。图像压缩问题相应算法的时间复杂度为 O(n)。成绩六、教师评语签名： 日期： 年 月 日
