首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题,将解答写在答题纸的对应栏内。 【说明】 n皇后问题描述为:在一个n×n的棋盘上摆放n个皇后,要求任意两个皇后不能冲突,即任意两个皇后不在同一行、同一列或者同一斜线上。 算法的基本思想如下: 将第i个皇
阅读下列说明和C代码,回答问题,将解答写在答题纸的对应栏内。 【说明】 n皇后问题描述为:在一个n×n的棋盘上摆放n个皇后,要求任意两个皇后不能冲突,即任意两个皇后不在同一行、同一列或者同一斜线上。 算法的基本思想如下: 将第i个皇
admin
2021-03-13
22
问题
阅读下列说明和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://jikaoti.com/ti/MZa7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下说明,回答问题1、问题2、问题3和问题4,将解答填入对应栏内。[说明]某公司想建立一个Intranet,建立FTP服务器、DNS服务器、Email服务器、Web服务器和内部业务服务器,同时其他部门的工作人员也要联网,要求这些机器有的
设计该宽带路由器的多任务嵌入式实时操作系统时,由于多个任务均可能要求占用CPU这个关键资源,因此CPU的任务管理是一个非常重要的设计内容。在该实时操作系统中,任务作为占用资源的基本单位,总共有5个状态:休眠状态、就绪状态、运行状态、等待或挂起状态和中断服务
设计该宽带路由器的多任务嵌入式实时操作系统时,由于多个任务均可能要求占用CPU这个关键资源,因此CPU的任务管理是一个非常重要的设计内容。在该实时操作系统中,任务作为占用资源的基本单位,总共有5个状态:休眠状态、就绪状态、运行状态、等待或挂起状态和中断服务
设计该宽带路由器的多任务嵌入式实时操作系统时,由于多个任务均可能要求占用CPU这个关键资源,因此CPU的任务管理是一个非常重要的设计内容。在该实时操作系统中,任务作为占用资源的基本单位,总共有5个状态:休眠状态、就绪状态、运行状态、等待或挂起状态和中断服务
认真阅读以下基于Windows2003操作系统IPv6的技术说明,根据要求回答问题1至问题4。【说明】由于现有的网络设备大部分都是基于IPv4的,也不可能在短时间内都更新换代来支持IPv6,因此在相对比较长的一段时期内,IPv6网络将和IPv4
阅读以下关于HFC宽带接入Internet网的技术说明,根据要求回答问题1至问题4。【说明】混合光纤同轴电缆网(HFC网)应用数字和模拟传输技术,综合接入Internet、电话、模拟和数字广播电视、数字交互业务等多种业务,将计算机网络、有线电视网
随着Internet的发展,用户对网络带宽的要求不断提高,传统的接入网已成为整个网络中的瓶颈,以新的宽带接入技术取而代之已成为目前研究的焦点。其中最引人注意的是光纤接入技术。
随机试题
A.小便点滴短少B.小便浑浊如米泔水C.小便时尿道刺痛有血D.小便点滴不通根据上述症状选出血淋的主症
外感咳嗽,经解表后,仍咳嗽咽痒,微有恶寒发热,舌苔薄白者,治宜选用
根据研究发现,具有C型人格特征的人易患
复方硫黄洗剂属于何种类型的液体制剂?()
下列中,()不属于工程咨询项目管理组织的社会技术支持。
下岗失业人员小额担保贷款遵循()的原则。
学生听到“集合”口令后,迅速跑向集合地点,为节省时间,学生可以从基准生和指挥员之间穿过。()
下列关于名义利率与有效年利率的说法中,正确的是()。[浙江工商大学2012研]
设有如下通用过程:PublicFunctionFun(xStrAsString)AsStringDimtStrAsString,strLAsIntegertStr=""strL=Len(xStr)i=lDoWhil
PleasemakeallcheckspayabletoTheGlassHouse.Toreportanyproblem,contactthesalesrepresentativewhotookyourorderb
最新回复
(
0
)