题目内容
阅读下列程序说明和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));
}
查看答案
搜索结果不匹配?点我反馈
更多问题