首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C语言函数,将应填入(n)处的语句写在对应栏内。 【说明】 著名的四色定理指出任何平面区域均可以用4种颜色着色,使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。 【函数】 # in
阅读以下说明和C语言函数,将应填入(n)处的语句写在对应栏内。 【说明】 著名的四色定理指出任何平面区域均可以用4种颜色着色,使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。 【函数】 # in
admin
2012-12-10
60
问题
阅读以下说明和C语言函数,将应填入(n)处的语句写在对应栏内。
【说明】
著名的四色定理指出任何平面区域均可以用4种颜色着色,使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。
【函数】
# include <stdio.h>
#define N 10 /*要着色的N个区域*/
void output(int color[]) /*输出一种着色方案 color
的值为区域i所着颜色*/
{
int i;
for (i=0; i<N; i++)
printf("%4d", color
);
printf("\n");
}
int back(int *ip, int color[j] /*回溯*/
int c=4;
while (c==4)
{
if (*ip<=0)
return 0:
--(*ip);
c=(1);
color[*ip]=-1;
}
return c;
}
/*检查区域i,考查c种颜色的可能性 */
int colorOK(iht i, int c, int adj[][N], int color[])
{
int j;
for(j=0; j<i; j++)
if ((2))
return 0;
return 1;
}
/*为区域i选一种可着的颜色*/
int select(int i, int c, int adj[][N], int color[])
/*寻找各种着色方案 adj
[j]=1表示区域i与区域j不相邻*/
{
int k;
for (k=c; k<=4; k++) /*4种颜色*/
if (colorOK((3)))
return k;
return 0;
}
int coloring(int adj[][N])
{
int color[N], i, c, cnt;
for (i=0; i<N; i++) color
=-1:
i=c=0; cnt=0;
while (1)
[
if ((c=(4))==0)
{
c=back(&i, color);
if (c==0)
return cnt;
}
else
{
(5);
i++;
if(i==N)
{
output(color);
++cnt;
c=back(&i, color);
}
else
c=0;
}
}
}
void main()
{
int adj[N][N]={ {0, 1, 0, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 1, 1, 0, 1, 1, 1, 1, 0},
{0, 1, 0, 1, 0, 1, 1, 0, 1, 1},
{1, 1, 1, 0, 1, 1, 0, 0, 1, 1},
{1, 0, 0, 1, 0, 1, 0, 0, 0, 0},
{1, 1, 1, 1, 1, 0, 1, 0, 0, 1},
{1, 1, 1, 0, 0, 1, 0, 0, 1, 0},
{1, 1, 0, 0, 0, 0, 0, 0, 1, 1},
{1, 1, 1, 1, 0, 0, 1, 1, 0, 1},
{1, 0, 1, 1, 0, 1, 0, 1, 1, 0}
};
printf("共有%d 组解.\n", coloring(adj));
选项
答案
(1)color[*ip] (2)adj[i][j]==1&&color[j]==c (3)i,k,aaj,color (4)select(i,c+1,adj,color) (5)color[i]=c
解析
本题考查四色定理在C语言中的实现。
题目对四色定理做了解释,是指任何平面区域均可以用4种颜色着色,使相邻区域着不同的颜色。而题目中给定了区域图,要求找出所有可能的不超过4种颜色的着色方案。下面我们来分析程序。
第(1)空在函数back()中,这个函数的作用在注释中已经给出,是回溯,通过回溯,我们可以搜索出问题的所有解。此空是给变量c赋一个值,从程序中我们可以推断出变量c中存放的是区域中当前选中的颜色,而表示区域中当前选中的颜色的是数组color的当前值,因此,此空答案为“color[*ip]”。
第(2)空在函数colorOK()中,这个函数的作用在注释中也给出了,是检查区域i,考查c种颜色的可能性,这就要求判断每种颜色是否适合区域i,如果适合,则返回真。此空是函数体中一个条件判断语句的条件,如果条件不成立,则返回真,那么条件应该不能确定该颜色是否适合区域i。如果比较的是两个不相邻的位置,且两个位置的颜色都为当前色,那么肯定不能确定当前色是否适合区域i。因此,此空答案为“adj
[j]==1 &&color[j]==c”。
第(3)空在函数select()中,这个函数是为区域i选一种可着色,此空是函数colorOK()的参数,而这个函数有4个参数,分别是当前位置i、当前颜色和两个数组,因此,此空答案为“i,k,adj,color”。
第(4)空是给变量c赋值,变量c中存放的是当前要处理的颜色,而这条语句是条件判断执行语句,如果条件成立,则要回溯,那么说明不能确定当前区域的颜色,而为当前区域i选一种可着色是函数select()的功能,它返回0时,说明不能确定区域i的颜色。因此,此空答案为“select(i,c+1,adj,color)”。
第(5)空是在上空中条件不成立的情况下执行的语句,条件不成立说明确定了当前区域i的颜色,然后应该将该区域存为这种颜色,而变量c中存放的就是当前处理的颜色,因此,此空答案为“color
=c”。
转载请注明原文地址:https://kaotiyun.com/show/snjZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
下列快捷功能按钮中,可以在画好的图形内填充颜色的是(49)。
某金融企业正在开发移动终端非现场办公业务,为控制数据安全风险,采取的数据安全措施中并不包括______。
下列传输协议中,采用了加密技术的是______。
双击某个非可执行程序的文件名将(24)。
在Word的编辑状态下,先后新建了两个文档,但并没有对这两个文档做“保存”或“另存为”操作,则______。
下图是某国多年来统计的出生人数和死亡人数曲线图。从图中看出,该国从________________年以后,死亡人数超过了出生人数,出现了人口危机。
数据处理过程中经常会发生数据出错,因此,数据校验工作非常重要。实际工作中一般都需要采取某些有效的数据校验措施,但有些做法是很少采用的。例如,在每个处理阶段结束后,要求(26)。
发送电子邮件属于信息处理的(33)过程。
连接主机A与交换机的单根网线的最大长度为多少?为了控制局域网用户访问Internet时只能进行WWW浏览,网管应该在路由器上采取什么措施?
为什么一般处理“震荡波”病毒时,首先要把被侵入的计算机系统从网络上断开?在计算机系统发现病毒并清除以后,在未接入网络之前,从安全方面考虑,若需重新安装操作系统,通常需要执行以下几项主要工作后,方可接入网络。请给出下列工作的合理顺序。A.安装操作
随机试题
党的十六大以来,以胡锦涛为总书记的党中央提出全面建设小康社会的又一个重要目标是
A.基底细胞癌B.睑板腺癌C.鳞状细胞癌D.恶性黑色素瘤E.腺样囊腺癌在眼睑恶性肿瘤中的发病居第二位的是
A.谵语B.呓语C.独语D.郑声E.口吃热扰心神可见
图4-27所示平面桁架的尺寸与载荷均已知。其中,杆1的内力大小Fs1为()。
根据《合同法》第一百二十九条规定,国际货物买卖合同和技术进出口合同争议提出诉讼或申请仲裁有一定期限,自当事人知道或应当知道其权利受到侵害之日起计算。该期限为( )。
使用直方图主要为了了解产品质量特性的()。
火车车次前的字母代表了不同的含义,“Z”指代的是直达特快列车。()
A、B、C、D四个工程队修建一条马路,A、B合作可用8天完成,A、C或B、D合作可用7天完成,问C、D合作能比A、B合作提前多少天完成?
2011年,我国本地生产总值平减物价指数为:
TheEndofAIDS?A)OnJune5th1981America’sCentresforDiseaseControlandPreventionreportedtheoutbreakofanunusualfor
最新回复
(
0
)