2. 从业资格
  3. n皇后问题描述为：在一个n×n的棋盘上摆放n个皇后，要求任意两个皇后不能冲突，即

n皇后问题描述为：在一个n×n的棋盘上摆放n个皇后，要求任意两个皇后不能冲突，即

资格题库2022-08-02  54
问题 n皇后问题描述为：在一个n×n的棋盘上摆放n个皇后，要求任意两个皇后不能冲突，即任意两个皇后不在同一行、同一列或者同一斜线上。算法的基本思想如下：将第i个皇后摆放在第i行，i从1开始，每个皇后都从第1列开始尝试。尝试时判断在该列摆放皇后是否与前面的皇后有冲突，如果没有冲突，则在该列摆放皇后，并考虑摆放下一个皇后；如果有冲突，则考虑下一列。如果该行没有合适的位置，回溯到上一个皇后，考虑在原来位置的下一个位置上继续尝试摆放皇后，……，直到找到所有合理摆放方案。【C代码】下面是算法的C语言实现。（1）常量和变量说明n:皇后数，棋盘规模为n×nqueen[]:皇后的摆放位置数组，queen表示第i个皇后的位置，1≤queen≤n（2）C程序#include＜stdio.h>#define n 4int 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＜j;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;}【问题1】（8分）根据题干说明，填充C代码中的空（1）（4）。【问题2】（3分）根据题干说明和C代码，算法采用的设计策略为（5）。【问题3】（4分）当n=4时，有（6）种摆放方式，分别为（7）。
选项
答案
解析 【问题1】（1）queen==queen[j]或其等价形式（2）1（3）Place(j)或其等价形式（4）Nqueen(j+1)【问题2】（5）回溯法【问题3】（6）2个（7）（2413）或（2,4,1,3）（3142）或（3,1,4,2）【问题1】（1）第一空根据代码上下文：for(i=1;i＜j;i++){/*检查与已摆放的皇后是否在同一列或者同一斜线上*/if(（1）)‖abs(queen-queen[j])==(j-i)){return 0;}}abs(queen-queen[j])==(j-i)判断是否在同一斜线上，此处还缺少对同一列的判断，即queen==queen[j]或其等价形式。（2）第二空根据Place(int j)函数首行注释：int Place(int j){/*检查当前列能否放置皇后，不能放返回0，能放返回1*/此处是成功后的返回，返回值应该是1。（3）第三空根据代码上下文if(（3）){if(j==n){/*如果所有皇后都摆放好，则输出当前摆放方案*/Show();}else{/*否则继续摆放下一个皇后*/（4）;}}（3）与j==n结合可以判断所有皇后都摆好，（3）与j!=n结合可以判断继续摆放下一个皇后，即前面的皇后已摆放好。所以（3）的判断条件应该是摆放函数Place()返回值为1，即（3）Place(j)或其等价形式。（4）第四空填写摆放下一个皇后，即（4）Nqueen(j+1)。【问题2】根据题干描述“如果该行没有合适的位置，回溯到上一个皇后，考虑在原来位置的下一个位置上继续尝试摆放皇后”，本题采用的是回溯法的设计策略。【问题3】当n=4时，可以有2种摆放方式，如下所示：即（2413）（3142）。
转载请注明原文地址:https://tihaiku.com/congyezige/2409603.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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