课程设计题目：
名称：八皇后问题
内容：设计程序完成如下要求：在8×8的国际象棋棋盘上，放置8个皇后，使得这8个棋子不能互相被对方吃掉。要求：(1)依次输出各种成功的放置方法。(2)最好能画出棋盘的图形形式，并在其上动态地标注行走的过程。(3)程序能方便地移植到其他规格的棋盘上。一、问题分析和任务定义
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，根据国际象棋的规定，皇后可以攻击与它在同一行、同一列或者同一斜线上的棋子，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。在8!=40320种排列中共有92种解决方案。
本程序需要解决的问题有：
1、建立合适的数据类型表示皇后在棋盘上所处的位置。
2、成功的输出全部正确的放置方法。
3、画出棋盘形式，在上面动态的标注其行走的过程。
二、数据结构的选择和概要设计
1、为了简单易行的表示皇后在棋盘所处的位置，在此建立一个整型数组queen[i]来表示，若queen[3]=2则表示皇后处在8×8棋盘的第三行和第二列。
2、表示好皇后以后，设计judge( )和check( )函数来检测第一个皇后的同列和同斜线上有没有其他皇后（程序以行为基础，逐行试探每列和斜线上是否有皇后）。然后设计输出函数show( )和print( )分别输出正确解法的排列形式和棋盘摆放形式。在输出棋盘的步骤中，设计一个递归函数go( )实现棋盘的输出。
3、程序的流程图如下图所示：
图1 程序流程图
三、详细设计和编码
1、首先定义整型数组queen[i]表示皇后的位置，i的取值由0到7表示八个皇后。然后定义一个整型变量count来统计所有正确解法的个数。
2、因为每行只能摆放一个皇后，所以在皇后不在同一行的基础上，设计检测函数检测皇后的同列和同斜线上是否存在其他皇后。检测是否同列的时候，定义两个变量i和j表示两个皇后所在的行数，则用queen[i]和queen[j]表示它们所在的列数，通过验证queen[i]和queen[j]是否相等确定两个皇后是否处于同一列上。检测同斜线的时候，用到了求绝对值的函数abs( )函数，用abs(p[j]-p[i])==j-i是否相等来验证任意两个皇后是否在同一斜线上。int judge(int *p, int j) //检测皇后是否在同列或者同一斜线上
{int i;
for(i=0;i { if(p[j]==p[i]) return 0; if(abs(p[j]-p[i])==j-i) //皇后在同一斜线上的情况 return 0; } return 1; } int check(int queen[], int i) //检测棋盘布局是否合法 { int j, k; for (j=0;j<=i;j++) { for(k=0;k<=i;k++) { if(j!=k&&(queen[j]==queen[k]||abs(queen[j]-queen[k])==abs(j-k))) //皇后不在同一行且在同一列或者同一斜线时 { return 0; } } } return 1; } 3、设计输出函数输出八皇后问题的正确解法，首先编写show（）函数输出排列形式，为了方便，将正确解法的判定条件编写在输出函数中，用多个for循环条件语句筛选可行方案，执行之后输出所有正确方法的排列形式和正确解法的个数。然后编写print( )函数输出棋盘形式，按行扫描，用for循环条件语句判定条件之后，皇后输出“Q”，非皇后位置输出“+”，在递归函数go( )中调用print( )函数可以完整的输出所有正确解法的棋盘形式。 void show(int queen[]) {int i=0,j=0,amount=0; for(queen[0]=0;queen[0]<8;j=0,queen[j]++)//按行开始逐行试探每一列上的皇后位置是否合法 for(queen[++j]=0;queen[j]<8;j=1,queen[j]++) if(judge(queen,j)) for(queen[++j]=0;queen[j]<8;j=2,queen[j]++) if(judge(queen,j)) for(queen[++j]=0;queen[j]<8;j=3,queen[j]++) if(judge(queen,j)) for(queen[++j]=0;queen[j]<8;j=4,queen[j]++) if(judge(queen,j)) for(queen[++j]=0;queen[j]<8;j=5,queen[j]++) if(judge(queen,j)) for(queen[++j]=0;queen[j]<8;j=6,queen[j]++) if(judge(queen,j)) for(queen[++j]=0;queen[j]<8;queen[j]++) if(judge(queen,j)) {for(i=0;i<8;i++) printf(" %d ",queen[i]); //输出正确解法的排列形式 ++amount; //统计所有正确解法的个数 printf("\n");} printf("\nthere is %d answer\n",amount); void print(int queen[]) //输出皇后在棋盘上的摆放形式 { int i,j; for(i=0;i<8;i++) { for(j=0;j { printf("+ "); } printf("Q"); //输出Q表示皇后 for(j=7;j>queen[i];j--)//皇后后面输出"+" { printf(" +"); }; } printf("press anykey to show next answer:"); getchar(); //接收字符 } 4、编写程序主函数，在main( )中调用各个功能函数实现八皇后问题的要求，其中运用getchar( )函数接收字符，设置按任意键继续的功能。 5、注：本次课程设计主要运用Visual C++6.0的编译环境，无法使用清屏函数，在turboc 的编译环境中，使用clrscr( )清屏函数可以实现动态的输出皇后在棋盘上的摆放形式。详细代码如下： void print(int queen[]) //动态输出棋盘摆放形式 { int i,j; clrscr(); //清屏函数 for(i=0;i<8;i++) {for(j=0;j {printf("+ ");} printf("Q"); //皇后 for(j=7;j>queen[i];j--) { printf(" +");}; //每行中皇后后面的棋盘 printf("\n"); } clrscr(); } 四、上机调试 本次课程设计中遇到了许多的困难，产生了不少的问题。 1、刚开始使用结构体表示皇后的位置，构造了较多的变量，程序设计中产生了许多的错误，判断同斜线情况不太方便，算法性能也不少很好。后来想到运用数组来表示皇后的位置，不但数据结构简单，而且较容易的表示处皇后的位置，容易分析皇后同列、同斜线的情 况（用到abs( )函数），所以建立整型数组来表示皇后在棋盘上的位置。 2、动态输出棋盘摆放形式的时候，自动输出的速度太快，无法观察清楚，后来只好运用getchar( )函数接受一个空的字符手动控制棋盘的输出。 五、测试结果及其分析 程序运行结果如下各图所示： 分析：本次课程设计完成之后，仍觉得有些不足之处，例如无法让电脑自动输出动态的摆放皇后过程，必须手动操作完成。算法的时间复杂度也不是很好。 各函数的时间复杂度如下： int judge(int *p, int j) 时间复杂度为O(n) int check(int queen[], int i) 时间复杂度为O(n2) void show(int queen[]) 时间复杂度为O(n9) void print(int queen[]) 时间复杂度为O(n2) void go(int queen[], int i) 时间复杂度为O(n) 图2 程序运行结果部分截图(1) 图3 程序运行结果部分截图(2) 图4 程序运行结果部分截图(3) 工学院 数据结构课程设计报告设计题目：八皇后 2008 年 6 月25 日 设计任务书 摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法 目录 1. 课题综述 (1) 1.1课题的来源及意义 (1) 1.2面对的问题 (1) 2. 需求分析 (1) 2.1涉及到的知识 (2) 2.2软硬件的需求 (2) 2.3功能需求 (2) 3. 概要设计 (2) 4. 详细设计和实现 (3) 4.1算法描述及详细流程图 (3) 4.1.1算法描述 (3) 4.1.2算法流程图 (3) 5. 代码编写及详细注释 (4) 6. 程序调试 (8) 6.1调试过程、步骤及遇到的问题 (8) 7. 运行与测试 (8) 7.1运行演示 (8) 总结 (10) 致 (11) 参考文献 (12) . 1. 课题综述 1. 1课题的来源及意义 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。 到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。 1. 2 面对的问题 1）解决冲突问题： 这个问题包括了行，列，两条对角线； 列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； 2）使用数据结构的知识，用递归法解决问题。 2. 需求分析 年级：八年级姓名：日期：3月6日 实验名称：用弹簧测力计测量力的大小 一、实验目的 1.练习使用弹簧测力计。 2.正确使用弹簧测力计测量力的大小。 二、实验仪器和器材（要求标明各仪器的规格型号） 弹簧测力计2个（规格相同），钩码2个，铁架台。 三、实验步骤或内容： 1.检查实验器材。 2.测量手的拉力。 3.测量钩码所受的重力。 4.测两个弹簧测力计相互作用的拉力。 5.整理器材。 五、实验记录与结论 1.弹簧测力计的量程 0-5N ，分度值 0.2N ，指针是否指零刻线是。 2.记录数据： 年级：八年级姓名：日期： 实验名称：探究重力的大小与质量的关系。 一、实验目的 探究重力的大小与质量的关系。 二、实验仪器和器材（要求标明各仪器的规格型号） 弹簧测力计，铁架台，相同的钩码5个(质量已知)，铅笔， 刻度尺。 三、实验步骤或内容：要求步骤或内容简单明了 （1）检查器材：观察弹簧测力计的量程、分度值，指针是否指到 零刻度线。 （2）将弹簧测力计悬挂在支架上。 （3）将钩码逐个加挂在弹簧测力计上。 （4）将5次的测量结果记录在表格中。 (5)整理器材。 四、实验记录与结论 1.观察弹簧测力计的量程为 0-5N N，分度值为 0.2 N。 实验结论： 重力的大小跟物体的质量的关系是物体所受重力与物体质量成 正比。 年级：八年级姓名：日期： 实验名称：探究影响滑动摩擦力大小的因素 一、实验目的 探究压力的大小和接触面的粗糙程度对滑动摩擦力大小的影响。 二、实验仪器和器材（要求标明各仪器的规格型号） 木块，砝码，弹簧测力计，毛巾。 三、实验步骤或内容：要求步骤或内容简单明了 （1）检查器材：观察弹簧测力计的量程和分度值，指针是否指在零刻线处。（2）当木块在水平桌面上运动，测出压力F=G木块时木块受到的滑动摩擦力。（3）改变压力，将砝码放在木块上，测出木块压力F＞G木块时木块受到的滑动摩擦力。 （4）改变接触面的粗糙程度，将毛巾平铺在水平桌面上，测出压力F=G木块时木块受到的滑动摩擦力。 （5）整理器材。 五、实验记录与结论 （1）弹簧测力计的量程为0-5N，分度值为0.2N。 (3)实验结论： 在接触面相同时，压力越大，滑动摩擦力越大；在压力相等的情况下，接触表面越粗糙，滑动摩擦力越大。 //运行环境TC3.0 #include 数据结构课程设计 选题：八皇后问题 姓名： 学号： 指导老师： 目录 一.选题概述---------------------------------------3 二.设计要求与分析--------------------------------3 三.数据结构与定义--------------------------------4 1.结构体定义 2.函数定义 3.函数之间的定义 四.程序段与分析----------------------------------5 五.完整程序代码及运行结果截图------------------7 六.心得体会--------------------------------------10 七.参考文献--------------------------------------10 一．选题概述： 在实际应用中，有相当一类问题需要找出它的解集合，或者要求找出某些约束条件下的最优解。求解时经常使用一种称为回溯的方法来解决。所谓回溯就是走回头路，该方法是在一定的约束条件下试探地搜索前进，若前进中受阻，则回头另择通路继续搜索。为了能够沿着原路逆序回退，需用栈来保存曾经到达的每一个状态，栈顶的状态即为回退的第一站，因此回溯法均可利用栈来实现。而解决八皇后问题就是利用回溯法和栈来实现的。 二．设计要求与分析 八皇后问题是在8x8的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线。 八皇后在棋盘上分布的各种可能的格局，其数目非常大，约等于232种，但是，可以将一些明显不满足问题要求的格局排除掉。由于任意两个皇后不能同行，即每一行只能放置一个皇后，因此将第i个皇后放置在第i行上。这样在放置第i个皇后时，只要考虑它与前i 一1个皇后处于不同列和不同对角线位置上即可。因此，其算法基本思想如下： 从第1行起逐行放置皇后，每放置一个皇后均需要依次对第1，2，…，8列进行试探，并尽可能取小的列数。若当前试探的列位置 一练习使用弹簧测力计 班级姓名 实验目的：会正确使用弹簧测力计 实验器材：弹簧测力计一个，其余学生自备。 1.观察：弹簧测力计的量程是，分度值是。 2.检查：指针是否指在零刻度线上？指针是否与平板之间有摩擦? 3.感受： 用手拉测力计，使指针分别指在1N、3N、5N，感受一下1N、3N、5N的力的大小。 4.测量： （1）把笔袋挂在挂钩上，提起笔袋，笔袋对测力计的拉力，F= （2）把笔袋挂在挂钩上，在桌面上水平拖动笔袋，笔袋对测力计的拉力，F= （3）拉断一根头发，所需要的力，F= 5．使用弹簧测力计时： （1）如果所测量的力的大小超出测力计的量程，会 （2）如果没有认清分度值，会 （3）如果指针指在零刻度线的上方或下方就进行测量，会使测量值或 二探究重力的大小跟质量的关系 班级姓名 实验目的：正确使用弹簧测力计，正确记录实验数据，正确绘制数据图像，根据实验数据和图像总结出重力的大小跟质量的关系 实验器材：弹簧测力计一个，勾码一盒。 1.看勾码盒上的标注，每个勾码的质量是kg。 2.逐次增挂钩码个数，测出所受重力，并记录在下面的表格中。 3.在右图中，以质量为横坐标，重力为纵坐标， 描点并画出重力与质量的关系图像。 4.分析数据和图像，重力与质量的关系是 重力与质量的比值是（用g表示）。重力与质量的关系式用字母表示为： 5. 重力与质量的比值g=9.8N/kg，表示的物理意义是 三探究二力平衡的条件 班级姓名 实验目的：通过探究，知道作用在一个物体上的两个力满足什么条件时，才能平衡。 实验器材：长木板（两端有滑轮）一个，小车一个（两端有挂钩），钩码一盒，细绳两段。 1.小车保持平衡状态，是指小车处于状态或状态。 2.按右图所示装好器材 3. 两端挂上数量不相等的钩码，观察小车的运动状态。 4. 两端挂上数量相等的钩码，观察小车的运动状态。 5. 两端挂上数量相等的钩码，把小车在水平桌面上扭转一个角度后再放手，观察小车的运动状态。 把实验条件和观察到现象记录在下面的表格中 6.总结二力平衡的条件： 作用在同一个物体上的两个力，如果大小，方向，并且 ，这两个力就彼此平衡。这时物体就处于状态或状态。 人工智能课程设计报告 课班姓学程:人工智能课程设计报告级 : 名: 号: 指导教师:赵曼 2015年11月 人工智能课程设计报告 人工智能课程设计报告 课程背景 人工智能（Artificial Intelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，可以设想，未来人工智能带来的科技产品，将会是人类智慧的“容器”。 人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能，但能像人那样思考、也可能超过人的智能。 人工智能是一门极富挑战性的科学，从事这项工作的人必须懂得计算机知识，心理学和哲学。人工智能是包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，总的说来，人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。 人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。也被认为是二十一世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。这是因为近三十年来它获得了迅速的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，无论在理论和实践上都已自成一个系统。 人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、思考、规划等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可以说几乎是自然科学和社会科学的所有学科，其范围已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不仅限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的发展，数学常被认为是多种学科的基础科学，数学也进入语言、思维领域，人工智能学科也必须借用数学工具，数学不仅在标准逻辑、模糊数学等范围发挥作用，数学进入人工智能学科，它们将互相促进而更快地发展。 课程设计报告 课程名称数据结构课程设计 课题名称八皇后问题演示 专业通信工程 班级通信工程1081 学号 0103 姓名刘献文 指导教师田娟秀郭芳 2012年 7 月 6 日 湖南工程学院 课程设计任务书 课程名称数据结构 课题八皇后问题演示 专业班级通信工程1081 学生姓名刘献文 学号 0103 指导老师田娟秀郭芳 审批 任务书下达日期 2012 年 7 月 1 日 任务完成日期2012 年 7 月 6 日 1设计内容与设计要求 设计内容 （4）课题四：八皇后问题演示 八皇后问题是一个古老而着名的问题，是回溯算法的典型例题。该问题是十九世纪着名的数学家高斯1850年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。 设计思路：?解决8皇后时，在安放第i行皇后时，需要在列的方向从1到n试 探(j =1,…, n)：首先在第j列安放一个皇后，如果在列、主对角线、次对角线方 向有其它皇后，则出现攻击，撤消在第j列安放的皇后。如果没有出现攻击，在第 j列安放的皇后不动，递归安放第i+1行皇后。 对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动。要求用Turbo C或 MFC实现的八皇后问题的图形程序，能够演示全部的92组解。 选题方案： 所选题目根据学号确定，学号模6加1，即（学号%6+1）。如你的学号为9，则 所选题目号为：9%6+1＝（题目4）。注意，所有的课题都要求用图形方式演示步骤 和结果。同学们可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法。 设计要求： 课程设计报告规范 （1）需求分析 a.程序的功能。 b.输入输出的要求。 （2）概要设计 a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块 的功能。 b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的 结构，它们之间有什么关系等。 （3）详细设计 目录 1、课程设计的目的 (1) 2、课程设计的要求 (1) 3、课程设计的内容 (1) 3.1设计的内容 (1) 3.2算法思路 (1) 3.2.1算法的内容 (1) 3.2.2算法中函数的流程图 (1) 3.3程序调试与测试以及结果的分析 (3) 3.3.1详细设计 (3) 3.3.2遇到的问题及解决方法 (6) 3.3.3 算法的时空分 (6) 3.3.4结果分析 (6) 3.3.5 算法的改进 (6) 3.3.6 程序使用说明 (6) 3.3.7 测试结果 (7) 4、总结 (10) 5、参考文献 (10) 6、附录 (11) 八皇后问题 1、课程设计的目的 （1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； （4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风； 2、课程设计的要求 （1）设计的课题能够体现数据结构和算法的算法分析、设计、算法实现。 （2）根据自己对数据结构和算法的基本概念、原理和机制的理解，自拟题目和设计内容，选题尽可能结合实际的应用。 3、课程设计的内容 3.1设计的内容 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八皇后问题有92个解答。 我要设计的程序就是怎样把92种解答直观清晰的让大家了解和认识。 3.2算法思想 3.2.1算法的内容 （1）解数组a，a[i]表示第i个皇后放置的列，范围为1~8。 （2）行冲突标记数组b，b[j]=0 表示第j行空闲，b[j]=1 表示第j行被占领，范围为1~8。（3）对角线冲突标记数组c、d。c[i-j]=0 表示第（i-j）条对角线空闲，c[i-j]=1 表示第（i-j）条对角线被占领，范围-7~7。d[i+j]=0 表示第（i+j）条对角线空闲，d[i+j]=1 表示第（i+j）条对角线被占领，范围2~16。 （4）抽象数据类型的定义 Print() //打印每一列皇后的放置的行数以及以矩阵形式形象的显示皇后的放置位置JudgeQueen1() //递归寻找摆放皇后位子 void main() //主函数调用 3.2.2算法中函数的流程图 (1)数据初始化。 (2)从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当 计算机科学与技术专业 数据结构课程设计报告设计题目：八皇后问题 目录 1需求分析 (3) 1.1功能分析 (3) 1.2设计平台 (4) 2概要设计 (4) 2.1算法描述 (5) 2.2算法思想 (6) 2.3数据类型的定义 (6) 3详细设计和实现 (7) 3.1算法流程图 (7) 3.2 主程序 (7) 3.3 回溯算法程序 (8) 4调试与操作说明 (10) 4.1调试情况 (10) 4.2操作说明 (10) 5设计总结 (12) 参考文献 (13) 附录 (13) 1需求分析 1.1功能分析 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八皇后问题有92个解答。 1、本演示程序中，利用选择进行。程序运行后，首先要求用户选择模式，然后进入模式。皇后个数设0 南京理工大学紫金学院VC++课程设计报告 课程：VC++课程设计 系别：计算机系 班级： 学号： 姓名： 选题名称：八皇后问题 选题难易别：B级 起止时间：2011.11.21~2011.12.22 指导教师：朱俊 2011年 12 月 1．程序功能介绍 答：这个程序是用于解决八皇后问题的。八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。我的程序进入时会让使用者选择程序的功能，选【1】将会通过使用者自己手动输入第一个皇后的坐标后获得答案；选【2】将会让程序自动运算出固定每一个皇后后所有的排列结果。 2．课程设计要求 答：（1）增加函数，完成每输入一组解，暂停屏幕，显示“按任意键继续！”。 （2）完善程序，编程计算八皇后问题共有集中排列方案。 （3）增加输入，显示在第一个皇后确定后，共有几组排列。 （4）将每组解的期盼横向排列输出在屏幕上，将五个棋盘并排排列，即一次8行同时输出5个棋盘，同样完成一组解后屏幕暂停，按任意键继续。 （5）求出在什么位置固定一个皇后后，解的数量最多，在什么位置固定皇后后，解的数量最少，最多的解是多少，最少的解是多少，并将最多，最少解的皇后位置及所有的解求出，同样5个一组显示。 3．对课程题目的分析与注释 答：众所周知的八皇后问题是一个非常古老的问题，问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子。因此，本课程设计的目的也是通过用C++语言平台在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现。使用递归方法最终将其问题变得一目了然，更加易懂。首先要用到类，将程序合理化：我编辑了一个盘棋8*8的类：class Board，还有个回溯法的类：class Stack，关键的类好了，然后编辑好类的成员，然后编辑主函数利用好这些类的成员，让其运算出结果。 4．程序设计和说明（说明算法思想、设计思路，给出重要的、关键的代码） 答：算法思想： 初中物理实验报告单 年级：八年级姓名：日期：3月6日 实验名称：用弹簧测力计测量力的大小 一、实验目的 1.练习使用弹簧测力计。 2.正确使用弹簧测力计测量力的大小。 二、实验仪器和器材（要求标明各仪器的规格型号） 弹簧测力计2个（规格相同），钩码2个，铁架台。 三、实验步骤或内容： 1.检查实验器材。 2.测量手的拉力。 3.测量钩码所受的重力。 4.测两个弹簧测力计相互作用的拉力。 5.整理器材。 五、实验记录与结论 1.弹簧测力计的量程 0-5N ，分度值 0.2N ，指针是否指零刻线是。 2.记录数据： 初中物理实验报告单 年级：八年级姓名：日期： 实验名称：探究重力的大小与质量的关系。 一、实验目的 探究重力的大小与质量的关系。 二、实验仪器和器材（要求标明各仪器的规格型号） 弹簧测力计，铁架台，相同的钩码5个(质量已知)，铅笔， 刻度尺。 三、实验步骤或内容：要求步骤或内容简单明了 （1）检查器材：观察弹簧测力计的量程、分度值，指针是否指到 零刻度线。 （2）将弹簧测力计悬挂在支架上。 （3）将钩码逐个加挂在弹簧测力计上。 （4）将5次的测量结果记录在表格中。 (5)整理器材。 四、实验记录与结论 1.观察弹簧测力计的量程为 0-5N N，分度值为 0.2 实验结论： 重力的大小跟物体的质量的关系是物体所受重力与物体质量成 正比。 初中物理实验报告单 年级：八年级姓名：日期： 实验名称：探究影响滑动摩擦力大小的因素 一、实验目的 探究压力的大小和接触面的粗糙程度对滑动摩擦力大小的影响。 二、实验仪器和器材（要求标明各仪器的规格型号） 木块，砝码，弹簧测力计，毛巾。 淮阴工学院 C++程序设计课程设计报告 选题名称:八皇后 系（院）：计算机工程系 专业：计算机科学与技术 班级：计算机1084 姓名: XXX 学号:XXXXXXXXXX 指导教师:戴峻峰、赵建洋 学年学期:2008 ~ 2009 学年第 2 学期 2009 年 6 月13 日 设计任务书 指导教师（签章）： 年月日 摘要： 八皇后问题。这是由大数学家高斯于1850年首先提出来的，要求在8*8的方格国际象棋盘上放置8个皇后，任意两个皇后不能位于同一行，同一列或同一斜线（正斜或反斜线）上。输出所有可能的放法。分析：解此问题的基本思路为：开始时棋盘为空，第二个皇后可在第一行的任意位置上放置。一旦放置好第一个皇后，以后各行放置皇后时需检查当前列和同一斜线上是否已放置了皇后。如果未放置，则当前位置可放新的皇后，否则需试新的位置。假设前行的皇后已放好，现从当前行的第1列起选择适当的位置放置第5个皇后。显然第1，2列不能放置，因为这两个位置与第1，2行皇后的位置起冲突。第1个合适的位置是第3列（第4列也可以）。如果试探结果本行中没有合适的位置，则说明前面的皇后放置的位置不对，应回退到上一行，释放皇后原来占据的位置，改试下一个合适的位置。如果回退一行后本行仍然没有合适的位置，则继续回退；一旦当前的皇后放置好后，则前进一行放置下一个皇后。如此下去，直至8个皇后化全部放置好后，则前进一行放置下一个皇后。如此下去，直至8个皇后全部放置好时即可打印一个解。 关键词：八皇后，回溯法（试探法），递归法 目录 1 课程综述 (1) 1.1课程来源及意义 (1) 1.2预期目标 (1) 1.3面对的问题 (1) 1.4需解决的关键技术 (1) 2 需求分析联系 (1) 2.1涉及的知识基础 (1) 2.2解决问题的思路 (3) 2.3总体方案 (5) 2.4功能模块框图 (5) 3 模块及算法设计 (6) 3.1算法描述 (6) 3.2实现方法 (6) 3.3流程图 (7) 4 代码编写 (7) 5程序调试 (15) 5.1调试过程与步骤 (15) 5.2发现的问题 (15) 5.3解决的办法 (15) 6 运行与测试 (15) 7 结论 (17) 总结 (18) 致谢 (20) 参考文献 (21) 八皇后问题学 2012年 9 月 5 日 目录 一、选题 1.1背景知识 (2) 1.2设计目的与要求 (2) 二、算法设计 2.1问题分析 (3) 2.2算法设计 (3) 三、详细设计 3.1源程序清单 (4) 四、调试结果及分析 4.1调试结果 (6) 4.2调试分析 (7) 五、课程设计总结 5.1总结及体会 (7) 六、答辩 6.1答辩记录 (8) 6.2教师意见 (8) 一、选题及背景知识 1.1 背景知识 在国际象棋中，皇后是一个威力很大的棋子，她可以“横冲直撞”（在正负或垂直方向走任意步数），也可以“斜刺冲杀”（在正负45度方向走任意步数），所以在8*8的棋盘上要布互相不受攻击的皇后，最多只能布八个，共92种布法，再也不能有别的布法了——这就是著名的八皇后问题 在8*8的国际象棋棋盘上，放置八个皇后，使得这八个棋子不能互相被对方吃掉。也就是说一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 1.2 设计要求 要求：·判断在国际象棋中，能否在空棋盘上摆放8个皇后，并使其中任意两个皇后不能在同一行，同一列或同一对角线上。 ·编写完整的摆放八皇后问题的程序 ·具体要求第一个皇后的起始位置由键盘输入 二、算法设计 2.1问题分析 设计——图形表示下图中，Q代表皇后 假设在第k列上找到合适的位置放置一个皇后，要求它与第1——k-1列上的皇后不同行、列、对角线；可以从图上找到规律：不同列时成立，皇后放在第k列上；讨论行时，第j个皇后的位置（a[j] ，j）要与（i，k）位置的皇后不同行；如果同在／斜线上，行列值之和相同；如果同在＼斜线上，行列值之差相同；如果斜线不分方向则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同,可表示为（|a[j]-i|=|j-k|）。 2.2 算法设计 利用计算机运行速度快的特点，采用枚举法，逐一尝试各种摆放方式，来判断最终摆法。其中判断是否同在对角线上用到了：行数差的绝对值与列数差的绝对值相等， 八皇后问题 一、设计任务与目标 在8行8列的棋盘上放置8个皇后，皇后可吃掉与她处于同行或同列或同一对角线上的其他棋子，要使任一个皇后都不能吃掉其他的7个皇后，则需要同时控制同行，同列，同一条对角线的情况，然后当行，列，以及对角线都无皇后时，记录该点。并用“Q”表示皇后的位置，“+”表示其它位置。 二、方案设计与论证 定义4个具有全局作用域的数组int LineNum[9]; bool a[9], b[15]分别表示第几列的皇后要放的行位置，第几行上是否未放皇后，“/”斜对角线上是否未放皇后，“\”反斜对角线上是否未放皇后。通过语句“if ( a[j] && b[i+j-2] && c[i-j+7] ) LineNum[i]=j;”判断并实现一枚皇后是否放置安全。然而当第一枚皇后位置放置后，则它所在的行，列，以及对角线的记录状态需要改变后，才能进行下一枚皇后的放置。下一枚皇后判断位置的步骤与第一枚一样，所以可以用递归的方法进行下一枚皇后位置的放置。当第8枚皇后的位置确定后，就跳出递归。之后还要对之前每一个位置记录的情况初始化才能进行下一种放置八皇后的情况。 四、全部源程序清单 # include 淮阴工学院 数据结构课程设计报告 设计题目：八皇后 系（院）:计算机工程系 专业：信息安全 班级：信息 1 0 6 学生姓名: 叶青学号:1061303127 指导教师:张亚红寇海洲胡荣林夏森 学年学期: 2007 ~ 2008 学年第 2 学期 2008 年 6 月25 日 设计任务书 摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法 目录 1. 课题综述 (1) 1.1课题的来源及意义 (1) 1.2面对的问题 (1) 2. 需求分析 (1) 2.1涉及到的知识 (1) 2.2软硬件的需求 (1) 2.3功能需求 (2) 3. 概要设计 (2) 4. 详细设计和实现 (2) 4.1算法描述及详细流程图 (2) 4.1.1算法描述 (3) 4.1.2算法流程图 (3) 5. 代码编写及详细注释 (4) 6. 程序调试 (7) 6.1调试过程、步骤及遇到的问题 (7) 7. 运行与测试 (7) 7.1运行演示 (7) 总结 (9) 致谢 (10) 参考文献 (11) . 目录 一需求分析 (1) 1.1程序的功能： (1) 1.2程序的输入输出要求： (1) 二概要设计 (3) 2.1程序的主要模块： (3) 2.2程序涉及： (3) 三详细设计 (3) 3.1相关代码及算法 (4) 3.1.1 定义相关的数据类型如下：...................... 错误！未定义书签。 3.1.2 主模块类C码算法： (4) 3.1.3 画棋盘模块类C码算法 (5) 3.1.4 画皇后模块类C码算法： (5) 3.1.5 八皇后摆法模块（递归法）： (6) 3.1.6 初始化模块 (7) 3.1.7 输出摆放好的八皇后图形（动态演示）： (7) 3.2相关流程图 (9) 四调试分析 (12) 五设计体会 (13) 六附录 (13) 七参考文献 (17) 一需求分析 1.1 程序功能： 八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出的。八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子，问有多少种不同的摆法？并找出所有的摆法。因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。本程序通过对子函数void qu(int i)的调用，将八皇后的问题关键通过数据结构的思想予以了实现。虽然题目以及演算看起来都比较复杂，繁琐，但在实际中，只要当一只皇后放入棋盘后，在横与列、斜线上没有另外一只皇后与其冲突，再对皇后的定位进行相关的判断。即可完成。如果在这个程序中，我们运用的是非递归的思想，那么将大量使用if等语句，并通过不断的判断，去推出答案，而且这种非递归的思想，大大的增加了程序的时间复杂度。如果我们使用了数据结构中的算法后，那么程序的时间复杂度，以及相关的代码简化都能取得不错的改进。这个程序，我运用到了数据结构中的栈、数组，以及树和回溯的方法。特别是在对于树以及二叉树的学习，更是为八皇后的问题提供了科学的解决方案，通过对树的分析，把八皇后的问题看成了树，而在衍生第一个变化后，上面的第一层八个变化就变成了八个结点，而这八个结点再继续的衍生……，这样比较形象的将八皇后的问题简单化了。然后再通过回溯法进行设计，回溯法是设计递归过程的一个重要的方法。它的求解过程实质上是一个先序遍历一棵“状态树“的过程。在这个程序设计中，它先进行判断，棋盘上是否已经得到一个完整的布局（即棋盘是否已经摆上8个棋子），如果是，则输出布局；如果不是则依次先根遍历满足约束条件的各棵子树，流程即是： 判断该子树根的布局是否合法：如果合法的话，则先根遍历该子树；如果不合法的话，则剪去该子树的分支。 1.2 程序的输入输出要求： 用TC软件进行编译以及调试，调试正确之后，运行结果如下图： 庆坪中学探究实验报告单 八年级物理（下） 一练习使用弹簧测力计 班级姓名 实验目的：会正确使用弹簧测力计 实验器材：弹簧测力计一个，其余学生自备。 1.观察：弹簧测力计的量程是5N ，分度值是0.2N 。 2.检查：指针是否指在零刻度线上？指针是否与平板之间有摩擦? 3.感受： 用手拉测力计，使指针分别指在1N、3N、5N，感受一下1N、3N、5N的力的大小。 4.测量： （1）把笔袋挂在挂钩上，提起笔袋，笔袋对测力计的拉力，F= 4N （2）把笔袋挂在挂钩上，在桌面上水平拖动笔袋，笔袋对测力计的拉力，F=1.5N （3）拉断一根头发，所需要的力，F= 5．使用弹簧测力计时： （1）如果所测量的力的大小超出测力计的量程，会损坏弹簧秤 （2）如果没有认清分度值，会出现读数错误 （3）如果指针指在零刻度线的上方或下方就进行测量，会使测量值偏大或偏小 庆坪中学探究实验报告单 八年级物理（下） 二探究重力的大小跟质量的关系 班级姓名 实验目的：正确使用弹簧测力计，正确记录实验数据，正确绘制数据图像，根据实验数据和图像总结出重力的大小跟质量的关系 实验器材：弹簧测力计一个，勾码一盒。 1.看勾码盒上的标注，每个勾码的质量是0.05 kg。 2.逐次增挂钩码个数，测出所受重力，并记录在下面的表格中。 实验次数一个钩 码两个钩 码 三个钩 码 四个钩 码 五个钩 码 六个 钩码 质量m/kg 0.05 0.10 0.15 0.20 0.25 0.30 重力G/N 0.49 0.98 1.47 1.98 2.45 2.94 重力与质量之比9.8 9.8 9.8 9.8 9.8 9.8 3.在右图中，以质量为横坐标，重力为纵坐标， 描点并画出重力与质量的关系图像。 4.分析数据和图像，重力与质量的关系是 成正比关系 重力与质量的比值是9.8 （用g表示）。 重力与质量的关系式用字母表示为：G =mg 5. 重力与质量的比值g=9.8N/kg，表示的物 安徽建筑大学 课程设计报告 课程名称：数据结构与算法课程设计 题目：八皇后求解 院系： 专业： 班级： 学号： 姓名： 时间： 目录 一、绪论 (2) 二、需求分析 (2) 三、概要分析 (2) 四、详细设计 (4) 五、调试分析 (5) 六、测试结果 (5) 七、使用说明 (6) 八、参考文献 (7) 一、绪论 八皇后问题是一个古老而著名的问题。这个问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。例如: 面对这个问题，要放在以往可能就要耗费大量的时间在纸上画来画去，这样做的耗费了大量的精力，但是效果却不佳。借助计算机就可以很高效的完成这些工作。那么，采用什么样的数据结构和算法，才能在时间和空间复杂度上完成这个问题呢？ 二、需求分析 1．问题说明： 在8×8的国际象样棋盘上，放置8个皇后，使得这8个棋子不能互相被对方吃掉。 既要满足以下条件： a.不能在同一列 b.不能在同一行 c.不能在同一个对角线上 2．本程序的目的是将八皇后中满足条件的所有的可能性统计出来, 然后将这些结果输出。 3. 测试数据 输入皇后的个数8，程序会输出可能的结果,以及统计结果。 三、概要分析 1．算法思想 如果进行遍历，不仅需要遍历8*8*8*8*8*8*8*8*8 = 2^24次数据，还要 判断各种条件，实际的计算复杂度还要比较这个高。其实这中间很多的 计算其实很多是不需要的，因为如果我们在某一行没有可以插入的数据 算法设计与分析 实验报告 —八皇后问题 - 姓名：崔明鑫 学号：08208012 班级：软件83 【问题描述】 在国际象棋盘上放八个皇后，要求任一皇后吃不到别人，也不受其他皇后的攻击，求出问题的所有解。 【问题分析&算法设计】 用8元组x[1: n]表示8后问题。其中x[ i]表示皇后i放在棋盘的第i行的第x[ i]列。由于不允许将2个皇后放在一列，所以解向量中的x[ i]互不相同。2个皇后不能放在同一斜线上是问题的隐约束。故若2个皇后放置的位置分别是（i，j）和（k，l），且i – j = k – l或i + j = k + l，则说明这2个皇后处于同一斜线上。这两个方程分别等价于i – k = j – l和i – k = l – j。由此可知，只要|i - k| = |j - l|成立，就表明2个皇后位于同一条斜线上。问题的隐约束化成了显约束。用回溯法解决8皇后问题时，用完全8叉树表示解空间。 【算法实现】 #include "stdio.h" #include "math.h" #include "iostream.h" #define N 8 /* 定义棋盘大小*/ static int sum; /* 当前已找到解的个数*/ static int x[N]; /* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列*/ /* 每找到一个解,打印当前棋盘状态*/ void Show() { sum++; cout << "第" << sum << "种情况：" << endl; cout << "坐标为:\t"; for(int k = 0; k < N; k++) 数据结构课程设计报告 任务 要求八皇后问题的解决完整文档
八年级下册物理实验报告单(供参考)
数据结构课程设计(C++)_八皇后动态演示原代码
数据结构课程设计报告-8皇后问题
八年级(下)物理实验报告单
人工智能课程设计报告-n皇后问题解读
数据结构课程设计之-八皇后问题
数据结构课程设计-八皇后问题
八皇后问题讲解
C++课程设计八皇后问题
八年级下册物理实验报告单(供参考)
八皇后课程设计报告
八皇后问题 C语言程序设计
c++八皇后问题 课 程 设 计 报 告
八皇后问题的解决完整文档
八皇后源代码及流程图
2014-2015八年级(下)物理实验报告单
八皇后设计报告
算法设计与分析实验报告—八皇后问题
八皇后问题数据结构课程设计报告
八皇后问题
设计任务书
课题 八皇后 名称 1. 2. 3. 4. 调研并熟悉八皇后的基本功能、数据流程与工作规程； 学习八皇后相关的算法和基于 VC++集成环境的编程技术； 通过实际编程加深对基础知识的理解，提高实践能力； 学习开发资料的收集与整理，学会撰写课程设计报告。
设计 目的
实验 环境
1. 微型电子计算机（PC）； 2. 安装 Windows 2000 以上操作系统，Visual C++6.0 开发工具。
1. 利用课余时间去图书馆或上网查阅课题相关资料，深入理解课题含义及设 计要求，注意材料收集与整理； 2. 在第 16 周末之前完成预设计，并请指导教师审查，通过后方可进行下一 步工作； 3. 本课题要求至少用三种方法解决八皇后问题，输入棋盘的阶层，然后显示 共有多少种布局方案，并显示每一种方案的具体情况。 4. 结束后，及时提交设计报告（含纸质稿、电子稿），要求格式规范、内容 完整、结论正确，正文字数不少于 3000 字（不含代码）。 工作进度计划 起止日期 工 作 内 容
序号
1
2009.06.7~2009.06.7
在预设计的基础上， 进一步查阅资料， 完善设计方案， 形成书面材料。 设计总体方案，构建、绘制流程框图，编写代码，上 机调试。
2
2009.06. 7~2009.06.10 2009.06.11~2009.06.1 2 2009.06.12~2009.06.1 3
3
测试程序，优化代码，增强功能，撰写设计报告。
4
提交软件代码、设计报告，参加答辩，根据教师反馈 意见，修改、完善设计报告。
指导教师（签章）：
年
月
日
摘要： 众所周知的八皇后问题是一个非常古老的问题，具体如下：在 8*8 的国际象棋棋 盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处 于棋盘的同一行、同一列或同一对角线上,这是做出这个课题的基础。要求编写实现八 皇后问题的递归解法或非递归解法，对于任意给定的一个初始位置，输出八皇后问题 的一个布局。本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及 变通能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题 和解决问题的作风和能力。
相关主题
文本预览