数据结构课程设计用C语言解决八皇后问题
19页1、 用C+语言解决八皇后问题 1 引 言在程序设计中,可以用两种方法解决问题:一是传统的结构化程序设计方法,二是更先进的面向对象程序设计方法。在结构化程序设计中关键是如何将问题域中的行为(即操作)抽取出来,作为C+程序中的函数。由于多个函数均需要访问某些数据,这些数据常被设计为全局变量。而在面向对象程序设计中关键是如何将问题域中的实体(即日常所见的概念)抽取出来,作为C+程序中的类,而属性与行为作为类的两类要素通常是必不可少的,甚至还应考虑类必须满足的约束1。1.1课程设计目的深入理解数据结构的基本理论,掌握数据存储结构的设计方法,掌握基于数据结构的各种操作的实现方法,训练对基础知识和基本方法的综合运用能力,增强对算法的理解能力,提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。熟练运用C+语言、基本数据结构和算法的基础知识,独立编制一个具有中等难度的、解决实际应用问题的应用程序2。1.2课程设计内容国际象棋中皇后威力很大,它可以象“车”一样沿直线上下或左右移动;也可以如同“象”那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么,在一张空白的国际象
2、棋盘上最多可以放上几个皇后并且不让它们互相攻击呢?这个问题是伟大数学家高斯在十九世纪中期提出来的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后,他还认为可能有76种不同的放法,这就是有名的“八皇后”问题。现在我们已经知道八皇后问题有92个解答。那么你能试着找出几种方法吗?如果你动手试试,就一定会发现开头几颗皇后很容易放置,越到后来就越困难。由于我们的记忆有限,很可能在某个位置放过子后来证明不行取消了,但是以后又重新放上子去试探,这样就会不断地走弯路,花费大量的精力。因此,必须找到一个简易有效、有条不紊的法则才行3。 2问题描述和分析2.1问题描述在一个的棋盘里放置个皇后,要求每个皇后两两之间不相冲(在每一横列竖列斜列只有一个皇后)。一个合适的解应是在每列、每行确实有一个皇后,且在一条对角线上最多只有一个皇后2.2分析问题分析:(1) 满足上述条件的八个皇后,必然是每行一个,每列一个。(2)棋盘上任意一行、任意一列、任意一条斜线上都不能有两个皇后。如果我们把88的棋盘看成是一个平面直角坐标系,则八皇后问题就可以用数学语言来描述了,任意两个皇后在平面上的坐标应该同时满足以下三个条件
3、:两个皇后不在同一行:两个皇后的横坐标不相等;两个皇后不在同一列:两个皇后的纵坐标不相等;两个皇后不在同一条斜线上:两个皇后的横坐标之差的绝对值不等于两个皇后的纵坐标之差的绝对值。依据“分而治之”的思想,先讨论4皇后的问题。也就是说在44的盘内放4个后。8皇后的问题实际上是4皇后问题的衍生。如图2.1所示。图2.1 模拟棋盘图首先清理棋盘,把所有的坐标值都归零,如图2.2所示。 图 2.2 棋盘坐标清零然后放第一个Q1到(1,1)的位置,。即Q1.row=1,Q1.col=1,如图2.3所示。图2.3 放入第一颗棋子Q1会占据它所在的所有横,竖,斜的位置。调用seize(1,1)函数来实现这个功能。让Q1所在的横竖斜线上所在的坐标都置1,如图2.4所示。图2.4 继续探索接着放Q2。放Q2的过程可以看作是在43的棋格里放Q2-Q4的过程。其中33的棋格中间斜线被Q1占据,因此Q2放在(2,3)的位置。即Q2.row=2,Q2.col=3。放完Q2后,调用seize(2,3)函数来实现Q2的占据坐标,如图2.5所示。 图2.5 划出下一颗棋子可能的区间接下来要放Q3,可以看作是一个在42
4、的棋格里放Q3、Q4。但是我们看到第3行已经没有空位放Q3了。因此回退到Q2的时刻,把Q2往后放,寻找第2个适合Q2的位置。若没有位置可放,则退回到Q1改变Q1的位置,如图2.6所示。图2.6 放入第二颗棋子Q2从(2,3)的位置出来后,可以放在(2,4)的位置。即Q2.row=2,Q2.col=4。如此Q3便可放到(3,2)的位置,如图2.7所示。图2.7 继续探索但是如此一来,Q3放在(3,2)的位置会占据Q4(4,3)的位置使Q4无法安放。所以应该回退到Q1。使Q1放在(1,2)的位置,如图2.8所示。 图2.8 无解 退回Q1Q2因为(2,1)(2,2)(2,3)都被Q1占据,因此只能放在(2,4)的位置,如图2.9所示。图2.9 得出一个解至此,我们已经得到4皇后的一个解,判断是否已解出的条件是Q4是否被安放成功。此时Q4被安置,得出一个解,因此应该输出4个Q的位置调用函数print()输出此时的4个Q的位置。输出以后程序还没有完,因为我们还没有把所有的棋盘都遍历完毕。Q1只是到了(1,2)。要到(1,4)以后程序才算结束。所以我们应该把Q1往后移动一位到(1,3)继续找解。
《数据结构课程设计用C语言解决八皇后问题》由会员夏**分享,可在线阅读,更多相关《数据结构课程设计用C语言解决八皇后问题》请在金锄头文库上搜索。
大象版二年级科学(下册)期中试卷
中国移动2004年全球通VIP高尔夫俱乐部策划案
学校中学生暑期社会实践活动计划_1
交通安全班会演讲稿五篇
远程教育工程项目实施情况汇报
垃圾分类作文11篇(精选汇编)
石油成品油供应链现状
灌注桩监理细则
2022年二手房购房定金合同9篇
黑龙江省大庆市2017-2018学年高一数学上学期期中试题
关于《福建省高级会计师职务
[脚踝运动损伤紧急处理方法有哪些]运动损伤的处理方法
最新《施工组织设计》xx市黄河路立交桥引道工程
幼儿园小班语言《走开绿色大怪物》FLASH课件动画教案
财务会计试用期转正工作小结范文(3篇)
免疫规划整改报告(8篇)
初中物理老师教学反思8篇
行政管理与文秘
IPODtouch蓝牙共享手机上网
二次结构技术交底(最终)
2023-04-23 35页
2023-10-07 21页
2023-07-31 8页
2023-07-01 8页
2023-03-27 31页
2023-07-22 10页
2023-10-28 11页
2024-01-12 4页
2022-09-08 11页
2023-10-28 21页