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代码，算法采用的设计策略为(5)________。
选项
答案(5)回溯法
解析 这是一个典型的回溯算法求解问题的过程。分治法、动态规划、贪心算法、回溯法和分支限界法是要求考生掌握的算法设计策略，考生需要理解算法求解问题的基本步骤以及应用该算法策略求解的典型例子。
转载请注明原文地址:https://www.kaotiyun.com/show/7sxZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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