实验一递归与分治算法的应用.doc

实验一:递归与分治算法的应用
——零件切割问题
院系:信息学院05计算机系班级: 1班姓名:阙寿辉学号:22120051203884
一、问题描述:
给定一块宽度为W的矩形板,矩形板的高度不受限制。现需要从板上分别切割出n个高度为hi,宽度为wi的矩形零件。切割的规则是零件的高度方向与矩形板的高度方向保持一致。问如何切割使得所使用的矩形板的高度h最小?
例如:
请设计出一个分治算法,实现下述功能:
,能输出切割所需要的实际高度

二、算法思想:
首先将零件按从大到小的顺序排列好。选择零件中长度最长的一块,将该零件按照高度方向放入矩形,零件的左下角与矩形的左下角重合。此时矩形被划分成零件所占的一块、零件右侧一块和零件上侧一块。在剩下的零件中选择长度最大的一块,将它放入零件右侧的一块小矩形,此时第二大的零件又将第一个零件划分出来的右侧矩形划分成三块,如此递归,直至所有的零件的长度都比被先于它放入矩形的零件所划分出来的右侧小矩形的宽度长。按同样的方法递归地将剩余的零件放入零件上一侧的矩形中直至所有的零件都被放入矩形。
三、具体实现:
struct rectangle
{ //实现对矩形数据结构的定义
int width; //矩形宽度
int high; //矩形高度
float x; //矩形的左下顶点横坐标
float y; //矩形的左下顶点纵坐标
int flag; //判断切割时是否需要增加高度h
}RECTANGLE;
定义矩形的宽度、高度为整形。(矩形的高度可以设为无穷大)确定矩形的坐标,这个对后面的图形实现有用,分别定义矩形的左下顶点横坐标和左下顶点纵坐标为x和y。另外加一个标志的int型数据flag,用以判断切割时是否需要增加高度h。
struct part //实现对木块数据结构的定义
{
int width; //零件宽度
int high; //零件宽度
float x; //切割后零件左下顶点横坐标
float y; //切割后零件左下顶点纵坐标
}PART;
定义零件的宽度、高度,另外还需要定义切割后零件左下顶点横坐标、纵坐标,用以确定零件在矩形中的位置。
**CreatFloatArray_2(float **head,int m,int n)
{
int i,j;
float *p=NULL;
if( !(m > 0 && n > 0) )
{ //判断维度是否正确
printf("数组维度出错!\n");
return NULL;
}
p = (float *)malloc(sizeof(float) * m * n); //申请总体空间
head = (float **)malloc(sizeof(float *)*m); //申请二级指针空间
for(i = 0;i < m;i++)
head[i]=p + n * i;
for(i = 0;i < m;i++)
for(j = 0;j < n;j++)
head[i][j] = 0;
return head;
}
这