2. 计算机
  3. 请阅读以下技术说明和C代码，将程序段中(1)～(5)空缺处的语句填写完整。 【说明】 著名的四色定理指出任何平面区域图均可用4种颜色着色，使相邻区域着不同的颜色。以下C程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。该程序中用1～4分

请阅读以下技术说明和C代码，将程序段中(1)～(5)空缺处的语句填写完整。 【说明】 著名的四色定理指出任何平面区域图均可用4种颜色着色，使相邻区域着不同的颜色。以下C程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。该程序中用1～4分

admin2009-02-15  22
问题 请阅读以下技术说明和C代码，将程序段中(1)～(5)空缺处的语句填写完整。
   【说明】
   著名的四色定理指出任何平面区域图均可用4种颜色着色，使相邻区域着不同的颜色。以下C程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。该程序中用1～4分别表示4种颜色。要着色的N个区域用0～-1编号，区域相邻关系用adj[][]矩阵表示，矩阵的i行j列的元素为1，表示区域i与区域了相邻；矩阵的i行j列的元素为0，表示区域i与区域j不相邻。数组color[]用来存储着色结果，color的值为区域i，所着颜色。
   【C程序】
   #include ＜stdio.h＞
   #define N 10
   void output(int color[]) {                   /*输出一种着色方案*/
      int i ;
      for ( i = 0 ; i ＜ N ; i++ )
          printf( "%4d" , color ) ;
      printf ("\n") ;
   }
   int back(int *ip ,int color[] ) {            /*回溯*/
       intc = 4 ;
       while ( c == 4 ) {
           if ( *ip ＜= 0 )
              return 0 ;
           -- (*ip) ;
           c =(1);
           color[*ip] =-1 ;
       }
       return c ;
   }
   /*检查区域i，对c种颜色的可用性*/
   int colorOk(int i , intc , 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 =-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
解析 这是一道要求考生用C语言解决着色问题的编程题。本题的解答思路如下。
   认真阅读程序说明部分和所给出的C程序段可知，该C程序由6个函数组成，即主函数main()、输出一种着色方案函数void output(int color[])、回溯操作函数int back(int *ip,int color[])、检查区域i对c种颜色的可用性函数int colorok(int I,int c,int[][N],int color[]、为区域i选一种可着的颜色函数int select(int I,int c,int adj[][N],int color[])和寻找各种着色方案函数int coloring(int adj[][N])。
   1)空缺处在回溯操作子函数back()中，其中形参用指针指向记录当前考查区域号的变量。整个回溯过程是一个循环过程，当循环条件成立时，进行回溯。如果当前区域*ip已是0号区域，则不再回溯，函数返回0值，表示已穷尽了所有可能方案。否则，当前区域*ip减1，取出*ip区域的着色方案color[*ip]存放在c中，并置*ip区域为未着色。如果*ip区域的着色方案不是最后一种颜色，则回溯结束，函数返回该区域原来的着色方案。因此(1)空缺处所填写的内容是“color[*ip]”。
   2)空缺处在检查区域i对c种颜色的可用性子函数colorok()中，根据程序的意义可以看出，(2)空缺处应填入的是判断该颜色不可取的条件，根据题干说明，相邻区域不能着相同的颜色，即和区域i相邻的区域不能着c种颜色。而当adj[j]为1时，表示区域j和区域i相邻。如果区域j着c种颜色，则颜色不可取。所以(2)空缺处所填写的内容是“adj[j]!=0 && color[j]==c”。
   3)空缺处在为区域i选一种可着的颜色子函数select()中，依次选定一种颜色，调用colorok()函数，测试该颜色是否可以着在i区域上。(3)空缺处应为该函数colorok()填上实参“I,k,adj,color”，即(3)空缺处所填写的内容是“I,k,adj,color”。
   4)(5)空缺处在寻找各种着色方案子函数coloring()中，该程序中定义了用于存放一种着色方案的数组color[]，并对数组进行了初始化。该函数执行部分的程序结构是由一个while循环完成，循环的主体是一个if...else语句。该if...else体的else部分又包含一个if...else语句。在嵌套的内层if...else语句中，当 if(i==N)中条件成立时，表示为每一区域都找到了合适的颜色，则该方案是成功的，之后输出一种着色方案，再进行回溯。如果有一个区域找不到合适的颜色，则该方案就是失败的，这时也需要进行回溯操作。
   由以上分析可知，寻找全部着色方案在while循环中进行，每次循环首先是为i号区域寻找一种方案。因为select()函数的功能就是为i区域选一种可能的颜色，同时可选的初始颜色是c+1号颜色，邻接矩阵是 adj[][]，选定的颜色存于数组color[]中，所以(4)空缺处所填写的内容是“select(I,c+1,adj,color)”。
   根据if(c=select(I,c+1,adj,color))==0)能够证实对函数back()的第一次调用肯定是在一种方案失败的情况下，而紧接着的else后面的语句则显然表示为区域i找到了一种可用的颜色c，所以应将颜色c存储在数组color[]中，即(5)空缺处所填写的内容是“color=c”。
转载请注明原文地址:https://kaotiyun.com/show/fojZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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