首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题,将解答写在答题纸的对应栏内。 【说明】 n皇后问题描述为:在一个n×n的棋盘上摆放n个皇后,要求任意两个皇后不能冲突,即任意两个皇后不在同一行、同一列或者同一斜线上。 算法的基本思想如下: 将第i个皇
阅读下列说明和C代码,回答问题,将解答写在答题纸的对应栏内。 【说明】 n皇后问题描述为:在一个n×n的棋盘上摆放n个皇后,要求任意两个皇后不能冲突,即任意两个皇后不在同一行、同一列或者同一斜线上。 算法的基本思想如下: 将第i个皇
admin
2021-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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下说明和交换机的配置信息,回答问题1-3。【说明】某公司下设3个部门,为了便于管理,每个部门组成一个VLAN,公司网络结构如图1-5所示。【交换机Switch1的部分配置信息】Switch1(config)#
阅读以下说明,回答问题1、问题2、问题3和问题4,将解答填入对应栏内。[说明]某公司想建立一个Intranet,建立FTP服务器、DNS服务器、Email服务器、Web服务器和内部业务服务器,同时其他部门的工作人员也要联网,要求这些机器有的
设计该宽带路由器的多任务嵌入式实时操作系统时,由于多个任务均可能要求占用CPU这个关键资源,因此CPU的任务管理是一个非常重要的设计内容。在该实时操作系统中,任务作为占用资源的基本单位,总共有5个状态:休眠状态、就绪状态、运行状态、等待或挂起状态和中断服务
设计该宽带路由器的多任务嵌入式实时操作系统时,由于多个任务均可能要求占用CPU这个关键资源,因此CPU的任务管理是一个非常重要的设计内容。在该实时操作系统中,任务作为占用资源的基本单位,总共有5个状态:休眠状态、就绪状态、运行状态、等待或挂起状态和中断服务
阅读以下关于HFC宽带接入Internet网的技术说明,根据要求回答问题1至问题4。【说明】混合光纤同轴电缆网(HFC网)应用数字和模拟传输技术,综合接入Internet、电话、模拟和数字广播电视、数字交互业务等多种业务,将计算机网络、有线电视网
随着Internet的发展,用户对网络带宽的要求不断提高,传统的接入网已成为整个网络中的瓶颈,以新的宽带接入技术取而代之已成为目前研究的焦点。其中最引人注意的是光纤接入技术。
随机试题
麦氏重排的特点有哪些?
数而时一止,止无定数所主病有
多发性骨髓瘤患者血清蛋白电泳图谱出现M区带是由于患者血清中有大量的
下列哪一项是对行政诉讼和刑事诉讼之间关系的错误表述?
关于公路施工企业信用评价等级的说法正确的有()。
对圆的直径是它的半径的两倍的学习属于()。
收容教育的期限是()
设函数f(x)==__________。
Manyexpertsbelievethatinthenewworldofartificialintelligence(AI)humanbeingswillstillbeneededtodothejobsthat
FannyKemble(1809—93)wasthenieceoftwoShakespeareantragedians,SarahSiddonsandSiddons’sbrother,JohnPhilipKemble.【R1】
最新回复
(
0
)