八皇后课程设计实验报告C++.docx
- 文档编号:11906735
- 上传时间:2023-06-03
- 格式:DOCX
- 页数:17
- 大小:211KB
八皇后课程设计实验报告C++.docx
《八皇后课程设计实验报告C++.docx》由会员分享,可在线阅读,更多相关《八皇后课程设计实验报告C++.docx(17页珍藏版)》请在冰点文库上搜索。
八皇后课程设计实验报告C++
设计任务书
课题
名称
八皇后
设计
目的
调研并熟悉八皇后的基本功能、数据流程与工作规程;
学习八皇后相关的算法和基于VC++集成环境的编程技术;
通过实际编程加深对基础知识的理解,提高实践能力;
学习开发资料的收集与整理,学会撰写课程设计报告。
实验
环境
微型电子计算机(PC);
安装Windows2000以上操作系统,VisualC++开发工具。
任务
要求
利用课余时间去图书馆或上网查阅课题相关资料,深入理解课题含义及设计要求,注意材料收集与整理;
在第16周末之前完成预设计,并请指导教师审查,通过后方可进行下一步工作;
本课题要求至少用三种方法解决八皇后问题,输入棋盘的阶层,然后显示共有多少种布局方案,并显示每一种方案的具体情况。
结束后,及时提交设计报告(含纸质稿、电子稿),要求格式规范、内容完整、结论正确,正文字数不少于3000字(不含代码)。
工作进度计划
序号
起止日期
工作内容
1
在预设计的基础上,进一步查阅资料,完善设计方案,形成书面材料。
2
.7~
设计总体方案,构建、绘制流程框图,编写代码,上机调试。
3
测试程序,优化代码,增强功能,撰写设计报告。
4
提交软件代码、设计报告,参加答辩,根据教师反馈意见,修改、完善设计报告。
指导教师(签章):
年月日
摘要:
众所周知的八皇后问题是一个非常古老的问题,具体如下:
在8*8的国际象棋棋盘上放置了八个皇后,要求没有一个皇后能吃掉另一个皇后,即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上,这是做出这个课题的基础。
要求编写实现八皇后问题的递归解法或非递归解法,对于任意给定的一个初始位置,输出八皇后问题的一个布局。
本次设计旨在学习各种算法,训练对基础知识和基本方法的综合运用及变通能力,增强对算法的理解能力,提高软件设计能力。
在实践中培养独立分析问题和解决问题的作风和能力。
要求熟练运用C++语言、基本算法的基础知识,独立编制一个具有中等难度的、解决实际应用问题的应用程序。
通过对题意的分析与计算,用递归法回溯法及枚举法解决八皇后是比较适合的。
递归是一种比较简单的且比较古老的算法。
回溯法是递归法的升华,在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。
而枚举法,更是一种基础易懂简洁的方法。
把它们综合起来,就构成了今天的算法。
不论用什么法做这个课题,重要的就是先搞清楚哪个位置是合法的放皇后的位置,哪个不能,要先判断,后放置。
关键词:
八皇后;递归法;回溯法;数组;枚举法…….
1课题综述
八皇后问题概述
八皇后问题是一个古老而著名的问题。
该问题是十九世纪著名的数学家高斯1850提出;在8×8格的国际象棋上摆放八皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
高斯认为有76种方案。
1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后人有人用图论的方法解出92宗结果。
虽然问题的关键在于如何判定某个皇后所在的行、列、斜线是否有别的皇后;可以从矩阵的特点上找到规律,如果在同一行,则行号相同;如果在同一列上,则列号相同;如果同在“/”斜线上的行列值之和相同;如果在对角线上,则行列号之和或之差相等,逐个纪录符合题意的情况,最终得出解。
(如图1-1,是八皇后问题的一个实例图)
图1-1八皇后棋盘实例
预期目标
运用C++程序设计的编程思想编写代码,实现八皇后问题的所有(92种)摆放情况。
要求在DOS界面上显示出每一种方式。
八皇后问题课题要求
编写代码,用至少三种方法解决八皇后问题。
运行程序后,显现下面的参考界面:
八皇后问题
============
1.方法一
2.方法二
3.方法三
请选择(1、2或3,0:
退出):
图1-2输出界面实例
选择一个菜单后,要求输入棋盘的阶层,即N。
输入后,显示共有多少种布局方案,并显示每一种方案的具体情况,如下图:
77:
(0,2)(1,0)(2,6)(3,4)(4,7)(5,1)(6,3)(7,5)
78:
(0,7)(1,1)(2,4)(3,2)(4,0)(5,6)(6,3)(7,5)
图1-3输出样式实例
面对的问题
需要用三种方法解决八皇后问题,在这里需要查阅大量资料并多加练习,才能成功编写程序。
主要要解决下面的问题:
冲突:
包括列、行、两条对角线;
列:
规定每一列放一个皇后,就不会造成列上的冲突;
行:
当第i行被某个皇后占据时,该行所有空格就都不能放置其他皇后;
对角线:
对角线有两个方向,在同一对角线上的所有点都不能有冲突。
2需求分析
涉及到的知识基础
在本次的课程设计中,用到的知识点主要有:
类、函数、选择结构里的条件语句、循环结构里的while语句以及for循环语句、控制语句里的break语句、以及字符串函数的运用等等,并且应用到递归、回溯及穷举等比较经典的算法。
类
类定义
类就是用户自定义的数据类型。
类定义的一般形式如下:
class类名
{
细节;(数据成员,成员函数)
};
类函数定义
类成员函数类的成员函数通常在类外定义,一般形式如下:
返回类型类名:
:
函数名(形参表)
{
函数体;
}
双冒号:
:
是域运算符,主要用于类的成员函数的定义。
函数
函数的定义
定义函数需要指明:
函数执行结果返回值的类型、函数名、形式参数(简称形参)和函数体。
一般形式为:
数据类型函数名(行参表)
{
语句序列;
Return合适类型数值
}
数据类型
规定了函数返回值类型。
党执行函数体中的语句后,通常会产生一个结果,这就是函数的返回值,它可以是任何有效的类型。
若函数执行后不返回值,数据类型习惯用void来表示。
如果在函数定义时没有数据类型出现,则默认为函数返回值为整型值(int)。
函数调用
调用一个函数之前必须对该函数进行说明。
函数调用由函数名和函数调用运算符()组成,()内有0个或多个逗号分隔的参数(称为实参)。
每一个参数是一个表达式,且参数的个数与参数的类型要与被调函数定义的参数(称为形参)个数和类型匹配。
当被调函数执行时,首先计算实参表达式,并将结果值传送给行参,然后执行函数体,返回的返回值被传送到调用函数。
如果函数调用后有返回值,调用表达是可以用在表达式中,而无参函数的调用是一个单独的语句。
选择结构
用if语句实现选择结构设计
if语句的基本形式可分为两种:
(1)if(表达式)语句
其执行过程是,首先计算表达式的值,若不为0,条件判断为真,则执行()后面的语句,否则,if语句中止执行,即不执行()后面的语句。
(2)if(表达式)语句1
else语句2
其执行过程是,首先计算表达式的值,若不为0,条件判断为真,则执行()后面的语句,否则执行语句2。
if语句嵌套
if语句中的任何一个子句可以是任意可执行语句,当然也可以是一条if语句,这种情况称为if语句嵌套。
当出现if语句的嵌套时,不管书写格式如何,else格式都将与它前面最靠近的未曾配对的if语句相配对,构成一条完整的if语句。
它的格式为:
if(表达式1)语句1;
elseif(表达式2)语句2;
……
elseif(表达式n)语句n;
else语句n+1;
while和do-while语句
while语句用来实现“当型”循环结构,即先判断表达式,然后判断循环条件是否成立。
其一般形式为:
do
{
语句;
●○○○○○○○
○○○○●○○○
○○○○○○○●
○○○○○●○○
○○●○○○○○
○○○○○○●○
○●○○○○○○
○○○●○○○○
图2-1“1”作为皇后图2-2棋盘中的八皇后位置显示
3模块及算法设计
算法描述
递归法
递归是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现像.
递归算法一般用于解决三类问题:
(1)数据的定义是按递归定义的。
(Fibonacci函数)
(2)问题解法按递归算法实现。
(回溯)(3)数据的结构形式是按递归定义的。
(树的遍历,图的搜索)
能采用递归描述的算法通常有这样的特征:
为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。
回溯法
回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。
按选优条件向前搜索,以达到目标。
但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
可用回溯法求解的问题P,通常要能表达为:
对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)|xi∈Si,i=1,2,…,n},给定关于n元组中的一个分量的一个约束集D,要求E中满足D的全部约束条件的所有n元组。
其中Si是分量xi的定义域,且|Si|有限,i=1,2,…,n。
我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。
回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T,把在E中求问题P的所有解转化为在T中搜索问题P的所有解。
树T类似于检索树,它可以这样构造:
设Si中的元素可排成xi
(1),xi
(2),…,xi(mi-1),|Si|=mi,i=1,2,…,n。
从根开始,让T的第I层的每一个结点都有mi个儿子。
这mi个儿子到它们的双亲的边,按从左到右的次序,分别带权xi+1
(1),xi+1
(2),…,xi+1(mi),i=0,1,2,…,n-1。
照这种构造方式,E中的一个n元组(x1,x2,…,xn)对应于T中的一个叶子结点,T的根到这个叶子结点的路径上依次的n条边的权分别为x1,x2,…,xn,反之亦然。
另外,对于任意的0≤i≤n-1,E中n元组(x1,x2,…,xn)的一个前缀I元组(x1,x2,…,xi)对应于T中的一个非叶子结点,T的根到这个非叶子结点的路径上依次的I条边的权分别为x1,x2,…,xi,反之亦然。
特别,E中的任意一个n元组的空前缀(),对应于T的根。
因而,在E中寻找问题P的一个解等价于在T中搜索一个叶子结点,要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1,x2,…,xn满足约束集D的全部约束。
在T中搜索所要求的叶子结点,很自然的一种方式是从根出发,按深度优先的策略逐步深入,即依次搜索满足约束条件的前缀1元组(x1i)、前缀2元组(x1,x2)、…,前缀I元组(x1,x2,…,xi),…,直到i=n为止。
在回溯法中,上述引入的树被称为问题P的状态空间树;树T上任意一个结点被称为问题P的状态结点;树T上的任意一个叶子结点被称为问题P的一个解状态结点;树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点,它对应于问题P的一个解。
穷举法
顾名思义,穷举法就是通过把需要解决问题的所有可能情况逐一试验来找出符合条件的解的方法,对于许多毫无规律的问题而言,穷举法用时间上的牺牲换来了解的全面性保证,尤其是随着计算机运算速度的飞速发展,穷举法的形象已经不再是最低等和原始的无奈之举,比如经常有黑客在几乎没有任何已知信息的情况下利用穷举法来破译密码,足见这种方法还是有其适用的领域的。
可是,在实际生活中,只有很少的一些问题是真正意义上的“毫无规律”,其余的大多数仍有内在规律可循,对于这些问题,使用穷举法在效率上就显得比较低下,而在一些对速度要求较高的区域和规模较大的问题上,效率的低下往往是致命的。
.详细流程图
数据初始化
从当前点当前方向开始,判断能否向前走
结束程序
向前走一步
(入栈)
是否已到达目标位置
输出结果
新位置作为当前点
方向数加1
方向数是否超界
退回一步(退栈)
是否已经回到起点
能
否
否
否
是
是
是
否
图3-3解决八皇后问题的基本流程图
4.代码编写
八皇后问题是在限制条件下的排序问题
include<>法一:
递归法‖"< cout<<"\t"<<"‖2.方法二: 运用类‖"< cout<<"\t"<<"‖3.方法三: 穷举法‖"< cout<<"\t"<<"‖0.后退‖"< cout<<"\t"<<"‖‖"< cout<<"\t"<<"‖请选择(1、2,或者0): ‖"< cout<<"\t"<<"‖----------------------------------------‖"< cout<<"\t"<<"‖________________________________________‖"< } intmain() 然这次实验还是有很多问题的。 比如程序设计的界面不够好,一些程序并非自己所写,而是修改某些程序而成,但这些不该,在下次课程设计时不会再发生. 在编写代码时,我希望能随机选择一数X(1~92)后,能输出该种情况所对应的八个皇后的摆放方式和每个皇后所在的位置,但想了好久,就是无法实现。 而且,当92种情况都输出时,前面的几十种情况无法看到,要想让摆放皇后的图形和所在具体的位置一起输出,就得修改程序让使她们一个一个地输出,这样显然比较麻烦。 针对八皇后这个课题,也许表层只局限于对八个皇后的摆放,但还可以对更多的情况进行探讨分析,比如九皇后,十皇后等等。 在报告正文中已经多次提到关于N皇后的设计方法,但只是一带而过,有些问题很难通过一个报告设计就轻而易举的得到解决,还需要花费更多的时间。 也许随着皇后个数的增多,程序运行的时间将变得很长,我们能否将运行的时间缩短呢 致谢 课程设计终于告一段落了,一周的努力过后,也算是颇有收获,很多以前不清楚、不熟悉的内容都在这一周的努力中得到了锻炼,感谢老师给予的大量帮助及指导,感谢同学们的帮助,才让我顺利完成了这次的课程设计! 通过他们们的帮助,我深刻体会到: 做程序设计需要团队共同努力,共同贡献自己的力量,才能编写出一段好的程序,谢谢你们! 在此,由衷的感谢淮阴工学院、计算机工程系提供的实践机会,实验室人员提供的实验环境,让我可以在不断地调试中完善程序;感谢指导教师王晓燕、戴俊峰的辛勤指导,让我认识这个课题、熟悉这个课题并且最后完成这个课题;感谢同组同学的互帮互助,提供那么多经典程序供我参考并且指出了许多我的编程过程中出现的问题;感谢我的导师,在我遇到困难难以完成时,他总会给我宝贵的建议,帮助我战胜困难;感谢参考文献的原作者,以及给过我帮助的所有人员! 可以说本次的实验并不是仅仅有我一个人在努力,是通过的大家的帮助,和我个人的劳动共同得出的,我不会忘记你们给我的支持,谢谢你们! 感谢帮助过我的每一个人! 谢谢! ! 参考文献 1于永彦,于长辉,刘作军.C++程序设计《实践教学指导书》.淮安市淮海路小学印刷厂,00000000 2谭浩强,C程序设计.北京: 清华大学出版社,1998 3吴乃陵,况迎辉.C++程序设计.第二版.北京: 高等教育出版社,2006 4求是科技.C&C++实效编程百例.人民邮电出版社,2004 5蒋爱军,李师贤,梅骁勇.C++Primer习题解答.第四版.人民邮电出版社,2006 6於春景.实用C++调试指南.华中理工大学出版社,2006 7徐惠民.C++大学基础教程.人民邮电出版社,2004 8於春景.实用C++调试指南.华中理工大学出版社,2006 指导教师评语 学号 04 姓名 李金伟 班级 计算机1102班 选题 名称 八皇后 序号 评价内容 权重(%) 得分 1 考勤记录、学习态度、工作作风与表现。 5 2 自学情况: 上网检索机时数、文献阅读情况(笔记)。 10 3 论文选题是否先进,是否具有前沿性或前瞻性。 5 4 成果验收: 是否完成设计任务;能否运行、可操作性如何等。 20 5 报告的格式规范程度、是否图文并茂、语言规范及流畅程度;主题是否鲜明、重心是否突出、论述是否充分、结论是否正确;是否提出了自己的独到见解。 30 6 文献引用是否合理、充分、真实。 5 7 答辩情况: 自我陈述、回答问题的正确性、用语准确性、逻辑思维、是否具有独到见解等。 25 合计 指导教师(签章): 年月日
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 皇后 课程设计 实验 报告 C+