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

阅读以下说明和C语言函数，将应填入(n)处的语句写在对应栏内。 【说明】 著名的四色定理指出任何平面区域均可以用4种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。 【函数】 # in

admin2012-12-10  21
问题 阅读以下说明和C语言函数，将应填入(n)处的语句写在对应栏内。
    【说明】
   著名的四色定理指出任何平面区域均可以用4种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过4种颜色的着色方案。
   【函数】
   # include  ＜stdio.h＞
   #define N 10 /*要着色的N个区域*/
   void output(int color[]) /*输出一种着色方案 color的值为区域i所着颜色*/
   {
       int i;
       for (i=0; i＜N; i++)
           printf("%4d", color);
       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[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=-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[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=c”。
转载请注明原文地址:https://kaotiyun.com/show/snjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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