数据结构课程设计报告八皇后问题

---优质资料.z.目录TOC\o"1-3"\h\u1631第一章八皇后问题概述 -1-24611.1课题的描述-1-170601.2需求分析-1-243171.2.1涉及到的知识-1-175571.2.2模块的功能要求-1-289501.2.3软硬件的需求-2-276811.2.4面对的问题 -2-286791.3概要设计-2-248821.3.1构造设计理念 -2-172251.3.2算法流程图-3-142511.4详细设计和实现-4-62071.5程序调试-6-215771.5.1问题思考及改良设想-6-5241.5.2运行与测试-7-85921.6课设总结-9-7500第二章n阶魔阵问题概述-10-238582.1课题的描述-10-323562.2需求分析-10-188282.2.1涉及到的知识-10-101192.2.2模块的功能需求-10-113112.2.3软硬件的需求-10-275492.2.4面对的问题-10-24482.3概要设计-11-35062.3.1算法设计理念-11-203032.3.2函数逻辑功能调用图-11-103942.3.3算法流程图-12-270732.4详细设计和实现-12-22792.4.1代码编写及详细设置-12-262592.5程序调试-15-131612.5.1问题思考及改良设想-15-55722.5.2运行与测试 -15-258062.6课设总结-18-25424参考文献-19-31514完毕语-20-14137附录-21-优质资料.z.第一章八皇后问题概述1.1课题的描述八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。八皇后问题是在8*8的国际象棋棋盘上，安放8皇后，要求没有一个皇后能够"吃掉〞任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列、或同一对角线。到了现代，随着计算机技术的飞速开展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好时机，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。1.2需求分析1.2.1涉及到的知识本次课程设计中，用到的主要知识有：递归法的运用，for语句的灵活运用，数据构造中树知识的灵活运用、栈及数组的有关知识的掌握。要求熟练运用C++语言、根本算法的根底知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过对题意的分析与计算，用递归法回溯法及枚举法解决八皇后是比拟适合的。递归是一种比拟简单的且比拟古老的算法。回溯法是递归法的升华，在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才完毕。而枚举法，更是一种根底易懂简洁的方法。把它们综合起来，就构成了今天的算法。不管用什么法做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。1.2.2模块的功能要求当运行程序时，在屏幕上显示每一种方法八个皇后的相对位置，要用比拟直观的界面显示。列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被*个皇后占领后，则同一行所不能再放皇后，要把以I为下标的标记置为被占领状态；对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点〔设下标为(i,j)〕，要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。用数组a[I]：a[I]表示第I个皇后放置的列；I的*围：1-8;对角线数组：b[j](主对角线),c[j]〔从对角线〕，根据程序的运行，去决定主从对角线是否放入皇后。1.2.3软硬件的需求〔1〕系统要求：win98以上操作系统；〔2〕语言平台：tc++或vc++6.0；1.2.4面对的问题(1)列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被*个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点〔设下标为(i,j)〕，要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。〔2〕使用数据构造的知识，用递归法解决问：。数组a[I]：a[I]表示第I个皇后放置的列；I的*围：1..8;对角线数组：b[j](主对角线),c[j]〔从对角线〕，根据程序的运行，去决定主从对角线是否放入皇后；1.3概要设计1.3.1构造设计理念〔1〕从n列开场摆放第n个皇后〔因为这样便可以符合每一竖列一个皇后的要求〕，先测试当前位置〔n，m〕是否等于0〔未被占领〕。如果是，摆放第n个皇后，并宣布占领，接着进展递归；如果不是，测试下一个位置〔n，m+1〕，但是如果当n<=8，m=8时，发现此时已无法摆放时，便要进展回溯。从问题的*一种可能出发，搜索从这种情况能出发，继续搜索，这种不断"回溯〞的寻找解的方法，称为"回溯法〞。〔2〕使用数组实现回溯法的思想。〔3〕当n>8时，便打印出结果。1.3.2算法流程图图1-1算法流程图序图1-11.4详细设计和实现#include<conio.h>#include<math.h>#include<stdlib.h>#include<stdio.h>#include<iostream.h>#defineQUEENS8intiCount=0;//!记录解的序号的全局变量。intSite[QUEENS];//!记录皇后在各行上的放置位置的全局数组。voidQueen(intn);//!递归求解的函数。voidOutput();//!输出一个解。intIsValid(intn);//!判断第n个皇后放上去之后，是否有〉冲突。voidmain()/*Main：主函数。*/{system("title管理102孙海龙八皇后问题");cout<<""<<"八皇后问题："<<endl;cout<<""<<""<<endl;Queen(0);//!从第0行开场递归试探。getch();//!按任意键返回。}voidQueen(intn)/*Queen：递归放置第n个皇后，程序的核心!*/{inti;if(n==QUEENS)//!参数n从0开场，等于8时便试出了一个解，将它输出并回溯。{Output();return;}for(i=1;i<=QUEENS;i++)//!n还没到8，在第n行的各个行上依次试探。{Site[n]=i;//!在该行的第i行上放置皇后。if(IsValid(n))//!如果放置没有冲突，就开场下一行的试探。 Queen(n+1);}}intIsValid(intn)/*IsValid：判断第n个皇后放上去之后，是否合法，即是否无冲突。*/{inti;for(i=0;i<n;i++)//!将第n个皇后的位置依次于前面n－1个皇后的位置比拟。{if(Site[i]==Site[n])//!两个皇后在同一列上，返回0。return0;if(abs(Site[i]-Site[n])==(n-i))//!两个皇后在同一对角线上，返回0。return0;}return1;//!没有冲突，返回1。}voidOutput()/*Output：输出一个解，即一种没有冲突的放置方案。*/{ inti;printf("No.%-5d",++iCount);//!输出序号。for(i=0;i<QUEENS;i++)//!依次输出各个行上的皇后的位置，即所在的列数。 printf("%d",Site[i]);cout<<〞〞<<endl;}1.5程序调试1.5.1问题思考及改良设想在完整程序调试时由于太急于求成导致程序进展循环时出现无法运行的问题，逻辑错误导致程序死循环或不循环或循环一小局部，后经细心改正后才把调试工作做完。做程序真的不是三两下就能完美的做好的，正应了那句话"心急吃不了热豆腐啊〞。但对于这个程序我由于c++语言学的不到位以至于有些掺杂了c语言的有关算法，要是都用c++来编写就再好不过了。在编写代码时，我希望能随机选择一数*(1～92)后，能输出该种情况所对应的八个皇后的摆放方式和每个皇后所在的位置，但想了好久，就是无法实现。而且，当92种情况都输出时，前面的几十种情况无法看到，要想让摆放皇后的图形和所在具体的位置一起输出，就得修改程序让使她们一个一个地输出，这样显然比拟麻烦。倘假设有一种既能把八皇后的所在位置和把皇后所有情况连续输出，我感觉就应该算是一个完美的程序了，这还需要我一致的探索开掘下去才行。1.5.2运行与测试〔1〕由于在编写代码时漏写了*个函数导致程序不能正常运行出现了错误提示；图1-1错误警告〔2〕在同学帮助下成功的运行了该程序；图1-2成功运行〔3〕最后输出了最终八皇后问题的结果。图1-3输出八皇后结果1.6课设总结通过这次的课程设计，让我了解了八皇后这一经典的问题。同时让我更好地掌握了栈思想以及一维数组等等知识,以及一些书本上没有的东西，这对我以后的学习生涯以及将来步入社会起到很大的帮助。这次课程设计虽然花了我很多时间和精力，但很值得,因为它对我能力提高起到很大帮助。这次课程设计也提醒我以前知识的匮乏,它给我敲响了警钟,让我意识到自己根底的不扎实.当然这次实验还是有很多问题的。比方程序设计的界面不够好，一些程序并非自己所写,而是修改*些程序而成,但这些不该,在下次课程设计时不会再发生.针对八皇后这个课题，也许表层只局限于对八个皇后的摆放，但还可以对更多的情况进展探讨分析，比方九皇后，十皇后等等。在报告正文中已经屡次提到关于N皇后的设计方法，但只是一带而过，有些问题很难通过一个报告设计就轻而易举的得到解决，还需要花费更多的时间。---优质资料.z.第二章n阶魔阵问题概述2.1课题的描述n阶魔阵问题在我国古代被称作"纵横图〞，其主要设计要求是对于给定的一个奇数n，构造一个n阶魔阵。n阶魔阵是一个n阶方阵，其元素由自然数1，2，3，…，n^2组成。魔阵每一行元素之和，每一列元素之和，以及主，副对角线员素质和均相等。2.2需求分析2.2.1涉及到的知识本次课程设计中，用到的主要知识有：二维数组的使用方法和一些根本的设计思路以及数据构造与数据存储的的有关知识。2.2.2模块的功能需求(1)voidmain〔〕函数，主函数，调用以下子函数，实现魔方阵填充与输出，实现问题要求功能；(2〕voidjishu〔intn〕函数，n为奇数实现n阶魔方阵；(3〕voidout〔intn，inta[MA*][MA*]〕函数，此函数用以调整方阵元素位置，实现魔方阵n*n形式输出〔4〕voidcheck〔intn，inta[MA*][MA*]〕函数，计算并输出n阶魔方阵每行、每列以及每条对角线上各个数字的累加和，同时验证魔方阵的准确性。2.2.3软硬件的需求〔1〕系统要求：win98以上操作系统；〔2〕语言平台：tc++或vc++6.0；2.2.4面对的问题〔1〕每列每行以及主副对角线元素之和相等；〔2〕要求输出结果的格式要具有n阶方阵的形式。2.3概要设计2.3.1算法设计理念首先，输入一个数字n〔1≤n≤99),则输出对应的n阶魔方阵，并输出每一行、每一列、每条对角线上各个数字累加和。假设输入数字n超出要求*围，则提醒用户重新输入n。但假设输入数字0时，操作完毕，退出程序。使用多维数组输出魔方阵，分别用3个子函数实现相应的功能。输入形式：数字n〔1≤n≤99)。输出形式：〔1〕以矩阵形式输出n〔1≤n≤99)阶魔方阵；〔2〕输出每一行、每一列、每条对角线上各个数字累加和；2.3.2函数逻辑功能调用图图2-1逻辑功能2.3.3算法流程图图2-2算法流程图2.4详细设计和实现2.4.1代码编写及详细设置voidjishu〔intn〕函数，n为奇数实现n阶魔方阵，实现思想如下；a.在1到n2的数字中，选择1开场填充魔方，将数字1填入第一行的中间方格中，即〔0，n/2〕的位置。b.向已填充的前一个数字位置〔p，q〕的左上角〔p-1，q-1〕填入下一个数字，如果出现以下情况，则修改填充位置：i〕假设填充位置超出上边界，则修改为下边界的相应位置，即把p-1修改为n-1；ii〕假设填充位置超出左边界，则修改为最右边的相应位置，即把q-1改为n-1；iii〕假设填充位置已有数字，则填充位置修改为下一行的同一位置。c.重复以上步骤，直至将n2个数字全部填入魔方中。最后调用函数函数out〔n，a〕和check〔n，a〕，实现魔方阵的输出，检验魔方阵的准确性。具体实现代码如下：voidjishu(intn)/*奇数*/{intp,q,i,a[MA*][MA*];p=0;q=(n-1)/2;a[0][q]=1;/*第一个数字的填入位置*/for(i=2;i<=n*n;i++){p=(p-1+n)%n;/*计算填入的位置*/q=(q-1+n)%n;if(a[p][q]>0)/*如果填入位置已有数字，则重新计算填入位置*/ {p=(p+2)%n;/*由于前面p减了1，因此p应该加1，才能表示下一行*/q=(q+1)%n;/*由于前面q减了1，因此q应该加1，才能表示同一列*/ }a[p][q]=i;/*填入数字*/}out(n,a);/*调用输出函数*/check(n,a);/*调用验证函数*/}(3〕voidout〔intn，inta[MA*][MA*]〕函数，此函数用以调整方阵元素位置，实现魔方阵n*n形式输出。具体实现代码如下：voidout(intn,inta[MA*][MA*])/*魔方矩阵输出函数*/{intp,q;for(p=0;p<=n-1;p++){for(q=0;q<=n-1;q++){cout<<setw(4)<<a[p][q]<<"";/*输出魔方矩阵的结果*/}cout<<endl<<endl;}}〔4〕voidcheck〔intn，inta[MA*][MA*]〕函数，计算并输出n阶魔方阵每行、每列以及每条对角线上各个数字的累加和，同时验证魔方阵的准确性。具体实现代码如下：voidcheck(intn,inta[MA*][MA*])/*魔方矩阵验证函数*/{intp,q,sum1=0,sum2=(n*n+1)*n/2,k;cout<<"此魔方阵的每行、每列、两条对角线的和为："<<sum2<<endl;/*输出标准魔方阵的每行、每列、两条对角线的和*/for(p=0;p<n;p++){for(q=0;q<n;q++){sum1=a[p][q]+sum1;/*计算矩阵横行纵行的和*/}if(sum1!=sum2)/*判断矩阵横行纵行的和是否与标准一样*/{cout<<"横行纵行计算结果与标准不符，请修改程序错误"<<endl;break;}sum1=0;}for(k=0;k<n;k++){sum1=a[k][k]+sum1;/*计算矩阵主对角线的和*/}if(sum1!=sum2)/*判断矩阵主对角线的和是否与标准一样*/cout<<"主对角线计算结果与标准不符，请修改程序错误"<<endl;sum1=0;for(k=0;k<n;k++){sum1=a[k][n-k-1]+sum1;/*计算矩阵次对角线的和*/}if(sum1!=sum2)/*判断矩阵次对角线的和是否与标准一样*/cout<<"次对角线计算结果与标准不符，请修改程序错误"<<endl;}2.5程序调试2.5.1问题思考及改良设想就编写的程序而言，虽然能到达预期的结果，但总体构造还不够简洁，不太容易去理解。许多问题还需要继续研究，许多技术还需要更多的改良。去图书馆借了不少书，也去网上看了些资料，只是对大概的知识有了点了解，但还是很难着手于写代码，后来就按照教师说的，先搞清楚原理，再考虑如何去实现！后来又去上网查看相关资料，又到图书馆借了很多书看，总算有头绪了。但在调试过程中，还是遇到了很多困难，后来通过了很多同学的帮助才把问题解决了。2.5.2运行与测试〔1〕运行顺利没有发现错误。图2-3准确运行〔2〕输入1-99阶魔阵。图2-4输入数据〔3〕当输入超出*围时，提示输入有误。图2-5输入有误〔4〕当输入的魔阵阶数为7时得到以下方阵。图2-6正常输入〔5〕当输入0时该程序完毕运行。图2-7完毕运行2.6课设总结在编程实现的过程中，我进一步掌握和熟悉了二为数组的应用，并熟悉了将问题分解在组装的解决方法和函数的调用。编程过程中，使用另外完成输出功能的子函数voidout(intn,inta)，通过对其调用，大大节省了程序编写的复杂度，提高了效率。在实现奇数阶魔方阵时，遇到了一点问题，请教了同学，一起进展了讨论研究，最终解决了问题。通过这次课程设计，使我们学到了一些以前没有学过的知识，使我们对程序设计有了更深层次的认识和理解，懂得了灵活运用。---优质资料.z.参考文献[1]*光然；数据构造实践训练教程；2009,4[2]李春葆，尹为民，李蓉蓉；数据构造教程上机实验指导；2009，1[3]胡元义，