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

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

admin2021-03-13  21
问题 阅读下列说明和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；
}
当n=4时，有(6)________种摆放方式，分别为(7)________。
选项
答案(6)2 (7)(2，4，1，3)或(2 4 1 3) (3，1，4,2)或(3 1 4 2)
解析 根据对问题的描述和C语言实现，可以摆放皇后获得问题的解。当n=4时，有两种摆放方案，如下图所示，其中◇表示皇后。因此(6)中填2，(7)中填(2，4，1，3)和1(3，1，4,2)。

本题考查算法设计策略与分析方法。
此类题目要求考生认真阅读题目对问题的描述，以及用算法求解该问题的思路，能够理解如何将典型的算法设计策略应用到实际问题的求解中，并用某种程序设计语言来实现。
转载请注明原文地址:https://kaotiyun.com/show/KsxZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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