首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题,将解答写在答题纸的对应栏内。 【说明】 n皇后问题描述为:在一个n×n的棋盘上摆放n个皇后,要求任意两个皇后不能冲突,即任意两个皇后不在同一行、同一列或者同一斜线上。 算法的基本思想如下: 将第i个皇
阅读下列说明和C代码,回答问题,将解答写在答题纸的对应栏内。 【说明】 n皇后问题描述为:在一个n×n的棋盘上摆放n个皇后,要求任意两个皇后不能冲突,即任意两个皇后不在同一行、同一列或者同一斜线上。 算法的基本思想如下: 将第i个皇
admin
2021-03-13
17
问题
阅读下列说明和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://kaotiyun.com/show/7sxZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
请简要说出DHCP服务的基础流程?请分别写出查看客户机TCP/IP的详细配置信息、手工释放IP地址、重新向DHCP服务器申请IP地址Windows2000命令。
划分VLAN有哪几种划分方式?在VLAN中,STP和VTP是什么协议?各有什么作用?
请阅读以下说明和Socfort程序,将应填(n)处的字句写在对应栏内。网络应用的基本模型是客户机/服务器模型,这是一个不对称的编程模型,通信的双方扮演不同的角色:客户机和服务器。以下是一个简单的客户机程序(服务器程序略),其工作过程非常简单:客
从工作的频段、数据传输速率、优缺点以及它们之间的兼容性等方面,对IEEE802.11a、IEEE802.11b和IEEE802.11g进行比较。1.将(1)处空缺设备的名称填写在相应位置。2.(1)所在局域网内的PC或笔记本计算机的IP地址有
阅读以下说明,回答问题1~4,将解答填入对应的解答栏内。利用VLAN技术可以把物理上连接的网络从逻辑上划分为多个不同的虚拟子网,可以对各个子网实施不同的管理策略。图4-1是在网络中划分VLAN的连接示意图。将Switch2的端口10划入cl
在“本地安全设置”中,用户账户锁定策略如图4-2所示,当3次无效登录后,用户账户被锁定的实际时间是(2)。如果“账户锁定时间”设置为0,其含义为(3)。备选答案:A.账户将一直被锁定,直到管理员明确解除对它的锁定B.账户将被
某公司网络结构如图3-9所示,通过在路由器上配置访问控制列表ACL来提高内部网络和Web服务器的安全。(2011年下半年下午试题四)请说明下面这组ACL语句的功能。Routerfconfig)#access-list101permit
网络存储备份系统的设计目标是什么?
ActiveXisthename(66)hasgiventoasetofobject-orientedconcepts,technologies,andtools.ItisimportanttonoticethatA
随机试题
Threepassions,simplebutoverwhelminglystrong,havegovernedmylife:thelongingforlove,thesearchforknowledge,andthe
GordonShawthephysicist,66,andcolleagueshavediscoveredwhat’sknownasthe"Mozarteffect",theabilityofaMozartsonat
中医治疗肿瘤的原则是
血小板抗原描述错误的是
采用质量成本评估法对工程咨询服务的投标文件进行评标时,技术建议书的权重一般不低于()。
下列关于各部门、各单位预算管理职权的说法正确的有()。
ItwasacoolOctobereveninginthehillcountryofsouthwestMississippi.【T1】Earlyfrosthadturnedleavestoagoldenhue.【
向敏中,字常之,开封人。父璃,仕汉符离令。性严毅,惟敏中一子,躬自教督,不假颜色。尝谓其母日:“大吾门者,此儿也。”及冠,继丁内外忧,能刻厉自立,有大志,不屑贫窭。太平兴国五年进士,任右赞善大夫,后命为枢密直学士。时通进、银台司主出纳书奏,领于枢
“国家活动不断增加的法则”,即随着高度的社会发展,政府的活动必将随之增加的法则,又可以称之为()。
DefendingtheTheoryofEvolutionStillSeemsNeededJudithS.Weis,abiologyprofessorwhoservesaspresidentoftheAmer
最新回复
(
0
)