2. 计算机
  3. 阅读下列说明和C代码，回答问题，将解答写在答题纸的对应栏内。 【说明】 n皇后问题描述为：在一个n×n的棋盘上摆放n个皇后，要求任意两个皇后不能冲突，即任意两个皇后不在同一行、同一列或者同一斜线上。 算法的基本思想如下： 将第i个皇

阅读下列说明和C代码，回答问题，将解答写在答题纸的对应栏内。 【说明】 n皇后问题描述为：在一个n×n的棋盘上摆放n个皇后，要求任意两个皇后不能冲突，即任意两个皇后不在同一行、同一列或者同一斜线上。 算法的基本思想如下： 将第i个皇

admin2021-03-13  29
问题 阅读下列说明和C代码，回答问题，将解答写在答题纸的对应栏内。
【说明】
    n皇后问题描述为：在一个n×n的棋盘上摆放n个皇后，要求任意两个皇后不能冲突，即任意两个皇后不在同一行、同一列或者同一斜线上。
    算法的基本思想如下：
    将第i个皇后摆放在第i行，i从1开始，每个皇后都从第1列开始尝试。尝试时判断在该列摆放皇后是否与前面的皇后有冲突，如果没有冲突，则在该列摆放皇后，并考虑摆放下一个皇后；如果有冲突，则考虑下一列。如果该行没有合适的位置，回溯到上一个皇后，考虑在原来位置的下一个位置上继续尝试摆放皇后……直到找到所有合理摆放方案。
【C代码】
    下面是算法的C语言实现。
    (1)常量和变量说明
    n：皇后数，棋盘规模为n×n
    queen[]：皇后的摆放位置数组，queen表示第i个皇后的位置，1≤queen≤n
    (2)C程序
    #include
    #define n 4
    int queen[n+1]；
    void Show(){    ／* 输出所有皇后摆放方案*／
       int i；
       printf("(")；
       for(i=1；i<=n；i++){
           printf(" ％d"，(queen)；
       }
       printf(")＼n")；
    }
    int Place(int j){    ／*检查当前列能否放置皇后，不能放返回0，能放返回1*／
        int i；
        for(i=1；i           if(  (1)________   ｜｜  abs(queen-queen[j])==(j-i)){
          return 0;
        }
    }
    return(2)________；
}
void Nqueen(int j){
    int i；
    for(i=1；i<=n；i++){
    queen[j]=i;
    if(  (3)________  ){
      if(j==n){  ／*如果所有皇后都摆放好，则输出当前摆放方案*／
         Show()
      }else{    ／*否则继续摆放下一个皇后*／
        (4)________；
      }
    }
   }
}
int main(){
    Nqueen(1)；
    return 0；
}
根据题干说明，填充C代码中的空(1)～(4)。
选项
答案(1)queen[i]==queen[j]或等价形式 (2)1 (3)Place(i) (4)Nqueen(j+1)
解析 函数Place用于检查当前行j的queen[j]位置能否放置皇后，不能放则返回0，能放则返回1。能放的前提是前j-1行已经放置了互相不冲突的皇后，此时判断第j行的皇后queen[j]是否与前面的皇后有冲突，因此判断if中的两个条件为是否在同一列或同一对斜线。其中，abs(queen-queen[j])==(j-i)表示两个皇后在同一斜线上，因此(1)中应填同一列，即queen==queen[j]。在定义函数Place的时候己经注释说明，如果不能放返回0，能放返回1，因此(2)填1。
在函数Nqueen中放置皇后。从第一行第一列开始，每次放置皇后是判断是否可以放置的位置，因此(3)填Place(j)。如果能放且j是最后一行，则得到一个放置方案：如果能放且i不是最后一行，则需要放下一个皇后，因此(4)填写Nqueen(j+1)。这里用到了递归调用，因此没有显式回溯的语句。
转载请注明原文地址:https://kaotiyun.com/show/zoxZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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