首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题,将解答写在答题纸的对应栏内。 【说明】 n皇后问题描述为:在一个n×n的棋盘上摆放n个皇后,要求任意两个皇后不能冲突,即任意两个皇后不在同一行、同一列或者同一斜线上。 算法的基本思想如下: 将第i个皇
阅读下列说明和C代码,回答问题,将解答写在答题纸的对应栏内。 【说明】 n皇后问题描述为:在一个n×n的棋盘上摆放n个皇后,要求任意两个皇后不能冲突,即任意两个皇后不在同一行、同一列或者同一斜线上。 算法的基本思想如下: 将第i个皇
admin
2021-03-13
11
问题
阅读下列说明和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代码中的空(1)~(4)。
选项
答案
(1)queen[i]==queen[j]或等价形式 (2)1 (3)Place(i) (4)Nqueen(j+1)
解析
函数Place用于检查当前行j的queen[j]位置能否放置皇后,不能放则返回0,能放则返回1。能放的前提是前j-1行已经放置了互相不冲突的皇后,此时判断第j行的皇后queen[j]是否与前面的皇后有冲突,因此判断if中的两个条件为是否在同一列或同一对斜线。其中,abs(queen
-queen[j])==(j-i)表示两个皇后在同一斜线上,因此(1)中应填同一列,即queen
==queen[j]。在定义函数Place的时候己经注释说明,如果不能放返回0,能放返回1,因此(2)填1。
在函数Nqueen中放置皇后。从第一行第一列开始,每次放置皇后是判断是否可以放置的位置,因此(3)填Place(j)。如果能放且j是最后一行,则得到一个放置方案:如果能放且i不是最后一行,则需要放下一个皇后,因此(4)填写Nqueen(j+1)。这里用到了递归调用,因此没有显式回溯的语句。
转载请注明原文地址:https://kaotiyun.com/show/zoxZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
请分别说出(1)与(2)的设备名称。目前常见宽带接入的方式有哪几种?
一台Windows2003操作系统的主机上同时安装了IPv6和IPv4两种协议,该主机既可以和仅支持IPv4协议的主机通信,也可以和仅支持IPv6协议的主机通信,这种实现IPv4向IPv6的平稳过渡的通信方案称为双协议栈技术。基于该技术的协议栈结构如图7
结构化布线成为网络设计和管理的首先考虑的问题,当实施结构化布线时,需要进行详细的规划设计。
在由L2TP构建的VPN中,主要由(1)和(2)两种类型的服务器构成。1.将图2中(1)和(2)处空缺名称填写在答题纸的相应位置。2.相对于L2TP,另一种构建VPN的方式是什么?某路由器(在图2中没有标出)的部分配置信息如下所示,请解
为了实现VLAN1、VLAN2和VLAN3的虚拟网络划分,在ATM和RT路由器中应设置哪几种服务协议(如BUS)?试述从PC,发送一个IP包到PC:的路由计算过程和传送路径。
目前,国内短消息服务平台按照接入方式主要可分为哪两种?彩信“多媒体信息(MMS)”的别称,用户可以通过彩信功能想手机或电子信箱发送带有图片和声音的内容的短消息,文字容量可达15000字左右。请问发送MMS需要什么条件?
阅读以下说明,回答问题1、问题2、问题3和问题4。短消息是指简短的字符信息,在短消息通信系统里,则指由短消息实体发起,通过移动网络传输到指定目的地址的有限长度的文本信息,近几年,短消息服务得到广泛应用。基于web的短消息服务平台的系统结构如图3所示。We
阅读以下说明,回答问题1~4,将解答填入对应的解答栏内。利用VLAN技术可以把物理上连接的网络从逻辑上划分为多个不同的虚拟子网,可以对各个子网实施不同的管理策略。图4-1是在网络中划分VLAN的连接示意图。使Switch1的千兆端口允许所有
阅读以下说明,回答问题1至问题6,将解答填入答题纸对应的解答栏内。【说明】某单位网络拓扑结构如图3-1所示,其中Web服务器和DNS服务器均采用WindowsServer2008R2操作系统,客户端采用Windows操作系统,公司Web网站的域名
SDLCwasinventedbyIBMtoreplacetheolderBisynchronousprotocolforwideareaconnectionsbetweenIBMequipment.Avarieti
随机试题
A.多见于乳管内头状瘤B.多见于乳管阻塞的乳管内乳头状瘤C.可见于终止哺乳后D.可见于正常月经期,早期妊娠或囊性增生症E.可见于因上皮增生而有乳头状体形成的乳腺囊性增生症鲜红色血性溢液
缺乏可致坏血病缺乏常见症状有口角炎和口唇炎
女性,16岁,于右膝下方有一肿块,5年来逐渐增大,无痛,步态正常。X线摄片发现右胫骨内上方有一肿物,基底部有骨小梁与胫骨相连,基顶盖部致密度减低,边界尚可辨认。根据以上表现,最可能的诊断是
A、胰岛素B、磺酰脲类口服降糖药C、双胍类口服降糖药D、α-糖苷酶抑制剂E、噻唑烷二酮类降糖药刺激胰岛β田胞释放胰岛素,但对切除胰腺者无效的是()。
A、抗菌谱扩大B、增强杀菌作用C、增强降压药的效果D、降低毒性E、延缓耐药性SD+TMP()。
中性、嗜酸、嗜碱粒细胞胞质中颗粒在形态上的区别点是()。
消防用电设备供电线路在电缆隧道时,须采取防火封堵措施的情况有()。
我国投入巨额资金实施退耕还林工程,这说明:
()
传值与传地址是函数调用时常采用的信息传递方式,______。
最新回复
(
0
)