●试题五阅读下列程序说明和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】#includestdio.h#define N 10void output(int color[])/*输出一种着色方案*/{int i;for(i=0;iN;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;ji;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;iN;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));}
●试题五
阅读下列程序说明和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));
}