2. 计算机
  3. 阅读以下程序说明和C程序，将程序段中(1)～(7)空缺处的语句填写完整。 【说明】 【C程序1】用回溯算法来产生由0或1组成的2m个二进位串，使该串满足以下要求。 视串为首尾相连的环，则由m位二进制数字组成的2m个子序列，每个可能的子序

阅读以下程序说明和C程序，将程序段中(1)～(7)空缺处的语句填写完整。 【说明】 【C程序1】用回溯算法来产生由0或1组成的2m个二进位串，使该串满足以下要求。 视串为首尾相连的环，则由m位二进制数字组成的2m个子序列，每个可能的子序

admin2009-02-15  29
问题 阅读以下程序说明和C程序，将程序段中(1)～(7)空缺处的语句填写完整。
    【说明】
   【C程序1】用回溯算法来产生由0或1组成的2m个二进位串，使该串满足以下要求。
   视串为首尾相连的环，则由m位二进制数字组成的2m个子序列，每个可能的子序列都互不相同。例如，如果m=3，在串11101000首尾相连构成的环中，由3位二进制数字组成的每个可能的子序列都在环中恰好出现一次，它们依次是111，110，101，010，100，000，001，011，如图2-14所示。
  
   【C程序2】是求“背包问题”的一组解的递归算法程序。“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为W1，W2，…，Wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。
【C程序1】
#define N 1024
#define M 10
int b [N+M-1]
int equal(int k, int j int m)  {
   int i;
   for(i=0; i＜m; i++
       if ( b[ k + i]  (1)  )
           return 0;
   return 1; }
int exchange (int k,  int m,  int v){
   while ( b[ k + m - 1 ) == v )  {
       b[ kncm--i]=! v  (2);
   }
     (3)=v;
   return k;
}
init ( iht v)  {
   int k
   for( k = 0;K = N + M - 1;k++)
       b[k] = v;
}
main ( )  {
   int m, v, k, n, j;
   printf (’Enter m (l＜m＜10) , v  v=0, v=1)\ n") ;
   scanf (" %d%d , &m, &v);
   n = 0x01 ＜＜ m;
   init (!v);
   k=0;
   while((4)＜ n)
       for (j=0;j＜k;j++)
           if (equal (k, j, m)) {
              k=exchange (k, m, v)
              j=(5);
         }
     for (k= 0 ;k＜n ;k++ )
         print{ (" %d\ n" , b[k]) ;
   }
}
【C程序2】
#include＜stdio. h＞
#define N 7
#define S 15
int w[N+1] = {0, 1, 4, 3, 4, 5, 2, 7};
int knap (int S, int n){
   if (S == 0)
       return 1;
   if (s＜0  ||  (s＞0 && n＜1))
       return 0;
   if ((6))) {
       printf( "4d", w[n]);
       return 1;
   }
   return  (7)  
}
main ( )  {
   if (knap (S, N)
      printf("OK:\n");
   else
      printf("NO!\n")
}
选项
答案(1)!=b[j+1] (2)k-，或-k，或k=k-1，或k-=l，或其他等价形式 (3)b[k+m-1] (4)++k，或(k=k+1)，或(k+=1)，或其他等价形式 (5)-1 (6)knap(s-w[n]，n-1) (7)knap(s，n，1)
解析 这是一道要求读者掌握回溯算法和递归算法的C语言编程题。解答此类题目的一般思路是读懂程序说明部分，弄清楚程序中各变量及各函数的含义，认真分析程序。本试题的解答思路如下。
   回溯算法也称为试探算法。该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了不满足问题规模要求外，还不满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯算法中，放弃当前候选解寻找下一个候选解的过程称为回溯，扩大当前候选解的规模并继续试探的过程称为向前试探。
   用回溯算法可以求得问题的一个解或全部解。为了不重复搜索已经试探过的解，需要采取某种方法来标记，最常用的方法是用栈(数组)来记录已经找到的解或搜索过的情况(路径)，也可以用位置指针、值的排列顺序等来标记。回溯算法的重点与难点如下。
   1)用回溯算法求问题的一个解时，找到的解不一定是最优解。在编写这类程序时，要注意记录(或标记)好中间每一个项的值，以便回溯。回溯到起始处，表示无解。
   2)用回溯算法求问题的全部解时，要注意在找到一组解时应及时输出或记录下来并统计解的个数，马上改变当前项的值并继续寻找下一组解，防止找到的解重复。回溯到起始位置表示找到了问题的全部解(尽管可能一组解也没输出)。
   认真阅读题干的程序说明和所给出的C程序段可知，【C程序1】由4个函数组成。①主函数main()的功能是初始化，在循环语句中调用函数依次产生二进位串，之后输出产生的二进位串；②函数init()对二进位串数组b进行初始化置位，全部置0或置1；③函数int equal()判断数组b中是否保存有相同的子串；④函数int exchange()将数组b中新加入的从k开始的子串最后一位由0变1或由1变0。
   (1)空缺处在函数int equal()中判断二进制串数组b中是否存在与新加入的子串相等的子串。新加入的子串在b中的开始下标为k，程序将b数组中k开始的m个字符逐个和i开始的m个字符相比较，又因为在主函数中有语句if(equal(k,j,m))(k=exchange(k,m,v)；……)，说明若m个字符都相等，则返回1，执行语句“k=exchange(k,m,v)；”来修改新加入的子串，否则只要有一个字符不等，则返回0。所以(1)空缺处所填写的内容是“!=b[j+i]”。
   (2)、(3)空缺处在函数int exchange()中的作用是修改新加入的子串，即将新子串的最后一个字符由 0变1或由1变0。如果修改后，经测试仍有相同的子串存在，则要回溯到b中的前一个子串，然后修改这个子串的最后一个字符，重复上述过程。当循环条件成立时新子串最后一个brk+m-1]修改后仍存在相同的子串，则要求回溯。而k为新子串在b数组中的开始下标，所以(2)空缺处所填写的内容是“k=k-1 (或其他等价形式，如--k，或k--，或k-=1)”。
   (3)空缺处所在的语句是处理不需要回溯的情况，此时要将新子串最后一个b(k+m-1]修改，又因为b[k+m-1]初值为!v，所以修改后的b[k+m-1]值应为v，所以(3)空缺处所填写的内容是“b(k+m-1]”。
   (4)、(5)空缺处在主程序main()中。依次往b数组中加入新子串，加入方式是对b数组都考查一个字符，即当加入子串在b数组中的下标k加1后，k又变成下两个新加入子串的下标。所以k+1也是在b数组中正确填写的二进制数的个数，根据题意其值不超过n。所以(4)空缺处所填写的内容是“k=k+1(或其他等价形式，如++k，或k+=1)”。
   根据(5)空缺处的前后语句可知，若函数equal返回1，即两个二进制字串相等，表示此步试探失败，此时调用函数exchange对新加入子串的最后一个字符进行修改或回溯，并返回修改或回溯后的最后一个子串在b数组中的下标k值。更改后，又要从第一个m位二进制字串开始检查，即要让for循环重新开始，此时j应为0。因为for循环语句每执行一次，要执行j++，所以(5)空缺处所填写的内容是“-1”。
   递归是设计和描述算法的一种有力的工具。能采用递归描述的算法通常有这样的特征：为求解规模为 N的问题，设法将它分解成一些规模较小的问题，然后由这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并由这些更小问题的解构造出规模稍大问题的解。特别地，当规模N=1时，能直接得到解。递归算法重点与难点如下 。
   1)编写递归程序的关键是：找出问题的递归关系和初始值。可以利用归纳法由一个问题归纳总结出递归式，加上初始条件，即可编写递归函数。
   2)编写递归程序时，必须要给出递归结束条件。
   3)递归的次数不是无限制的，每一次的递归调用都要压栈，占用内存，而计算机的内存是有限的。
   4)采用递归方法定义的数据结构或问题最适合使用递归方法。
   【C程序2】用递归算法解决背包问题的思路是对于物品i的选择有两种可能。
   1)考虑物品i被选择的情况，这种可能性当且仅当包含它不会超过方案总重量的限制时才是可行的。物品i被选择后，继续递归去考虑下一个物品。
   2)考虑物品i不被选择的情况，这种可能性当且仅当不包含物品i时，或找到价值更大的方案。考虑完物品i后，也要继续递归考虑下一个物品。
   根据以上思路分析【C程序2】中的函数knap(int s,intn)是用递归算法解决“背包问题”的。其中，参数s为考查完物品i后，背包还能盛放的重量：n为考查完物品i后，下一个待考查的物品。(6)空缺处是考虑物品n被选择的情况，此时因为物品n已被选择，所以剩余可盛放的重量应为s-w[n]，而背包待考查物品应为n-1，则(6)空缺处所填写的内容是“knap(s-w[n]n-1)”。
   (7)空缺处是处理不包含物品i时的情况。由于物品i没有放入背包，则背包可装载重量不变还应是 s，而这时应该考虑下一个物品n-1。因此(7)空缺处所填写的内容是“knap(s,n-1)”。
转载请注明原文地址:https://kaotiyun.com/show/2EjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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