logo资料库

地图着色问题.doc

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.16M 资料格式：doc 举报 版权申诉
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
资料共10页，剩余部分请下载后查看
    课程设计 地图的四色问题 班 级： 组 长： 组 员： 任课教师： 07 计单 陈轶群 吕 龙 鞠训光
    一 、需求分析 1．以二维数组 list[N+1][N+1]表示地图，N 表示区域数目，数组中以元素值为 0 表示不邻接，1 表示邻接，限定区域数目 N<=50. 2．用户先输入区域数目 N，再输入邻接区域的代码，邻接可只写一次，区域的 代码为 0～N,N 个为区域，一个为外部区域，或输入 N-1,则可不包括外部区域， N 个区域由用户定义 3．输出时，采用一一对应的方法，一个区域对应一种颜色 形式：区域代码＝＝》颜色代码（1～4）＝》颜色 4．本程序可为任意一张的地图染色，并且至多只染四种颜色 5．测试数据：当区域数目 N=8,地图如下： 输出为 0=>1=>red 1=>2=>green 2=>3=>blue 3=>4=>yellow 4=>1=>red 5=>2=>green 6=>2=>green 7=>4=>yellow 8=>3=>blue 6.程序执行的命令为：1）创建地图 2）存储地图 3）获取地图 4）地图着 色 5）退出 二、概要设计 1．设定地图的抽象数据类型为： ADT list{
    数据对象：D={ai,j|ai,jε{’0’、‘1’}，0 <=i<=N,0<=j<=N 数据关系：R={ROW,COL} ROW={|ai-1,j,ai,jε D,i=1,…N,j=0,…,N} D,i=0,…N,j=1,…,N} } COL={|ai,j-1,ai,jε 2.本程序包括两个模块 1）主程序模块： void main() { } 初始化； while { } 接受命令； 处理命令； 2）地图模块――实现地图抽象数据类型 各模块之间的调用关系如下： 主程序模块 地图模块 三、详细设计 1.地图数据类型的操作设置如下： int creat(int N,int list[][MAX+1]) //初始化并创建地图的邻接矩阵 2.两点是否邻接的伪码算法： int link(int x,int *dc,int n,int list[][MAX+1]) { //从 1 到 n 看是否与 x 相邻，是返回‘1’ // 否则，返回‘0’ for(i=0;i
    初始化颜色 for(i=0;i
    四、调试分析 1.首先使用了《离散数学》的解决方法，但在测试中国地图中出错，因为排序 并不能解决递归调用的问题，后来省掉了排序，在使用开始那个例子时，第 8 个区域不能着色，因此，改采用递归的方法 2.算法的时间复杂度为 O(N),空间复杂度为 O(N*N); 3.通过本次试验，我认识到采用递归方法比较快捷，实现方便 五、程序代码 #include #define MAX 50 int total; int lin[MAX][MAX]; int color[MAX]; void draw(); int okcyq(int dep,int i,int x) { int k; for(k=x;k<=dep;k++) { if(lin[dep][k]==1 && i==color[k])return(0); if(!okcyq(dep,i,k+1)&&k==dep)return(1); } return(0); } void output() { int k; for(k=1;k<=total;k++) printf("%d ",color[k]); } { void find(int dep) int i; for(i=1;i<=4;i++) { if(okcyq(dep,i,1)) { color[dep]=i; if(dep==total) {output();getch();draw();exit(1);} else find(dep+1);
    color[dep]=0; } } } { void draw() int gdriver,gmode; int x=1,y=1,dx,dy,dx2,dy2,i=1; char dot,draw; gdriver=DETECT; initgraph(&gdriver,&gmode,""); cleardevice(); setbkcolor(BLACK); while((dot=getch())!='q') { { line(1,440,639,440); switch(dot) case 'a': setviewport(1,441,639,479,BLUE); clearviewport(); outtextxy(1,2,"Press 'b' to end, then Press 'q' to quit"); setviewport(1,1,639,439,BLUE); moveto(x,y); while((draw=getch())!='b') { switch(draw) { case 77:x=(getx()+1)%639;y=gety();moveto(x,y);putpixel(x,y,RED);break; case 75:x=getx()-1;y=gety();moveto(x,y);putpixel(x,y,RED);break; case 72:x=getx();y=gety()-1;moveto(x,y);putpixel(x,y,RED);break; case 80:x=getx();y=(gety()+1)%439;moveto(x,y);putpixel(x,y,RED);break; } } break; default: setviewport(1,441,639,479,BLUE); clearviewport(); outtextxy(1,2,"Press 'e' to end, then Press 'q' to quit"); setviewport(1,1,639,439,BLUE);
    moveto(x,y); while((draw=getch())!='e') { switch(draw) { case 77:x=(getx()+1)%639;y=gety();putpixel(getx(),gety(),getpixel(x,y)) ;moveto(x,y);putpixel(x,y,YELLOW);break; case 75:x=getx()-1;if(x==0)x=639;y=gety();putpixel(getx(),gety(),getpi xel(x,y));moveto(x,y);putpixel(x,y,YELLOW);break; case 72:x=getx();y=gety()-1;if(y==0)y=439;putpixel(getx(),gety(),getpi xel(x,y));moveto(x,y);putpixel(x,y,YELLOW);break; case 80:x=getx();y=(gety()+1)%439;putpixel(getx(),gety(),getpixel(x,y)) ;moveto(x,y);putpixel(x,y,YELLOW);break; } } } } setviewport(1,441,639,479,BLUE); clearviewport(); outtextxy(1,2,"Press 'e' to end, then Press 'q' to quit"); setviewport(1,1,639,439,BLUE); moveto(x,y); while((dot=getch())!='q') { switch(dot) { case 77:x=(getx()+1)%639;y=gety();putpixel(getx(),gety(),getpixel(x,y)) ;moveto(x,y);putpixel(x,y,YELLOW);break; case 75:x=getx()-1;if(x==0)x=639;y=gety();putpixel(getx(),gety(),getpi xel(x,y));moveto(x,y);putpixel(x,y,YELLOW);break; case 72:x=getx();y=gety()-1;if(y==0)y=439;putpixel(getx(),gety(),getpi xel(x,y));moveto(x,y);putpixel(x,y,YELLOW);break; case 80:x=getx();y=(gety()+1)%439;putpixel(getx(),gety(),getpixel(x,y)) ;moveto(x,y);putpixel(x,y,YELLOW);break; case 13: dx=x;dy=y;
    while(1) if(getpixel(dx,dy)!=RED) dx--; else break; dx2=dx; dx=x; while(1) { if(getpixel(dx,dy)!=RED) dx++; else break; setcolor(color[i]); line(dx2+1,dy,dx-1,dy); dx=x; while(1) if(getpixel(dx,dy)!=RED) dy--; else break; dy2=dy; dy=y; while(1) { if(getpixel(dx,dy)!=RED) dy++; else break; { } } { } } setcolor(color[i]); line(dx,dy2+1,dx,dy-1); break; case 'k':i++; } } closegraph(); } void main() { int i,j,sp,ep; char c; clrscr();
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料