- 1、本文档共14页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构
实习报告
专业:数字媒体技术
姓名:李义
年级:2013级
学号:201301052015
完成日期:2015.12.31
题目:八皇后问题
一、项目简介
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8?8格的国际象棋棋盘上,安放八个皇后,要求没有一个皇后能够“吃掉”任何其他一个皇后,即任意两个皇后都不能处于同一行、同一列或同一条对角线上,求解有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法得出结论,有92种摆法。
二、概要设计
2.1 主要模块:
这个程序主要由4个模块组成,分别是画棋盘模块,画皇后模块,输出皇后摆法模块,和解决如何摆置皇后模块。这4个模块隶属于主函数模块。既主函数通过对这4个模块的合理调用解决“8皇后问题”,同时这4个模块之间也互有调用。
2.2 程序设计的数据结构及其关系:
数据结构的实现:数组a[i]:a [i]表示第i个皇后放置的列;i的范围:1-8;对角线数组:b[j](主对角线),c[j](从对角线),根据程序的运行,去决定主从对角线是否放入皇后;然后进行数据的初始化。从n列开始摆放第n个皇后(因为这样便可以符合每一竖列一个皇后的要求),先测试当前位置(n,m)是否等于0(未被占领):如果是,摆放第n个皇后,并宣布占领(切记要横列竖列斜列一起来),接着进行递归;如果不是,测试下一个位置(n,m+1),但是如果当时,却发现此时已经无法摆放时,便要进行回溯。
三 、详细设计
3.1 定义相关的数据类型:
3.1.1 定义的相关数据类型:
int A[21],B[21],C[21],Y[8];
void *buff1,*buff2
3.1.2 设计思想:
本程序通过对子函数void qu(int i)的调用,将八皇后的问题关键通过数据结构的思想予以了实现。虽然题目以及演算看起来都比较复杂,繁琐,但在实际中,只要当一只皇后放入棋盘后,在横与列、斜线上没有另外一只皇后与其冲突,再对皇后的定位进行相关的判断。即可完成。如果在这个程序中,我们运用的是非递归的思想,那么将大量使用if等语句,并通过不断的判断,去推出答案,而且这种非递归的思想,大大的增加了程序的时间复杂度。如果我们使用了数据结构中的算法后,那么程序的时间复杂度,以及相关的代码简化都能取得不错的改进。这个程序,我运用到了数据结构中的栈、数组,以及树和回溯的方法。特别是在对于树以及二叉树的学习,更是为八皇后的问题提供了科学的解决方案,通过对树的分析,把八皇后的问题看成了树,而在衍生第一个变化后,上面的第一层八个变化就变成了八个结点,而这八个结点再继续的衍生??,这样比较形象的将八皇后的问题简单化了。然后再通过回溯法进行设计,回溯法是设计递归过程的一个重要的方法。它的求解过程实质上是一个先序遍历一棵“状态树“的过程。在这个程序设计中,它先进行判断,棋盘上是否已经得到一个完整的布局(即棋盘是否已经摆上8个棋子),如果是,则输出布局;如果不是则依次先根遍历满足约束条件的各棵子树,流程即是:
判断该子树根的布局是否合法:如果合法的话,则先根遍历该子树;如果不合法的话,则剪去该子树的分支。
3.2 相关代码及算法
3.2.1 主模块C码算法:
void main(void)
{
Queen Q;
int gdriver=DETECT,gmode;
initgraph(gdriver,gmode,D://Win-TC);
SetQueen(Q);
setcolor(YELLOW);
QueenPic();
cleardevice();
setcolor(LIGHTGREEN);
settextstyle(0,0,3);
outtextxy(180,10,Eight Queens);
setcolor(WHITE);
settextstyle(0,0,1);
outtextxy(250,400,2009.11.8 3:30pm);
QueenRe(Q,0);
getch();
closegraph();
}
3.2.2 棋盘模块C码算法
void Checker(void) /* 画棋盘函数 */
{
int i,k;
for(k=0;k8;k++)
for(i=0;i8;i++)
if(k%2==0i%2==0||k%2!=0i%2!=0)
{
setfillstyle(SOLID_FILL,LIGHTBLUE);
setcolor(LIGHTBLUE);
rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);
floodfill(i*20+10,20+k*20+10,L
您可能关注的文档
- 油库第二章第六节材料.ppt
- 人民解放军百万大军横渡长江__优秀课件资料.ppt
- 天云趋势产品介绍-v1.0资料.pptx
- 数据备份、恢复和报表资料.ppt
- 添加网络打印机的各种方式以及打印机连接数量设置资料.doc
- 脑卒中康复护理资料.ppt
- 数据备份与恢复资料.doc
- 电力电子与MATLAB应用技术综述.ppt
- 人民警察的义务和纪律资料.ppt
- 数据仓库开发实例资料.ppt
- 2023年江苏省镇江市润州区中考生物二模试卷+答案解析.pdf
- 2023年江苏省徐州市邳州市运河中学中考生物二模试卷+答案解析.pdf
- 2023年江苏省苏州市吴中区中考冲刺数学模拟预测卷+答案解析.pdf
- 2023年江苏省南通市崇川区田家炳中学中考数学四模试卷+答案解析.pdf
- 2023年江西省吉安市中考物理模拟试卷(一)+答案解析.pdf
- 2023年江苏省泰州市海陵区九年级(下)中考三模数学试卷+答案解析.pdf
- 2023年江苏省苏州市高新二中中考数学二模试卷+答案解析.pdf
- 2023年江苏省南通市九年级数学中考复习模拟卷+答案解析.pdf
- 2023年江苏省南通市海安市九年级数学模拟卷+答案解析.pdf
- 2023年江苏省泰州市靖江外国语学校中考数学一调试卷+答案解析.pdf
最近下载
- 通用学术英语进阶(北京科技大学)中国大学MOOC(慕课)章节测验试题(答案).pdf
- 必威体育精装版部编版语文期末复习三年级非连续性文本阅读(附参考答案).docx
- 政务服务中心软硬件项目运维服务方案2.doc VIP
- 火力发电厂直接空冷工程技术规范初稿.doc
- 2024年河北省继续医学教育公共选修课参考答案.pdf VIP
- 老友记台词剧本第一季第1集中英双语左右对照.pdf
- 2024-2025学年广东省广州市省实教育集团初三数学试题第一次模拟考试试题含解析.doc VIP
- 【国家标准】国家职业技能标准 (2019年版) 起重装卸机械操作工.pdf
- 肺结核诊疗方案毕业设计.docx
- 2024年广东省职业院校技能大赛(中职组)智慧物流作业赛项考试题库(含答案).docx VIP
文档评论(0)