首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
请阅读以下技术说明和C代码,将程序段中(1)~(5)空缺处的语句填写完整。 【说明】 著名的四色定理指出任何平面区域图均可用4种颜色着色,使相邻区域着不同的颜色。以下C程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。该程序中用1~4分
请阅读以下技术说明和C代码,将程序段中(1)~(5)空缺处的语句填写完整。 【说明】 著名的四色定理指出任何平面区域图均可用4种颜色着色,使相邻区域着不同的颜色。以下C程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。该程序中用1~4分
admin
2009-02-15
29
问题
请阅读以下技术说明和C代码,将程序段中(1)~(5)空缺处的语句填写完整。
【说明】
著名的四色定理指出任何平面区域图均可用4种颜色着色,使相邻区域着不同的颜色。以下C程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。该程序中用1~4分别表示4种颜色。要着色的N个区域用0~-1编号,区域相邻关系用adj[][]矩阵表示,矩阵的i行j列的元素为1,表示区域i与区域了相邻;矩阵的i行j列的元素为0,表示区域i与区域j不相邻。数组color[]用来存储着色结果,color
的值为区域i,所着颜色。
【C程序】
#include <stdio.h>
#define N 10
void output(int color[]) { /*输出一种着色方案*/
int i ;
for ( i = 0 ; i < N ; i++ )
printf( "%4d" , color
) ;
printf ("\n") ;
}
int back(int *ip ,int color[] ) { /*回溯*/
intc = 4 ;
while ( c == 4 ) {
if ( *ip <= 0 )
return 0 ;
-- (*ip) ;
c =(1);
color[*ip] =-1 ;
}
return c ;
}
/*检查区域i,对c种颜色的可用性*/
int colorOk(int i , intc , int [] [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[ ] ){
int k ;
for(k = c ; k <= 4 ; k++ )
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]!=0 && color[j]==c (3)I,k,adj,color (4)select(I,c+1,adj,color) (5)color[i]=c
解析
这是一道要求考生用C语言解决着色问题的编程题。本题的解答思路如下。
认真阅读程序说明部分和所给出的C程序段可知,该C程序由6个函数组成,即主函数main()、输出一种着色方案函数void output(int color[])、回溯操作函数int back(int *ip,int color[])、检查区域i对c种颜色的可用性函数int colorok(int I,int c,int[][N],int color[]、为区域i选一种可着的颜色函数int select(int I,int c,int adj[][N],int color[])和寻找各种着色方案函数int coloring(int adj[][N])。
1)空缺处在回溯操作子函数back()中,其中形参用指针指向记录当前考查区域号的变量。整个回溯过程是一个循环过程,当循环条件成立时,进行回溯。如果当前区域*ip已是0号区域,则不再回溯,函数返回0值,表示已穷尽了所有可能方案。否则,当前区域*ip减1,取出*ip区域的着色方案color[*ip]存放在c中,并置*ip区域为未着色。如果*ip区域的着色方案不是最后一种颜色,则回溯结束,函数返回该区域原来的着色方案。因此(1)空缺处所填写的内容是“color[*ip]”。
2)空缺处在检查区域i对c种颜色的可用性子函数colorok()中,根据程序的意义可以看出,(2)空缺处应填入的是判断该颜色不可取的条件,根据题干说明,相邻区域不能着相同的颜色,即和区域i相邻的区域不能着c种颜色。而当adj
[j]为1时,表示区域j和区域i相邻。如果区域j着c种颜色,则颜色不可取。所以(2)空缺处所填写的内容是“adj
[j]!=0 && color[j]==c”。
3)空缺处在为区域i选一种可着的颜色子函数select()中,依次选定一种颜色,调用colorok()函数,测试该颜色是否可以着在i区域上。(3)空缺处应为该函数colorok()填上实参“I,k,adj,color”,即(3)空缺处所填写的内容是“I,k,adj,color”。
4)(5)空缺处在寻找各种着色方案子函数coloring()中,该程序中定义了用于存放一种着色方案的数组color[],并对数组进行了初始化。该函数执行部分的程序结构是由一个while循环完成,循环的主体是一个if...else语句。该if...else体的else部分又包含一个if...else语句。在嵌套的内层if...else语句中,当 if(i==N)中条件成立时,表示为每一区域都找到了合适的颜色,则该方案是成功的,之后输出一种着色方案,再进行回溯。如果有一个区域找不到合适的颜色,则该方案就是失败的,这时也需要进行回溯操作。
由以上分析可知,寻找全部着色方案在while循环中进行,每次循环首先是为i号区域寻找一种方案。因为select()函数的功能就是为i区域选一种可能的颜色,同时可选的初始颜色是c+1号颜色,邻接矩阵是 adj[][],选定的颜色存于数组color[]中,所以(4)空缺处所填写的内容是“select(I,c+1,adj,color)”。
根据if(c=select(I,c+1,adj,color))==0)能够证实对函数back()的第一次调用肯定是在一种方案失败的情况下,而紧接着的else后面的语句则显然表示为区域i找到了一种可用的颜色c,所以应将颜色c存储在数组color[]中,即(5)空缺处所填写的内容是“color
=c”。
转载请注明原文地址:https://jikaoti.com/ti/hTW7FFFM
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
PowerPoint内置的动画效果中,不包括(60)。
对用户来说,信息系统的(14)反映了系统的功能。
文件外壳型病毒(21)。
假设“EXAM.DOC”文件夹存储在“EXAM1”文件夹中,“EXAM1”文件夹存储在“EXAM2”文件夹中,“EXAM2”文件夹存储在F盘的根文件夹中,当前文件夹为“EXAM1”。那么,正确描述“EXAM.DOC”文件的绝对路径表示为(37)。
在Excel2003中,A1到E6单元格的值如下图所示,若在A7单元格中输入函数“=COUNTA(A1:E6)”,按回车键后,则A7单元格显示的值为(44)。
在Excel2010的A1单元格中输入函数“=ABS(ROUND(-1.478,2))”,按回车键后,A1单元格中的值为________________。
在Excel2010中,C3:C7单元格中的值分别为10、OK、20、YES和48,在。D7单元格中输入函数“=COUNT(C3:C7)”,按回车键后,D7单元格中显示的值为________________。
某软件公司规定,该公司软件产品的版本号由二至四个部分组成:主版本号次版本号[.内部版本号][.修订号]。对该公司同一软件的以下四个版本号中最新的版本号是(
在Windows7中,若删除桌面上某个应用程序的快捷方式图标,则(31)。
随机试题
集成电路布图设计的特点有()
公元前8世纪至公元前6世纪的罗马,尚处于氏族社会向阶级社会过渡时期。称为:()
函数,在x→1时,f(x)的极限是()。
基金监管的基本原则不包括()。
下列说法中,符合目前消费税政策规定的有()。
【B1】【B7】
对法律进行分类,可以从不同的标准、角度出发。一般来讲,根据不同的法律形式,可以把法划分为()。
《唐律疏议.名例律》规定:“诸应议、请、减及九品以上之官,若官品得减者之祖父母、父母、妻、子孙,犯流罪以下,听赎;若应以官当者,自从官当法。其加役流、反逆缘坐流、子孙犯过失流、不孝流,及会赦犹流者,各不得减赎,除名、配流如法。”请运用中国法制史知识和理论
KarlVonLinne(orLinnaeus,asheiswidelyknown)wasaSwedishbiologistwhodevisedthesystemofLatinisedscientificnames
假设某计算机系统的内存大小为256K,在某一时刻内存的使用情况如下表所示。此时,若进程顺序请求20K和5K的存储空间,系统采用某种算法为进程分配内存,分配后的内存情况如下表所示。那么系统采用的是什么分配算法?()
最新回复
(
0
)