阅读下列程序说明和C代码,将应填入(n)处的字句写在对应栏内。【程序说明】 著名的四色定理指出任何

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

【程序说明】

著名的四色定理指出任何平面区域图均可用4种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。程序中用1～4表示4种颜色。要着色的N个区域用0～N-1编号，区域相邻关系用adj[][]矩阵表示，矩阵的i行j列的元素为1，表示区域i与区域j相邻：矩阵的i行j列的元素为0，表示区域i与区域j不相邻。数组color[]用来存储着色结果，color[i]的值为区域i所着颜色。

【程序】

include＜stdio.h＞

define N 10

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

{

int i;

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

printf("%4d", color[i]);

pfintf("\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 colorOK(int 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[])

int k;

for(k = c; k＜=4; k++)

if( (3) )return k;

return 0;

int coloring(int adj[][N])/*寻找各种着色方案*/

{

int color[N], i, c, cnt;

for(i=0; i＜N; i++)cotor[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));

}

正确答案：

(1) color[*ip](2) adj[i][j]!=0 && color[j]==c(3) ikadjcolor(4) select(ic+1adjcolor)(5) color[i]=c(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 解析：本题考查著名的着色问题，相对难度较低，用到了回溯法的算法思想。 程序中