●试题五 阅读下列程序说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。 【程序5说明】 著

Question

●试题五

阅读下列程序说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

【程序5说明】

著名的四色定理指出任何平面区域图均可用四种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过四种颜色的着色方案。

程序中用1~4表示四种颜色。要着色的N个区域用0~N-1编号，区域相邻关系用adj［］［］矩阵表示，矩阵的i行j列的元素为1，表示区域i与区域j相邻；矩阵的i行j列的元素为0，表示区域i与区域j不相邻。数组color［］用来存储着色结果，color［i］的值为区域i所着颜色。

【程序5】

#include<stdio.h>

#define N 10

void output(int color［］)/*输出一种着色方案*/

{int i;

for(i=0;i<N;i++)

printf("%4d"，color［i］);

printf("＼n");

}

int back(int*ip,int color［］)/*回溯*/

{int c=4;

while(c==4){

if(*ip<=0)return 0;

--(*ip);

c= (1) ;

color［*ip］=-1;

}

return c;

}

/*检查区域i，对c种颜色的可用性*/

int color0k(int i,int c,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［i］=-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));

}

Answer 1

正确答案：

●试题五

【答案】（1）color［*ip］（2）adj［i］［j］ != 0 && color［j］ == c

（3）i,k,adj,color（4）select （i,c+l,adj,color）（5）color［i］=c

【解析】（1）Back（）函数将color数组中紧邻*ip位置的，颜色值为4的一个连续区域的元素赋值为－1。（2）colorOK（）判断区域i对其之前的所有区域是否可以着色c。该句是检查i的相邻区域是否已有颜色为c的。（3）这是colorOK的参数列表。Select为区域i选择一种颜色，使用colorok函数对各种颜色（值为c～4的一种，不一定是所有颜色）分别进行检查。（4）Coloring（）函数寻找各种着色方案。它先从区域0开始，检查颜色，并着色（着色的顺序总是从小色值的颜色开始的）。当发现某一区域无法着色时，就使用back（）函数，将该区域之前的一个连贯区域进行洗色（对应color数组中赋值为－1）并回溯，并从回溯后的位置，重新开始进行颜色检查和赋色，但使用的色值比该位置洗色前的颜色值更大。若所有区域均已着色，则输出该着色方案。然后，使用back函数，重新进行着色。当所有颜色方案均已找到后，函数结束。（5）该句对区域i赋颜色c。c为之前select函数所选出的可以用的颜色。