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

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

admin2013-01-05  73
问题 阅读下列程序说明和C代码，将应填入(n)处。
    【程序5说明】
   著名的四色定理指出任何平面区域图均可用四种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过四种颜色的着色方案。
   程序中用1～4表示四种颜色。要着色的N个区域用0～N-1编号，区域相邻关系用 adj[][]矩阵表示，矩阵的i行j列的元素为1，表示区域i与区域j相邻；矩阵的i行j列的元素为0，表示区域i与区域j不相邻。数组color[]用来存储着色结果，color的值为区域i所着颜色。
   【程序5】
   #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[])/*回溯*/
   {  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 [][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
解析 (1)Back()函数将color数组中紧邻*ip位置的，颜色值为 4的一个连续区域的元素赋值为-1。(2)colorOK()判断区域i对其之前的所有区域是否可以着色c。该句是检查i的相邻区域是否已有颜色为c的。(3)这是colorOK的参数列表。Select为区域i选择一种颜色，使用colorok函数对各种颜色(值为c～4的一种，不一定是所有颜色)分别进行检查。(4)Coloring()函数寻找各种着色方案。它先从区域0开始，检查颜色，并着色(着色的顺序总是从小色值的颜色开始的)。当发现某一区域无法着色时，就使用back()函数，将该区域之前的一个连贯区域进行洗色(对应color数组中赋值为-1)并回溯，并从回溯后的位置，重新开始进行颜色检查和赋色，但使用的色值比该位置洗色前的颜色值更大。若所有区域均已着色，则输出该着色方案。然后，使用back函数，重新进行着色。当所有颜色方案均已找到后，函数结束。(5)该句对区域i赋颜色c。c为之前select函数所选出的可以用的颜色。
转载请注明原文地址:https://kaotiyun.com/show/weDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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