北邮C 八皇后数据结构实验报告

数据结构与算法专题实验实验报告_八皇后_背包问题的求解_农夫过河实验报告：数据结构与算法专题实验报告实验题目：八皇后问题的求解与背包问题的求解实验目的：1. 掌握八皇后问题的求解方法，了解回溯算法的应用。

2. 掌握背包问题的求解方法，了解动态规划算法的应用。

3. 进一步理解数据结构与算法的基本概念和应用。

实验内容：1. 八皇后问题的求解八皇后问题是一个经典的递归与回溯算法问题，要求在一个8×8的棋盘上放置8个皇后，使得任意两个皇后不在同一行、同一列或同一斜线上。

具体求解步骤如下：a. 定义一个8×8的二维数组作为棋盘，初始化所有元素为0。

b. 从第一行开始，依次尝试在每一列放置皇后。

c. 对于每一列，判断当前位置是否与已经放置的皇后冲突。

如果冲突，则回溯到上一行，重新选择位置；否则，继续放置下一行的皇后。

d. 当放置完所有皇后时，输出结果。

2. 背包问题的求解背包问题是一个经典的动态规划算法问题，要求在给定的一组物品中选择一些物品放入背包，使得背包的总重量最大，但不能超过背包的承重量。

具体求解步骤如下：a. 定义一个二维数组dp，其中dp[i][j]表示在前i个物品中选择，背包容量为j时的最大重量。

b. 初始化dp数组的第一行和第一列为0，表示背包容量为0时和没有物品可选时的最大重量都为0。

c. 对于每个物品，分两种情况讨论：- 如果当前物品的重量大于背包的容量，则无法选择该物品，直接继承前i-1个物品的最大重量，即dp[i][j] = dp[i-1][j]；- 如果当前物品的重量小于等于背包的容量，则可以选择该物品或不选择该物品。

选择该物品时，背包的总重量为dp[i-1][j-w[i]] + v[i]，不选择该物品时，背包的总重量为dp[i-1][j]。

取两者中的较大值作为dp[i][j]的值。

d. 最终，dp[n][m]即为所求的最大重量，其中n为物品的个数，m为背包的承重量。

八皇后实验报告八皇后实验报告引言：八皇后问题是一个经典的数学问题，它要求在一个8x8的国际象棋棋盘上放置8个皇后，使得任意两个皇后都不会互相攻击。

这个问题看似简单，但实际上却充满了挑战。

在本次实验中，我们将探索八皇后问题的解法，并通过编写算法来解决这个问题。

一、问题背景：八皇后问题最早由数学家马克斯·贝瑟尔于1848年提出，它是一道经典的递归问题。

在国际象棋中，皇后可以在同一行、同一列或同一对角线上进行攻击，因此我们需要找到一种方法，使得8个皇后彼此之间不会相互攻击。

二、解决方法：为了解决八皇后问题，我们可以使用回溯法。

回溯法是一种穷举搜索的方法，它通过逐步尝试所有可能的解决方案，直到找到符合要求的解。

具体步骤如下：1. 初始化一个8x8的棋盘，并将所有格子标记为无皇后。

2. 从第一行开始，依次尝试在每一列放置一个皇后。

3. 在每一列中，检查当前位置是否符合要求，即与已放置的皇后不在同一行、同一列或同一对角线上。

4. 如果当前位置符合要求，将皇后放置在该位置，并进入下一行。

5. 如果当前位置不符合要求，尝试在下一列放置皇后。

6. 重复步骤3-5，直到找到一个解或者所有可能的位置都已尝试过。

7. 如果找到一个解，将其输出；否则，回溯到上一行，继续尝试下一列的位置。

三、编写算法：基于上述步骤，我们可以编写一个递归函数来解决八皇后问题。

伪代码如下所示：```function solveQueens(board, row):if row == 8:print(board) # 打印解returnfor col in range(8):if isSafe(board, row, col):board[row][col] = 1solveQueens(board, row + 1)board[row][col] = 0function isSafe(board, row, col):for i in range(row):if board[i][col] == 1:return Falseif col - (row - i) >= 0 and board[i][col - (row - i)] == 1:return Falseif col + (row - i) < 8 and board[i][col + (row - i)] == 1:return Falsereturn Trueboard = [[0]*8 for _ in range(8)]solveQueens(board, 0)```四、实验结果：通过运行上述算法，我们得到了八皇后问题的所有解。

北邮数据结构实验报告摘要：本报告基于北邮数据结构实验，通过实际操作和实验结果的分析，总结和讨论了各实验的目的、实验过程、实验结果以及相关的问题和解决方法。

本报告旨在帮助读者了解数据结构实验的基本原理和应用，并为今后的学习和研究提供参考。

1. 实验一：线性表的操作1.1 实验目的本实验旨在掌握线性表的基本操作以及对应的算法实现，包括插入、删除、查找、修改等。

1.2 实验过程我们使用C++语言编写了线性表的相关算法，并在实际编程环境下进行了测试。

通过插入元素、删除元素、查找元素和修改元素的操作，验证了算法的正确性和效率。

1.3 实验结果经过测试，我们发现线性表的插入和删除操作的时间复杂度为O(n)，查找操作的时间复杂度为O(n)，修改操作的时间复杂度为O(1)。

这些结果与预期相符，并反映了线性表的基本特性。

1.4 问题与解决方法在实验过程中，我们遇到了一些问题，例如插入操作的边界条件判断、删除操作时的内存释放等。

通过仔细分析问题，我们优化了算法的实现，并解决了这些问题。

2. 实验二：栈和队列的应用2.1 实验目的本实验旨在掌握栈和队列的基本原理、操作和应用，并进行实际编程实现。

2.2 实验过程我们使用C++语言编写了栈和队列的相关算法，并在实际编程环境下进行了测试。

通过栈的应用实现表达式求值和逆波兰表达式的计算，以及队列的应用实现图的广度优先遍历，验证了算法的正确性和效率。

2.3 实验结果经过测试，我们发现栈的应用可以实现表达式的求值和逆波兰表达式的计算，队列的应用可以实现图的广度优先遍历。

这些结果证明了栈和队列在实际应用中的重要性和有效性。

2.4 问题与解决方法在实验过程中，我们遇到了一些问题，例如中缀表达式转后缀表达式的算法设计、表达式求值的优化等。

通过查阅资料和与同学的讨论，我们解决了这些问题，并完善了算法的实现。

3. 实验三：串的模式匹配3.1 实验目的本实验旨在掌握串的基本操作和模式匹配算法，并进行实际编程实现。

c八皇后问题课程设计报告范文八皇后问题一、设计任务与目标在8行8列的棋盘上放置8个皇后，皇后可吃掉与她处于同行或同列或同一对角线上的其他棋子，要使任一个皇后都不能吃掉其他的7个皇后，则需要同时控制同行，同列，同一条对角线的情况，然后当行，列，以及对角线都无皇后时，记录该点。

并用“Q”表示皇后的位置，“+”表示其它位置。

二、方案设计与论证定义4个具有全局作用域的数组intLineNum[9];boola[9],b[15]分别表示第几列的皇后要放的行位置，第几行上是否未放皇后，“/”斜对角线上是否未放皇后，“\\”反斜对角线上是否未放皇后。

通过语句“if(a[j]&&b[i+j-2]&&c[i-j+7])LineNum[i]=j;”判断并实现一枚皇后是否放置安全。

然而当第一枚皇后位置放置后，则它所在的行，列，以及对角线的记录状态需要改变后，才能进行下一枚皇后的放置。

下一枚皇后判断位置的步骤与第一枚一样，所以可以用递归的方法进行下一枚皇后位置的放置。

当第8枚皇后的位置确定后，就跳出递归。

之后还要对之前每一个位置记录的情况初始化才能进行下一种放置八皇后的情况。

三、程序框图或流程图，程序清单与调用关系Inti=1i>8否是Intj=1;否j<9是j++输出并显示八皇后摆放情况a[j]&&b[i+j-2]&&c[i-j+7]是否跳出递归j++LineNum[i]=j;a[j]=fale;b[i+j-2]=fale;c[i-j+7]=fale;i++;i--a[j]=true;b[i+j-2]=true;c[i-j+7]=true;否i<2是四、全部源程序清单#include#includeintLineNum[9];//第i列的皇后要放的行位置（只用其中的列号1到8）boola[9];//a[i]为1表示第i行上尚未放皇后boolb[15];//b[i]为1表示第i条斜对角线上尚未放皇后（斜对角线指的是\状对角线，该对角线上各点的行列号之和i+j为一个常数）boolc[15];//c[i]为1表示第i条反斜对角线上尚未放皇后（反斜对角线指的是\状对角线，该对角线上各点的行列号之差i-j为一个常数）。

2007级数据结构实验报告实验名称：实验二——栈和队列学生姓名：班级：班内序号：学号：日期：2008年11月18日1．实验要求通过选择下面五个题目之一进行实现，掌握如下内容：➢进一步掌握指针、模板类、异常处理的使用➢掌握栈的操作的实现方法➢掌握队列的操作的实现方法➢学习使用栈解决实际问题的能力➢学习使用队列解决实际问题的能力利用栈结构实现八皇后问题。

八皇后问题19世纪著名的数学家高斯于1850年提出的。

他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。

请设计算法打印所有可能的摆放方法。

提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析2.1 存储结构采用栈存储，其结构图如下:2.2 关键算法分析函数原型： bool check(int i);2.2.1.1.1自然语言：检测至第i行所摆放的第i个皇后是否和之前的i-1个皇后发生冲突。

如是，则返回0；反之，则当前布局合法，返回1。

判断两个皇后是否相互攻击的准则是：若两个皇后处于同一行，或处于同一列，或处于同一斜线，就能相互攻击。

基于如上准则，函数check( )的工作原理是：考虑到数组的每个元素分别代表不同行的皇后，即每行只放置了一个皇后，所以不必考虑“同处一行相互攻击”的情形；对于同处一列，则语句：if(queen[s]==queen[t])就能判断出不同行的两个棋子是否同处一列；对于处于同一斜线的这种情况，首先，我们看出国际象棋的棋盘是一个八行八列的正方形。

因此我们可将棋盘想象为数学上的笛卡尔平面坐标系，两颗棋子想象为平面上的两个点，就很容易发现，为保证两颗棋子不处于同一斜线，只要过这两个点的直线斜率不为1或-1，就能达到要求。

由此可使用下列语句：if( abs(t-s) == abs(queen[s]-queen[t]) )其中t和s分别代表不同行的两个皇后，即数组queen[8]里不同下标的两个元素。

数据结构实验报告1．实验要求实验目的：利用栈结构实现八皇后问题八皇后问题如下：八皇后问题是19世纪著名的数学家高斯于1850年提出的。

他的问题是，在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行，同一列，同一斜线上。

实验内容：利用所学的栈结构用递归或非递归解决八皇后问题。

2. 程序分析程序使用程序最主要只是在主函数用了一个递归函数Queen。

Queen函数使用了三个参数m,flag[][],chess[][]。

其中m是行数，flag[][]是判断二维数组何处可以放置皇后，chess[][]是存储字符串的二维数组。

主函数中对Queen函数中的形参数组flag[][],chess[][]进行初始化，在Queen函数中再进行各种操作。

Queen函数执行代码，首先行数m为0，当m小于7时，通过if…else…语句，利用Queen(m+1,f,c)重新执行递归函数到下一行。

2.1 存储结构存储结构：数组存储。

flag[][]数组存储数字判断输出和储能放置皇后,chess[][]数组存储字符串即皇后和非皇后的形状。

2.2 关键算法分析1、关键算法：a．for(i=0;i<8;i++)for(j=0;j<8;j++){f[i][j]=0;c[i][j]='*';说明：对棋盘进行初始化未放置皇后的为“*”b．for(i=0;i<8;i++)for(j=0;j<8;j++){c[i][j]=chess[i][j];f[i][j]=flag[i][j];}说明：对c[][]，f[][]进行初始化。

c．for(i=0;i<8;i++)for(j=0;j<8;j++){i f(f[i][j]==0 && (i+j==m+k || m==i || k==j || m-k==i-j))f[i][j]=-1;}c[m][k]='#';说明：已放置皇后的行、列以及对角线都不能再放置皇后。

软件工程上机报告实验名称：八皇后问题图形界面求解姓名：郭恂学号：2011011435班级：11级数学班中国石油大学（北京）计算机科学与技术系一、试验程序截图：点击显示下一组解即可显示下一组解：同样的，如果点击上一组解即可显示上一组解。

若在第1组解时点击显示上一组解会弹出报错提示框。

同样，若在第92组解点击显示下一组解也会弹出报错提示框：二、程序代码程序使用Java语言编写，编写环境为jdk1.6.0_18。

使用编程开发环境eclipse.exe编写。

本程序创建了两个类，两个类在同一个工程中。

其中Queen类的作用仅仅用来保存八皇后问题计算结果的数据，便于画图时使用。

本程序大概由两部分组成，第一部分是解八皇后问题，第二部分是画图。

程序源代码为：类1：public class Queen{public int[] x=new int[8];public int[] y=new int[8];public String name;}类2：import javax.swing.*;import java.awt.event.*;import java.awt.*;import javax.swing.JOptionPane;public class bahuanghou extends JFrame implements ActionListener {//JLabel[] l;int number=0; //当前显示的解的编号int sum=0; //所有解得数量JLabel l2;JButton b1,b2; //b1为显示下一组解得按钮，b2为显示上一组解得按钮。

Queen[] q=new Queen[128]; //得到的解储存在Queen类的数组里面。

private Image bomb1=Toolkit.getDefaultToolkit().getImage("D:\\qizi1.JPG"); //黑格棋子为bomb1private Image bomb2=Toolkit.getDefaultToolkit().getImage("D:\\qizi2.JPG"); //白格棋子为bomb2public bahuanghou() //构造方法，初始化窗口。

八皇后问题实验报告源程序八皇后问题实验报告需求分析八皇后问题是一个古老而著名的问题。

该问题是十九世纪著名的数学家高斯1850年提出的。

八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子，问有多少种不同的摆法？并找出所有的摆法。

因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。

而本课程设计本人的目的也是通过C语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．最终将其问题变得一目了然，更加易懂。

概要分析本课件学生是用递归来实现的，分别一一测试了每一种摆法，并把它拥有的92种变化表现出来。

在这个程序中，学生的主要思路以及思想是这样的：1.解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态；对角线：对角线有两个方向。

在这学生把这两条对角线称为：主对角线和从对角线。

在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。

因此，当第i个皇后占领了第j列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。

(1) 满足上述条件的八个皇后，必然是每行一个，每列一个。

(2) 棋盘上任意一行、任意一列、任意一条斜线上都不能有两个皇后。

如果我们把8×8 的棋盘看成是一个平面直角坐标系，则八皇后问题就可以用数学语言来描述了，任意两个皇后在平面上的坐标应该同时满足以下三个条件：①两个皇后不在同一行：两个皇后的横坐标不相等；②两个皇后不在同一列：两个皇后的纵坐标不相等；③两个皇后不在同一条斜线上：两个皇后的横坐标之差的绝对值不等于两个皇后的纵坐标之差的绝对值。

数据结构课程设计姓名:学号:指导老师：目录一.选题概述——--———--——--—-—————---——-—-—-——---—-——3二.设计要求与分析-———---—-----——--——--—————-—-———3三.数据结构与定义-———--————---——-—-——-—-—————-—--41。

结构体定义2。

函数定义3。

函数之间的定义四.程序段与分析---———-———--—-—-———————--—--—---——5五.完整程序代码及运行结果截图---—-———-———-—————7六.心得体会-———-—-——---———-——-————-———————---——--10七.参考文献——————-——--——————-——--—---—-———-—--—--10一．选题概述：在实际应用中,有相当一类问题需要找出它的解集合,或者要求找出某些约束条件下的最优解.求解时经常使用一种称为回溯的方法来解决.所谓回溯就是走回头路，该方法是在一定的约束条件下试探地搜索前进，若前进中受阻，则回头另择通路继续搜索。

为了能够沿着原路逆序回退，需用栈来保存曾经到达的每一个状态,栈顶的状态即为回退的第一站，因此回溯法均可利用栈来实现。

而解决八皇后问题就是利用回溯法和栈来实现的。

二．设计要求与分析八皇后问题是在8x8的国际象棋棋盘上，安放8个皇后,要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线。

八皇后在棋盘上分布的各种可能的格局，其数目非常大，约等于232种，但是，可以将一些明显不满足问题要求的格局排除掉。

由于任意两个皇后不能同行，即每一行只能放置一个皇后，因此将第i个皇后放置在第i行上。

这样在放置第i个皇后时,只要考虑它与前i 一1个皇后处于不同列和不同对角线位置上即可.因此，其算法基本思想如下：从第1行起逐行放置皇后，每放置一个皇后均需要依次对第1，2，…，8列进行试探，并尽可能取小的列数。

北邮数据结构实验报告北邮数据结构实验报告一、引言数据结构是计算机科学中的重要基础知识，对于计算机程序的设计和性能优化起着至关重要的作用。

本报告旨在总结北邮数据结构实验的相关内容，包括实验目的、实验设计、实验过程和实验结果等。

二、实验目的本次实验旨在通过实践操作，加深对数据结构的理解和应用能力。

具体目的如下：1. 掌握线性表、栈和队列等基本数据结构的实现方法；2. 熟悉二叉树、图等非线性数据结构的构建和遍历算法；3. 学会使用递归和非递归算法解决实际问题；4. 培养编程实践能力和团队合作意识。

三、实验设计本次实验包括以下几个部分：1. 线性表实验：设计一个线性表类，实现线性表的基本操作，如插入、删除和查找等。

通过实验，了解线性表的顺序存储和链式存储结构的特点和应用场景。

2. 栈和队列实验：设计栈和队列类，实现栈和队列的基本操作，如入栈、出栈、入队和出队等。

通过实验，掌握栈和队列的应用，如括号匹配、迷宫求解等。

3. 二叉树实验：设计二叉树类，实现二叉树的创建、遍历和查找等操作。

通过实验，熟悉二叉树的前序、中序和后序遍历算法，并了解二叉树的应用，如表达式求值等。

4. 图实验：设计图类，实现图的创建、遍历和最短路径等操作。

通过实验，掌握图的邻接矩阵和邻接表表示方法，并了解图的深度优先搜索和广度优先搜索算法。

四、实验过程1. 线性表实验：根据实验要求，首先选择线性表的存储结构，然后设计线性表类，实现插入、删除和查找等基本操作。

在实验过程中，遇到了一些问题，如边界条件的处理和内存管理等，通过团队合作，最终解决了这些问题。

2. 栈和队列实验：根据实验要求，设计栈和队列类，实现入栈、出栈、入队和出队等基本操作。

在实验过程中，我们发现了栈和队列在实际应用中的重要性，如括号匹配和迷宫求解等，通过实验加深了对栈和队列的理解。

3. 二叉树实验：根据实验要求，设计二叉树类，实现二叉树的创建、遍历和查找等操作。

在实验过程中，我们发现了二叉树在表达式求值和排序等方面的应用，通过实验加深了对二叉树的理解。

八皇后问题一．八皇后问题简述:在8*8的国际象棋棋盘上放置8个皇后，使任意两个皇后不能互相攻击，即任何行任何列或对角线（与水平轴的夹角为45°或135°的斜线）上不得有两个或两个以上的皇后，这样的一个格局称为问题的一个解。

请求八皇后问题的算法。

二．解决思路：先声明我们根据条件可以知道皇后肯定是每行都有且只有一个所以我们创建一个数组x[t]让数组角标表示八皇后的行，用这个角标对应的数组值来确定这个皇后在这行的那一列。

我们用递归来做：这问题要求皇后所在的位置必须和其他皇后的位置不在同一行、列还有把两个皇后看成点其|斜率|=1；所以我们就要写这个限定条件用一个函数来实现：函数内对每一个已经放好的皇后的位置进行判断，所以就要有个循环。

我们既然是用递归来解决问题那就要把这个问题分成一个个相同的小问题来实现。

不难发现我们要在8*8的方格里放好8个皇后那我们就要知道在8（列）*7（行）是怎么放的在有我们事先写好的判断函数放好最后行就搞定了；以此类推我们要知道8*7的怎么方的我们就要知道8*6是怎么样的就好了，所以我们是以一行怎么放作为一个单元。

我们就去建一个可以放好一行的函数backtrack（int t）里面的t表示是第几行，在main函数调用的时候第一次传进来的是0也就是从第一行开始判断。

我们就开始写函数体了：每一行有8个位置可以放，每一个位置我们都要去判断一下所以我们就用循环来搞定。

在这个循环里面我们让x[t]=i也就是从这一行的第一个开始判断。

放好后就要去判断是否符合条件。

如果符合条件我们就在调用这个函数本身backtrack 不过传进去的参数是t+1也就是下一行的意思。

在进行判断下一行之前我们要判断一下t是不是等于8也就是已经是最后一行了，如果是最后一行了我们就可以将其进行输出。

打印8*8的矩阵（提示在写一个函数）皇后的位置用1表示出来没有的用0表示。

三．代码与注解：#include <math.h>#include <stdio.h>#include <time.h>#include<string.h>#include<conio.h> //用getch()要调用的头文件#include <stdlib.h> //要用system函数要调用的头文件int SUM=0; //统计有多少种可能int shezhi(){ //设置为N皇后问题int N;printf("这是一个N皇后问题...\n请输入N=");scanf("%d",&N);return N;}void Print(int N,int x[]) //印出結果{int MAX=N;for(int i=0;i<MAX;i++){for(int j=0;j<MAX;j++)if(j==x[i])printf("@");elseprintf("*");printf("\n");}SUM++; //打印一种情况统计一次printf("\n");}int Judge(int k,int x[]) //判断是否在同一直、橫、斜线上有其它棋子{int i;for(i=0;i<k;i++)if( abs(k-i)==abs(x[i]-x[k]) || x[i]==x[k] ) //函数名: abs; 功能: 求整数的绝对值 ;return 0;return 1;}void backtrack(int t,int N,int x[]) // 把棋子放到棋盘上{ int MAX=N;int i;for(i=0;i<MAX;i++){x[t]=i;if(Judge(t,x)){if(t==MAX-1){Print(MAX,x); // 找到其中一种放法，印出結果}else backtrack(t+1,N,x);}}}void Introduce(){printf("1.设置为N皇后问题。

数据结构课程设计报告八皇后问题设计任务书指导教师（签章）：年月日摘要：众所周知的八皇后问题是一个非常古老的问题，具体如下：在8*8的国际象棋棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上,这是做出这个课题的基础。

要求编写实现八皇后问题的递归解法或非递归解法，对于任意给定的一个初始位置，输出八皇后问题的一个布局。

本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力。

在实践中培养独立分析问题和解决问题的作风和能力。

要求熟练运用C++语言、基本算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。

通过对题意的分析与计算，用递归法回溯法及枚举法解决八皇后是比较适合的。

递归是一种比较简单的且比较古老的算法。

回溯法是递归法的升华，在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。

而枚举法，更是一种基础易懂简洁的方法。

把它们综合起来，就构成了今天的算法。

不论用什么法做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。

关键词：八皇后；递归法；回溯法；数组；枚举法…….目录1 课题综述…………………………………………………………………………………1.1 八皇后问题概述------------------------------------------------------------1.2 预期目标-------------------------------------------------------------------1.3 八皇后问题课题要求 -------------------------------------------------------1.4 面对的问题 ----------------------------------------------------------------2 需求分析…………………………………………………………………………………2.1 涉及到的知识基础-----------------------------------------------------------2.2 总体方案--------------------------------------------------------------------3 模块及算法设计……………………………………………………………………………………3.1 算法描述--------------------------------------------------------------------3.2．详细流程图 ----------------------------------------------------------------4.代码编写…………………………………………………………………………5 程序调试分析……………………………………………………………………………………6 运行与测试……………………………………………………………………………………总结…………………………………………………………………………1 课题综述1.1 八皇后问题概述八皇后问题是一个古老而著名的问题。

八皇后实验报告八皇后实验报告导言：八皇后问题是一个经典的数学问题，最早由西班牙的数学家马克斯·贝恩在1848年提出。

问题的目标是在一个8×8的棋盘上，放置8个皇后，使得它们互相之间无法攻击到对方。

本次实验旨在通过编程的方式求解八皇后问题，并分析解的个数和解的特点。

一、问题描述八皇后问题可以简化为在一个8×8的棋盘上放置8个皇后，使得任意两个皇后都不在同一行、同一列或同一斜线上。

这意味着每一行和每一列最多只能有一个皇后。

二、算法设计为了求解八皇后问题，我们采用了回溯算法。

回溯算法是一种通过逐步试错的方式来寻找问题解的方法。

具体的算法步骤如下：1. 从棋盘的第一行开始，依次尝试在每一列放置一个皇后。

2. 在放置一个皇后后，检查是否满足任意两个皇后都不在同一行、同一列或同一斜线上的条件。

3. 如果满足条件，则继续到下一行放置皇后；如果不满足条件，则回溯到上一行重新选择位置。

4. 当最后一行的皇后放置完毕后，即找到了一个解，记录下来。

5. 继续回溯，寻找下一个解，直到所有解都找到为止。

三、实验结果通过编程实现了八皇后问题的求解算法，并运行了多组实验。

实验结果如下：1. 解的个数在8×8的棋盘上，共有92个不同的解。

每个解都代表了一种放置皇后的方式，使得它们互不攻击到对方。

2. 解的特点(1) 对称性：在所有的解中，有一半解是对称的。

即如果一个解是对称的，那么它的镜像解也是一个合法解。

(2) 旋转性：每个解可以通过旋转得到其他的合法解。

例如，一个解可以通过将整个棋盘顺时针旋转90度得到另一个解。

(3) 反射性：每个解可以通过水平或垂直翻转得到其他的合法解。

例如，一个解可以通过将整个棋盘水平翻转得到另一个解。

(4) 解的数量：解的数量随着棋盘大小的增加而急剧增加。

在8×8的棋盘上有92个解，而在9×9的棋盘上有352个解。

四、讨论与总结八皇后问题是一个非常经典的数学问题，通过本次实验我们可以得出以下结论：1. 回溯算法是求解八皇后问题的有效方法，可以找到所有的解。

目录一、引言 (2)二、算法分析及流程 (2)三、实验过程分析 (4)四、结果与讨论 (5)五、改进 (5)六、结语 (7)一、算法分析及流程1、八皇后问题是一个古老而著名的问题。

该问题是十九世纪著名的数学家高斯1850提出；在8×8格的国际象棋上摆放八皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

高斯认为有76种方案。

1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后人有人用图论的方法解出92宗结果。

虽然问题的关键在于如何判定某个皇后所在的行、列、斜线是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在“/”斜线上的行列值之和相同；如果在对角线上，则行列号之和或之差相等，逐个纪录符合题意的情况,最终得出解。

//自定义一个类：CQueenclass cQueen {int aQueen[8]; //可以在类外访问的私有成员(默认)int sum;public: //只能被该类的成员函数所访问的公有成员cQueen(); //构造函数：确保每个对象正确地初始化int judge(int x,int y);void show();void step();};cQueen::cQueen()//通过构造函数对aQueen[1---8]初始化{sum=0;for(int i=0;i<8;i++)aQueen[i]=0;}int cQueen::judge(int x,int y) //判断皇后摆放位置是否有冲突，如果没有冲突，则返回；如果有冲突，则返回{for(int i=0;i<x;i++)if(aQueen[i]==y || aQueen[i]+x-i==y || aQueen[i]-x+i==y)return 0;return 1;}void cQueen::step() //一步一步进行查找摆放{int x=0,y=0;//标记皇后所在键盘位置，x代表列，y代表行（相当于坐标）while(aQueen[0]<8){while(y<8){if(judge(x,y)) //调用类函数judge(x,y),如果aQueen[1---8]都已经标记，则执行该语句{aQueen[x]=y; //摆放皇后x++; //进行下一列时y=0; //y进行重置}else //否则，进入下一行y++;} //当执行到最后一行时，继续执行下一个if语句if(y==8&&x!=8) //最后一行，从第一列开始{if(aQueen[--x]!=7)y=++aQueen[x];else if(aQueen[0]!=7)y=++aQueen[--x];elseaQueen[0]=8;}if(x==8) //最后一列{show(); //x,y从至结束,大循环结束if(aQueen[--x]!=7)y=++aQueen[x];elsey=++aQueen[--x];}}}void cQueen::show()//输出棋盘状态{cout<<"(非递归法)皇后摆放方式的第"<<++sum<<"种情况："<<endl;for(int i=0;i<8;i++) //输出八皇后的各种状态，有皇后的位置用@ 表示，没有皇后的位置用* 表示{for(int j=0;j<aQueen[i];j++)cout<<setw(2)<<"*";cout<<setw(2)<<"@";for(j++;j<8;j++)cout<<setw(2)<<"*";cout<<endl;}cout<<sum<<": ";for(int k=0;k<8;k++)cout<<'('<<k+1<<','<<aQueen[k]+1<<")";cout<<endl<<endl;//system("pause");//从程序里调用pause命令,一个结果一个结果地看}void measure2(){cQueen a;a.step();}二、实验过程分析在本次的课程设计中，用到的知识点主要有：类、函数、选择结构里的条件语句、循环结构里的while语句以及for循环语句、控制语句里的break语句、以及字符串函数的运用等等,并且应用到递归、回溯及穷举等比较经典的算法。

数据结构实验报告——八皇后问题实验目的:熟练掌握栈操作的基本算法实现。

实现功能:利用回溯法和栈来实现八皇后问题：在8×8的国际象棋棋盘上, 安放8个皇后, 要求没有一个皇后能够“吃掉”任何其他一个皇后, 即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一对角线。

设计思路:数据结构:enum boolean { false , true }enum boolean a[9] , b[17] , c[17] ;//检查皇后之间是否冲突//皇后位置安全性可用逻辑表达式: a[ j ] && b[ i+j ] && c[ i-j+9 ]int s[9];//s[1..8]表示顺序栈, 栈的下标值表示皇后所在的行号, 栈的内容是皇后所在的列号。

该算法抽象描述如下:置当前行当前列均为1；while(当前行号≤8){ 检查当前行, 从当前列起逐列试探, 寻找安全列号；if ( 找到安全列号)放置皇后, 将列号记入栈中, 并将下一行置成当前行, 第一列置为当前列；else退栈回溯到上一行, 移去该行已放置的皇后, 以该皇后所在列的下一列作为当前列；} 结束程序。

程序流程图:源程序：#include<stdio.h>enum boolean {FALSE,TRUE}; //声明全局变量enum boolean a[9],b[17],c[17];int s[9];int num=0;//函数声明void print();void movequeen();void eightqueen();void main(){ //主函数eightqueen();printf("共有%d种解法\n",num);}void print() //输出函数{int k;printf("\n");printf("NO.%d\n",++num);printf("行号: 1 2 3 4 5 6 7 8\n");printf("列号:");for(k=1;k<=8;k++)printf("%3d",s[k]);printf("\n");}void movequeen(int i,int j){a[j]=TRUE;b[i+j]=TRUE;c[i-j+9]=TRUE;}void eightqueen()//算法函数{int i,j;for(i=2;i<=16;i++){if(i>=2&&i<=9)a[i-1]=TRUE;b[i]=TRUE;c[i]=TRUE;}i=1;j=1;while(i>=1){while(j<=8){if(a[j]&&b[i+j]&&c[i-j+9])break;j++;}if(j<=8){a[j]=FALSE;b[i+j]=FALSE;c[i-j+9]=FALSE;s[i]=j;if(i==8){num++；print();movequeen(i,j);i--;j=s[i];movequeen(i,j);j++;}else {i++;j=1;}}else{i--;if(i>=1){j=s[i];movequeen(i,j)；j++;}}}}实验心得:通过本次实验大大的提高了我个人的动手能力, 对VC编程更加的熟练, 这个程序也一定程度的锻炼了我的思考能力, 对于八皇后问题的逻辑编排, 全局处理, 细节完善等方面都有一个深刻的认识。

数据结构课程设计报告八皇后问题设计任务书课题名称八皇后设计目的1.调研并熟悉八皇后的基本功能、数据流程与工作规程；2.学习八皇后相关的算法和基于VC++集成环境的编程技术；3.通过实际编程加深对基础知识的理解，提高实践能力；4.学习开发资料的收集与整理，学会撰写课程设计报告。

实验环境1.微型电子计算机（PC）；2.安装Windows 2000以上操作系统，Visual C++6.0开发工具。

任务要求1.利用课余时间去图书馆或上网查阅课题相关资料，深入理解课题含义及设计要求，注意材料收集与整理；2.在第16周末之前完成预设计，并请指导教师审查，通过后方可进行下一步工作；3.本课题要求至少用三种方法解决八皇后问题，输入棋盘的阶层，然后显示共有多少种布局方案，并显示每一种方案的具体情况。

4.结束后，及时提交设计报告（含纸质稿、电子稿），要求格式规范、内容完整、结论正确，正文字数不少于3000字（不含代码）。

工作进度计划序号起止日期工作内容1 2009.06.7~2009.06.7 在预设计的基础上，进一步查阅资料，完善设计方案，形成书面材料。

22009.06.7~2009.06.10设计总体方案，构建、绘制流程框图，编写代码，上机调试。

3 2009.06.11~2009.06.12测试程序，优化代码，增强功能，撰写设计报告。

4 2009.06.12~2009.06.13提交软件代码、设计报告，参加答辩，根据教师反馈意见，修改、完善设计报告。

指导教师（签章）：2013 年 5 月 15 日摘要：众所周知的八皇后问题是一个非常古老的问题，具体如下：在8*8的国际象棋棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上,这是做出这个课题的基础。

要求编写实现八皇后问题的递归解法或非递归解法，对于任意给定的一个初始位置，输出八皇后问题的一个布局。

本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力。

数据结构作业报告——八皇后姓名：李慧卓班级：071121班学号：07112012上机时间：2012-12-17报告时间：2013-01-05摘要1.实验目的熟悉树中回溯法与树的遍历。

2.实验方法本程序利用if函数中的条件判断，辅之循环，按要求摆放棋子。

总共有3个子函数，分别为显示结果函数，检查合法函数，置棋函数。

3.实验结果运行结果显示了符合规则的所有摆放八皇后的方法。

内容一．问题重述在8*8的棋盘上，摆放八个皇后，是之不能相互攻击，即任意两个棋子不在同一列、行、斜线上。

显示所有摆法。

二．算法描述四．函数与思路说明本函数运用了条件语句，其中最重要的判断是否合法即用if条件判断实现。

运用树的概念进行列举而后判断。

本程序总共有3子函数，1个主函数，其中3个子函数分别为show_result（）子函数，check_cross ()子函数，put_chess ()子函数。

五．程序执行结果六．结论参考列子，在根据实际情况调整编改，运行成功。

七．编程中遇到的问题以及解决方法参考网范例发现函数构成比较简单。

修改了头文件对getch（），puts()进行了了解。

八．附录#include "stdafx.h"#include <stdio.h>#include <conio.h> //配合getch()使用#include <math.h>#define MAX 8 /*棋子数及棋盘大小MAX*MAX*/int board[MAX];void show_result(){int i;for(i=0;i<MAX;i++)printf("(%d,%d)",i,board[i]);printf("\n");}/*检查在同一直线上是否有其他的棋子*/int check_cross(int n){int i;for(i=0;i<n;i++) //i小于n,只需与之前的比较{if(((board[i])==(board[n]))||((n-i)==abs((board[i])-(board[n])))) return 1;}return 0;}/*放棋子到棋盘上*/void put_chess(int n){int i;for(i=0;i<MAX;i++){board[n]=i;if(!check_cross(n)){if(n==MAX-1)show_result();/*找到其中一种方法打印出结果*/elseput_chess(n+1);}}}void main(){puts("The possible placements are:");put_chess(0);puts("\nPress any key to quit ...");getch(); ///利用它来实现程序运行完了暂停不退出的效果。