📄 fenzhi.cpp
字号:
#include <stdio.h>
#include <windows.h>
#include <GL/gl.h>
#include <GL/glaux.h>
#include <time.h>#define MAXBAN 200 //木板数组大小
#define fileName "fz.txt" //打开的木块文件名
typedef struct ban{ //木板定义 int x; //板宽度 int y; //板高度
float a; //板的左下顶点横坐标
float b; //板的左下顶点纵坐标
int flag; //表示切割时是否需要增加高度h}BAN;
typedef struct kuai{//木块定义 int x; //木块宽度 int y; //木块宽度
float a; //切割后木块左下顶点横坐标
float b; //切割后木块左下顶点纵坐标}KUAI;
KUAI *Kuai = NULL;//木块数组定义
int x = 0; //用于调整opengl中屏幕的相对坐标
int num; //num为木块的个数
int k =1; //用于动态显示木块变化
float **C = NULL; //定义颜色数组头指针
void myinit(void);void CALLBACK myReshape(GLsizei w,GLsizei h);
void CALLBACK display(void);
void CALLBACK down(void);//按 DOWN
void DrawMyObjects(void);
void Qiege(BAN *Ban,int num,KUAI *Kuai,int *h);
float **CreatFloatArray_2(float **Head,int m,int n);
//一下为两个比较函数，用于qsort函数
int B_cmp(const void *a,const void *b) //木板按高度排序
{
BAN *B_a = (BAN *)a;
BAN *B_b = (BAN *)b;
return B_a->y > B_b->y?1:-1;
}
int K_cmp(const void *a,const void *b) //木块按高度排序
{
KUAI *K_a = (KUAI *)a;
KUAI *K_b = (KUAI *)b;
return K_a->y > K_b->y?-1:1;
}
int main(void){ int i,n,w,h = 0;//w为木板宽度，n为木块个数，h为最终木板的切割高度 FILE *fp;
BAN Ban[MAXBAN];//定义木板数组
clock_t start,end; //测试程序运行时间
start = clock();
if(!(fp = fopen(fileName,"r"))){ //打开木块文件
printf("Open file %s error\n",fileName);
return -1;
} fscanf(fp,"%d %d",&n,&w);
x = w; //用于调整opengl中屏幕的相对坐标 if(!(Kuai = (KUAI *)malloc(sizeof(KUAI) *(n + 1)))){//木块数组申请 printf("malloc error!\n"); return -1; }
Ban[0].x = w; //初始木板 Ban[0].y = 35767; //高度为无穷大
Ban[0].a =(float)0.0;
Ban[0].b =(float)0.0;
Ban[0].flag = 1; //为1表示切割是需要增加高度 for(i = 0; i < n; i++) //读入木块数据 fscanf(fp,"%d %d",&Kuai[i].y,&Kuai[i].x);
Kuai[n].x = 0; //放置最后一块用于标志结束
Kuai[n].y = 0; fclose(fp);
qsort(Kuai,n,sizeof(Kuai[0]),K_cmp); //对木块按高度排序
Qiege(Ban,0,Kuai,&h); //递归函数
num = n; //木块的个数
printf("睡眠1秒...\n");
_sleep(1000);
printf("高度H = %d\n\n",h);
printf("注意：程序运行时有两个窗口，控制台窗口和图形窗口\n请勿移动控制台窗口，否则会影响图形显示\n");
printf("如果你已经移动控制台窗口并造成了图形窗口显示异常，请重新运行程序\n\n");
printf("请按键盘上的“向下方向键”动态显示木块\n\n");
end = clock();
printf("程序运行%lf秒\n",(double)(end - start) / CLK_TCK);
//生成颜色数组，用于绘制图形
C = CreatFloatArray_2(C,n,3); //动态创建二位数组，用于存放颜色
for(i = 0; i < n; i++){
C[i][0] = (rand()%3)/3.0 + 0.01;
C[i][1] = (rand()%6)/6.0 + 0.3;
C[i][2] = (rand()%9)/7 + 0.05;
}
//opengl函数
/////////////////////////////////////////////////////////////////////////
auxInitDisplayMode(AUX_SINGLE|AUX_RGBA); //
auxInitPosition(250,100,800,800); //
auxInitWindow("递归与分治:零件切割问题"); //
myinit(); //
auxKeyFunc(AUX_DOWN,down); //
auxReshapeFunc(myReshape); //
auxMainLoop(display); //
/////////////////////////////////////////////////////////////////////////
return 1;}
void Qiege(BAN *Ban,int num,KUAI *Kuai,int *h)
//num指向当前木板数组的最后一块，h为当前木板的切割高度
//Ban和Kuai指针分别是全局的木板和木块数组头指针
{
int i;
KUAI *p = Kuai + 1; //下次递归的参数，从下一块木块进入切割
//printf("%d ",(*p).y);
if(Kuai[0].y == 0) //没有木块需要切割了,退出递归
return ;
for(i = 0;Ban[i].x < Kuai[0].x || Ban[i].y < Kuai[0].y;i++); //寻找合适的木板
num++;
if(Ban[i].flag == 1)//判断是否需要增加切割高度
*h += Kuai[0].y;
//记录切割的左下角位置，便于图形显示
Kuai[0].a = Ban[i].a;
Kuai[0].b = Ban[i].b;
//切割木板并放入木板数组
Ban[num].x = Ban[i].x;
Ban[num].y = Ban[i].y - Kuai[0].y;
Ban[num].a = Ban[i].a;
Ban[num].b = Ban[i].b + Kuai[0].y;
if(Ban[i].flag == 1)
Ban[num].flag = 1;
Ban[i].x -= Kuai[0].x;
Ban[i].y = Kuai[0].y;
Ban[i].a = Ban[i].a + Kuai[0].x;
Ban[i].b = Ban[i].b;
Ban[i].flag = 0;
//对木板数组进行按高度的递减排序
qsort(Ban,num + 1,sizeof(Ban[0]),B_cmp);
//递归调用
Qiege(Ban,num,p,h);
}
//根据输入的二维数组行和列动态创建二位数组，返回数组指针
float **CreatFloatArray_2(float **Head,int m,int n)
{
int i,j;
float *p=NULL;
if( !(m > 0 && n > 0) ){ //判断维度是否正确
printf("错误的数组维度\n");
return NULL;
}
if( !(p = (float *)malloc(sizeof(float) * m * n))){ //申请总体空间
printf("Malloc error\n");
return NULL;
}
if( !(Head = (float **)malloc(sizeof(float *)*m))){ //申请二级指针空间
printf("Malloc error\n");
return NULL;
}
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;
}
//以下函数为opengl图形绘制函数
/////////////////////////////////////////////////////////////////////////////////////// void myinit(void) //
{ //
glClearColor(0.0,0.0,0.0,0.0); //
glClear(GL_COLOR_BUFFER_BIT);
glShadeModel(GL_FLAT);
}
void CALLBACK down(void)
{
if(k < num)
k++;
}
void CALLBACK myReshape(GLsizei w,GLsizei h)
{
glViewport(0,0,w,h);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
if(w<=h)
glOrtho(-x,x,-x*(GLfloat)h/(GLfloat)w,x*(GLfloat)h/(GLfloat)w,-50.0,50.0);
else
glOrtho(-x*(GLfloat)h/(GLfloat)w,x*(GLfloat)h/(GLfloat)w,-x,x,-50.0,50.0);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
}
void CALLBACK display(void)
{
glColor3f(1.0,0.0,0.0);
if(k == 1)
glTranslatef(-(x * 0.5),-(x-0.1*x),0.0);//移动屏幕坐标到木板左下方
DrawMyObjects();
glFlush();
}
void DrawMyObjects(void)
{
int i;
glBegin(GL_LINE_STRIP); //绘制木板
glVertex2f(0.0,0.0);
glVertex2f(0.0,2*x-0.2*x);
glVertex2f(0.0,0.0);
glVertex2f(x,0.0);
glVertex2f(x,0.0);
glVertex2f(x,2*x-0.2*x);
glEnd();
for(i = 0; i < k;i++){
glColor3fv(C[i]);
glBegin(GL_QUADS );
glVertex2f(Kuai[i].a,Kuai[i].b + Kuai[i].y);
glVertex2f(Kuai[i].a,Kuai[i].b);
glVertex2f(Kuai[i].a + Kuai[i].x,Kuai[i].b);
glVertex2f(Kuai[i].a + Kuai[i].x,Kuai[i].b + Kuai[i].y);
glEnd(); //
} //
} //
////////////////////////////////////////////////////////////////////////////////////
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -