2. 计算机
  3. 阅读以下应用程序说明和C程序，将C程序段中(1)-(7)空缺处的语句填写完整。 [说明] 以下[C程序]所完成的功能是在3X3方格中填入数字1～N(N≥10)内的某9个互不相同的整数，使所有相邻两个方格内的两个整数之和为质数。系统输出满足该要

阅读以下应用程序说明和C程序，将C程序段中(1)-(7)空缺处的语句填写完整。 [说明] 以下[C程序]所完成的功能是在3X3方格中填入数字1～N(N≥10)内的某9个互不相同的整数，使所有相邻两个方格内的两个整数之和为质数。系统输出满足该要

admin2009-02-15  56
问题 阅读以下应用程序说明和C程序，将C程序段中(1)-(7)空缺处的语句填写完整。
    [说明]
   以下[C程序]所完成的功能是在3X3方格中填入数字1～N(N≥10)内的某9个互不相同的整数，使所有相邻两个方格内的两个整数之和为质数。系统输出满足该要求的所有填法。系统的部分输出结果如图3-18所示。
  
   图3-18 系统的部分输出结果
   3×3方格从第1行左上角方格开始的序号分别为0、1、2，第2行左边方格开始的序号分别为3、4、 5，第3行左下角方格开始的序号分别为6、7、8。以下[C程序]采用试探法，即从序号为0的方格(左上角)开始，为当前方格寻找一个合理的可填整数，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格寻找一个合理的可填整数，就要后退到前一方格，调整前一方格的整数。直至序号为8的方格(右下角)也填入合理的整数时，就找到了一个解，将该解输出，并调整序号为8的方格所填的整数，继续去找下一个解。
   为了检查当前方格的填入整数的合理性，C程序引入二维数组checkMatrix，用于存放需要进行合理性检查的相邻方格的序号。
   [C程序]
   #include ＜stdio.h＞
   #define N 12
   int a [9];           /* 用于存储方格所填入的整数 */
   int b[N+1];
   int pos;
   checkMatrix[][3] = {{-1},{0,-1},{1,-1},{0,-1},{1,3,-1},{2,4,-1},{3,-1} {4,6,-1}, 5,7,-1}};
   void write(int a[])
   {   int i, j;
       for ( i = 0; i ＜ 3; i++)
           for ( j = 0;  j ＜ 3; j++)
               printf("%3d",a[3*i+j]);
           printf("\n");
       }
   }
   int isPrime(int m)
   {    int i;
        if  (m == 2)
            return 1;
            if (m == 1 || m % 2 == 0)
                return 0;
        for (i = 3; i * i ＜= m; )
        {   if (m % i == O)
                return 0;
            i+ =2;
        }
       return 1;
   }
   int selectNum(int start)
   {    int j;
        for  (j = start; j ＜= N; j++)
            if (b[j])
                return j;
            return 0;
   }
   int check ( )          /* 检查填入pos位置的整数是否合理 */
   {    int i, j;
        for (i = 0; (j =(1)) ＞= 0; i++)
            if (!isPrime(a[pos] + a[j]))
                 (2);
             (3);
   }
   extend ()               /* 为下一方格找一个尚未使用过的整数 * /
   {    a[(4)] = selectNum(1);
        b[a[pos]] = 0;
   }
   void change()           /* 为当前方格找下一个尚未使用过的整数(找不到回溯) */
   {    int j;
        while (pos ＞= 0 && (j = selectNum((5) ) == 0
             (6);
        if (pos ＜ 0)
            return;
        b[a[pos]] = 1;
        a[pos] = j;
        b[j] = 0;
   }
   find ( )
   {    int ok = 1;
        pos = 0; a[pos] = 1; b[a[pos]] = 0;
        de {
            if (ok)
                if (  (7)  ) {
                    write (a);
                    change( );
                }
                else
                    extend( );
            else
                change( );
            ok = check(pos);
        } while (pos ＞=0);
   }
   main( )
   {    int i;
        for (i = 1; i ＜=N; i++)
            b = 1;
        find( );
   }
选项
答案无论从程序规模还是从问题的复杂程度上看，这是一道有一定难度的试题。解题时可以先分析题干说明，然后再从程序的结构入手。结合试题说明及在程序中的使用情况，可以确定以下各个变量的含义，以及各个函数的功能。 1) b[N+1]存储可选择的整数的状态，若其值为1则表示未被选中，可以选；若其值为0则表示已被选中，不可再选。 2) pos记录当前正在处理的方格的位置。 3) 数组checkMatrix[][3]中每个元素的含义是，每个非负整数表示在填入某个位置时需要检查的方格；“-1”表示一个方格的关联方格罗列结束。 4) 在函数find()中使用了变量ok，从语句“ok=check()”，以及“if(ok)”可知，该变量表示一次check()的成功。 5) 从函数的内容上看，函数write()是打印一个合理的填写方法。 6) 函数isPrime()是判断一个整数是否为质数。 7) 函数selectNum()是为当前方格选择—个整数，至于该整数是否合理，还有待函数check()检查。 解题时，不妨再从函数find()读起。 if ( (7) ) { write(a)； change()； } 由题干说明中的关键信息“直至序号为8的方格也填入合理的整数后，就找到了一个解，将该解输出，并调整序号为8的方格所填整数，继续去找下一个解”可知，(7)空缺处所在的if...else处理语句是上述自然描述语言的表达形式。(7)空缺处所填写的内容就是判断当前填好的方格的位置是否为8，因此可以填入“pos==8”，也可以填写“pop＞7”，或者其他等价的语句形式。 对于函数check()， 该函数是检查填入的整数是否合理，从“(j= (1) )＞=0”和“if(isPrime(a[pos]+a[j])”两个语句来看，变量j在(1)空缺处取得了方格pos的一个相关位置的位置值。方格pos的一个相关位置如何取得呢?可以通过取数组checkMatrix的一个元素来获取。获取时可以通过变量i来计数，使用“checkMatrix[pos][i]”来依次取得方格pos的每一个相关位置的值，即(1)空缺处所填写的内容是“checkMatrix[pos][i]”。 由于函数isPrime()在m为质数时返回值为1，否则返回值为0，由此可以判断，(2)空缺处所在的语句是在检查到不合理的情况时的处理，即对检查到不合理的情况时的返回处理。如果(2)、(3)空缺处所在的for循环能够顺利结束，则说明检查结果是合理的，即该填写的内容是合理的。此时也应该进行返回处理，即(3)空缺处所在的语句也是一个返回控制。由于函数check()需要一个返回值以表明检查结果，其中，返回非0的值表示成功，否则即为失败(这从函数find()中if(ok)与ok=check()两条语句也可以看出)，因此(2)空缺处所填写的内容是“return0”或"return j＜0?1:0”，(3)空缺处所填写的内容是“return 1”或“return j＜0?1:0”。 (4)空缺处所在的extend()函数中，由于在调用该函数时指针pos仍然指向当前方格，因此在为下一个方格pos寻找尚未使用的整数时，首先必须是指针pos加1，使之指向下一个方格。另外，(4)空缺处之后有“b[a[pos]]=0”的操作，结合对函数selectNum()的理解可知，这是将已经选用过的整数在b[N+1]的相应响应位置0。这也间接要求(4)空缺处所进行的操作还必须改变pos的值，因此，(4)空缺处所填写的内容是“++pos”。 从函数change()的整体结构可以看出，这是—个回溯处理过程。如果回溯到“pos＜O”时，回溯处理过程就结束；否则选中j为位置pos的值。那么这个回溯过程是怎样实现的呢?函数change()是通过while循环来实现。(5)空缺处是构造函数selectNum()的start的值，由于在选a[pos]时已经从1开始搜寻了，a[pos]之前的值显然不必再搜寻了，且a[pos]也被证明不合适，因此start的值只需从a[pos]+1开始，即(5)空缺处所填写的内容是“a[pos]+1”，而不是“++a[pos]”或者“a[pos]++”。 当函数change()的while循环条件成立时，需要进行回退处理。此时先前已经被选中的整数不再有效，应恢复b[N+1]中相应位置的元素值，并将该元素值置1(表示未被选中)。考虑到需要修改pos以适应下一次对换，因此(6)空缺处所填写的内容是“b[a[pos--]]=1”，而不是“b[a[pos-1]]=1”。
解析
转载请注明原文地址:https://kaotiyun.com/show/MEjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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