【说明】 著名的四色定理指出任何平面区域均可以用4种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。 【函数】 # include ＜stdio.h＞ #define N 10 /*要着色的N个区域*/ void output(int color[]) /*输出一种着色方案 color[i]的值为区域i所着颜色*/ { int i; for (i=0; i＜N; i++) printf("%4d", color[i]); printf("\n"); } int back(int *ip, int color[j] /*回溯*/int c=4;while (c==4){ if (*ip＜=0)return 0: --(*ip);c= (1) ; color[*ip]=-1;}return c; } /*检查区域i，考查c种颜色的可能性 */ int colorOK(iht 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[]) /*寻找各种着色方案 adj[i][j]=1表示区域i与区域j不相邻*/ { int k; for (k=c; k＜=4; k++) /*4种颜色*/ 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));
参考答案：
解析：(1)color[*ip] (2)adj[i][j]==1&&color[j]==c (3)i，k，aaj，color (4)select(i，c+1，adj，color) (5)color[i]=c
[分析]： 本题考查四色定理在C语言中的实现。 题目对四色定理做了解释，是指任何平面区域均可以用4种颜色着色，使相邻区域着不同的颜色。而题目中给定了区域图，要求找出所有可能的不超过4种颜色的着色方案。下面我们来分析程序。 第(1)空在函数back()中，这个函数的作用在注释中已经给出，是回溯，通过回溯，我们可以搜索出问题的所有解。此空是给变量c赋一个值，从程序中我们可以推断出变量c中存放的是区域中当前选中的颜色，而表示区域中当前选中的颜色的是数组color的当前值，因此，此空答案为“color[*ip]”。 第(2)空在函数colorOK()中，这个函数的作用在注释中也给出了，是检查区域i，考查c种颜色的可能性，这就要求判断每种颜色是否适合区域i，如果适合，则返回真。此空是函数体中一个条件判断语句的条件，如果条件不成立，则返回真，那么条件应该不能确定该颜色是否适合区域i。如果比较的是两个不相邻的位置，且两个位置的颜色都为当前色，那么肯定不能确定当前色是否适合区域i。因此，此空答案为“adj[i][j]==1 &&color[j]==c”。 第(3)空在函数select()中，这个函数是为区域i选一种可着色，此空是函数colorOK()的参数，而这个函数有4个参数，分别是当前位置i、当前颜色和两个数组，因此，此空答案为“i,k,adj,color”。 第(4)空是给变量c赋值，变量c中存放的是当前要处理的颜色，而这条语句是条件判断执行语句，如果条件成立，则要回溯，那么说明不能确定当前区域的颜色，而为当前区域i选一种可着色是函数select()的功能，它返回0时，说明不能确定区域i的颜色。因此，此空答案为“select(i,c+1,adj,color)”。 第(5)空是在上空中条件不成立的情况下执行的语句，条件不成立说明确定了当前区域i的颜色，然后应该将该区域存为这种颜色，而变量c中存放的就是当前处理的颜色，因此，此空答案为“color[i]=c”。