2. 计算机
  3. 阅读下列程序说明和C代码，将应填入(n)处的字句写在对应栏内。 【程序说明】 著名的四色定理指出任何平面区域图均可用4种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。程序中用1～4表示4种颜色。要着色的

阅读下列程序说明和C代码，将应填入(n)处的字句写在对应栏内。 【程序说明】 著名的四色定理指出任何平面区域图均可用4种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。程序中用1～4表示4种颜色。要着色的

admin2013-05-11  69
问题 阅读下列程序说明和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所着颜色。
   【程序】
   #include＜stdio.h＞
   #define   N 10
   void output(int color[])/*输出一种着色方案*/
   {
         int i;
         for(i=0; i＜N; i++)
              printf("%4d", color);
         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=-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) i，k，adj，color (4) select(i，c+1，adj，color) (5) color[i]=c
解析 本题考查著名的着色问题，相对难度较低，用到了回溯法的算法思想。
   程序中，数组adj[][]存放所有区域的相邻情况，color[]存放着色方案。
   程序中子程序较多，注释中比较清楚地说明了各个子程序的功能。从主函数看起，main函数中给数组adj赋值，即初始化所有区域的相邻情况，然后调用coloring函数。coloring函数是用来寻找各种着色方案的，注意是找所有的着色方案，而不是只找一个解，因此找到一个解后需要进行回溯；另外，当一个方案无法继续为剩余区域着色时也需要回溯。while循环中，是一个if-else结构，else块中也是一个if-else结构，其中if块调用到了output函数，说明找到了一个解，然后进行回溯。可见外层else块是可以继续分配颜色，空(5)处应该是保存着色方案，故空(5)应填color=c。外层if块是尝试着色失败，进行回溯，故空(4)处应该尝试为区域i着色，应该调用select函数，又可选的初始颜色是c+1号颜色，故空(4)应填select(i， c+l，adj，color)。
   函数select函数是用来为区域i选一种可着的颜色，依次选定一种颜色，然后判断是否可行，若可行返回颜色号，若不可行返回0。显然需要调用函数colorOK函数，对着函数原型易得，空(3)应填“i，k，adj，color”。
   函数colorOK是用来判断区域i是否可着c号颜色。根据着色规则：相邻区域不能着相同的颜色”，即与区域i相邻的区域不能着c种颜色。空(2)条件成立返回0，结合函数select中的调用，返回0表示不可用，故空(2)应填“adj[j]!=0 && color[j]==c”。
   最后来看back函数，空(1)是相对比较难的一空。其中形参ip指向记录当前考查区域号的变量。用指针形参是因为回溯时函数需要修正当前区域号。整个回溯过程是一个循环，如果当前区域*ip已选第四号颜色(颜色已经用尽)，即while循环中的条件成立，则需要回溯。回溯时，若发现当前区域*ip已经是0号区域，当然不能再回溯了，函数返回0值，表示已经穷尽了所有可能的方案；否则，当前区域号减1，取出*ip区域的着色方案，并置*ip为未着色。 *ip的着色方案存储于color[*ip]中，如果*ip区域的着色方案不是最后一种颜色，则回溯结束，函数返回该区域原来的着色方案，让*ip区域选用编号更大的颜色。故空(1)应填“color[*ip]”。
转载请注明原文地址:https://www.kaotiyun.com/show/X1RZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)