问答题

【程序说明】 著名的四色定理指出任何平面区域图均可用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)); }