logo资料库

八皇后问题实验报告.docx

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.18M 资料格式：docx 举报 版权申诉
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
资料共9页，剩余部分请下载后查看
    实验报告
    实验报告 ——八皇后问题求解（递归和非递归） 学号： 专业年级： 姓名： 一、需求分析（要实现的功能描述） 1．问题描述 八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置 八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都 不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的 n 皇后摆放问题：这 时棋盘的大小变为 n×n，而皇后个数也变成 n。当且仅当 n = 1 或 n ≥ 4 时问题有解。八皇 后问题最早是由国际囯际象棋棋手马克斯·贝瑟尔于 1848 年提出。诺克也是首先将问题推 广到更一般的 n 皇后摆放问题的人之一。 2．实现功能 八皇后问题实现了在棋盘上摆放八个皇后的功能，这八个皇后任意两个皇后都不能处于 同一条横行、纵行或斜线上。
    3．测试数据 测试数据可以通过手工寻找三组满足需要的值，测试数组（M，N），其中 M 代表皇后 所在的行，N 代表皇后所在的列。例如，第一组测试数据： （1，4）、（2，7）、（3，3）、（4、8）、（5，2）、（6，5）、（7，1）、（8，6）；第二组测试数据 （1，5）、（2，2）、（3，4）、（4，7）、（5，3）、（6，8）、（7，6）、（8，1）；第三组测试数据： （1，4）、（2，2）、（3，7）、（4，3）、（5，6）、（6，8）、（7，5）、（8，1）。最后与编程求得 的结果进行比较。如果这三组数据在最后编程求得的结果中，说明程序的编写基本没有什么 问题。 二、概要设计 在进行概要设计的过程中，要清楚整个程序包含的功能模块及模块间的调用关系。 对于八皇后问题，整个程序中应该包括主函数模块，摆放皇后的函数模块，以及判断皇 后的位置是否摆放正确的判断模块。对于模块间的关系，在运行主函数的过程中会调用摆放 皇后的函数模块，在摆放皇后的函数模块中，又会调用判断皇后位置是否摆放正确的判断模 块。 三、详细设计 抽象数据类型中定义的各种操作算法实现（用 N-S 图描述） 对于求解八皇后问题的非递归算法，N-S 图如下： 运行 queens 函数 定义 8 个皇后，并且开辟 9 个空间（a[0]不用）初始化为 0，初始化 k 为第一列,即 k=1； 当 k>0 时候 在 a[k]的位置上摆放一个皇后，即皇后的位置用数组表示为（a[k],k） 当摆放皇后没有到列的最底部，并且摆放不冲突的时候 将皇后下移一位 皇后位置到达底部？ 是 否 回溯到 k-1 步 八列皇后全摆放完毕？ 是 否 打印出皇后摆 放的情况 继续摆放下一列 初始化 a[k]=0
    对于八皇后问题求解的递归算法，N-S 图如下： 调用 queen 函数，摆放第 k 个皇后(k 从 1 开始) 是否将最后一个皇后摆放完毕？ 是 否 检测摆放的皇后是否冲突 打印摆放皇后的情况 是 否 重新摆放 继续摆放下一个皇后 四、调试分析 1．程序在调式过程中出现的问题及解决方法 由于对于 C 语言编程问题掌握的并非十分熟练，因而在程序的调试过程中出现了一些 问题。例如，在编写位置冲突算法的过程中，在解决对角线问题上，没有考虑对角线有两条， 只考虑了其中的一条，因而在编写程序的过程中，没有使用绝对值，导致得到的满足要求的 测试结果比实际的要多得多。 再如，为了能够输出比较整齐的测试结果，开始的时候只是输出了皇后所在的列数，没 有输出皇后的行数。后来，在添加了行数坐标后，两个程序输出了相同的比较整齐美观的测 试结果。 2．算法的时间复杂度分析 在考虑算法的时间复杂度问题上，只需考虑每个函数的最大的时间复杂度即可，求得的 最大的时间复杂度即为整个程序的时间复杂度。 对于递归程序的时间复杂度： 对于非递归程序的时间复杂度： O() O() 因而，对于递归和非递归程序两个程序的时间复杂度，递归程序的时间复杂度要高。
    五、用户手册 由于在程序编写的过程中，使用的环境为 Visual C++ 6.0，因而在使用的过程中，最好 使用 Visual C++ 6.0，以免在程序运行错误。 本程序的操作过程十分简单，不需要操作者有 C 语言基础。 六、测试结果 通过对于问题的编程求解，共得到了 92 种结果。从中任意选择三组数据进行测试。数 组的第一个数值为皇后所在的行，第二个值为皇后所在的列。 第一组测试数据： （1，4）、（2，7）、（3，3）、（4、8）、（5，2）、（6，5）、（7，1）、（8，6） 用图像形象表示为： 再如，第二组测试数据： （1，5）、（2，2）、（3，4）、（4，7）、（5，3）、（6，8）、（7，6）、（8，1） 第三组测试数据：
    （1，4）、（2，2）、（3，7）、（4，3）、（5，6）、（6，8）、（7，5）、（8，1） 由于空间有限，所以 92 种测试结果用数组的形式表示如下：
    七、程序清单 非递归问题的程序清单： #include #include //位置冲突算法 int Chongtu(int a[], int n)//a[]位置数组，n 皇后个数 { int i = 0, j = 0; for (i = 2; i <= n; i++)//i：位置 for (j = 1; j <= i-1; j++)//j：位置 return 0;//冲突 } //八皇后问题：回溯法（非递归） void Queens8() { if ((a[i] == a[j]) || (abs(a[i]-a[j]) == i-j))//在同一行或在同一对角线上 return 1; //不冲突 int n = 8; int count = 0; int a[9] = {0}; //定义 8 个皇后 //记录当前第几种情况 //存放皇后位置，如：a[2] = 4;表示第 2 列第 4 行有一个皇 后（a[0]不用） int i = 0,k = 1; //初始化 k 为第一列 a[1] = 0; //初始化 a[1] = 0 while (k > 0) 找完所有情况） //k==0 时：表示摆放第 1 个皇后就超过了列底部（即已经 { a[k] += 1; while ((a[k] <= n) && (Chongtu(a,k)))//如果 a[k]（即皇后摆放位置）没有 //a[k]位置，摆放一个皇后 到列最底部，且摆放冲突。 a[k] += 1;//将皇后列下移一位 if (a[k] <= n)//皇后摆放位置没有到达列最底部 { if (k == n)//k==n 表示，8 列皇后全部摆放完毕 { printf("第%d 种情况：",++count); for (i = 1; i <= n; i++)//打印情况 printf("(%d,%d) ",i,a[i]); printf("\n"); }
    else { //皇后还未摆放完毕 k += 1; a[k] = 0; //继续摆放下一列 //此行初始化 a[k] = 0;表示第 k 列，从第一行开始摆 放皇后 } } else //回溯：当 a[k]>8 进入 else,表示在第 k 列中没有找到合适的摆放 k -= 1;//回溯到 k-1 步：k 表示第几个皇后，a[k]表示第 k 个皇后摆 位置 放的位置 } return; } //主函数 int main() { Queens8(); return 0; } 递归问题的程序清单： #include #include int a[9] = {0}; int n = 8, count = 0; //位置冲突算法 int Chongtu(int a[], int n)//a[]位置数组，n 皇后个数 { int i = 0, j = 0; for (i = 2; i <= n; i++)//i：位置 for (j = 1; j <= i-1; j++)//j：位置 if ((a[i] == a[j]) || (abs(a[i]-a[j]) == i-j))//在同一行或者同一对角线上 return 0; //冲突 return 1;//不冲突 } //八皇后问题：回溯算法（递归版） void Queens8(int k) //参数 k：递归摆放第 k 个皇后 {
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料