logo资料库

八皇后问题课程设计报告.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.10M 资料格式：doc 举报 版权申诉
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
资料共9页，剩余部分请下载后查看
    课程设计题目： 名称：八皇后问题 内容：设计程序完成如下要求：在 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、程序的流程图如下图所示： Main 建立数组表示皇后在棋盘上的位置 在不同行的基础上检测某个皇后的同 列和同斜线上是否存在其他皇后 输 出 正 确 解 法 的 排 列形式 输出正确解 法的棋盘 摆放形式 输 出 所 有 正 确 解 法 的 个 数，程序结束 图 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
    {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;jqueen[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;jqueen[i];j--) { printf(" +");}; printf("\n"); //皇后 //每行中皇后后面的棋盘 } clrscr(); } 四、上机调试 本次课程设计中遇到了许多的困难，产生了不少的问题。 1、刚开始使用结构体表示皇后的位置，构造了较多的变量，程序设计中产生了许多的 错误，判断同斜线情况不太方便，算法性能也不少很好。后来想到运用数组来表示皇后的位 置，不但数据结构简单，而且较容易的表示处皇后的位置，容易分析皇后同列、同斜线的情
    况（用到 abs( )函数），所以建立整型数组来表示皇后在棋盘上的位置。 2、动态输出棋盘摆放形式的时候，自动输出的速度太快，无法观察清楚，后来只好运 用 getchar( )函数接受一个空的字符手动控制棋盘的输出。 五、测试结果及其分析 程序运行结果如下各图所示： 分析：本次课程设计完成之后，仍觉得有些不足之处，例如无法让电脑自动输出动态 的摆放皇后过程，必须手动操作完成。算法的时间复杂度也不是很好。 各函数的时间复杂度如下： int judge(int *p, int j) int check(int queen[], int i) void show(int queen[]) void print(int queen[]) void go(int queen[], int i) 时间复杂度为 O(n) 时间复杂度为 O(n2) 时间复杂度为 O(n9) 时间复杂度为 O(n2) 时间复杂度为 O(n) 图 2 程序运行结果部分截图(1)
    图 3 程序运行结果部分截图(2) 图 4 程序运行结果部分截图(3)
    图 5 六、用户使用说明 程序运行结构部分截图(4) 执行.exe 程序按照提示，按回车输出两种结果。 七、参考文献 【1】王昆仑 李红. 数据结构与算法. 中国铁道出版社. 2007 年 6 月第一版. 【2】何钦铭 颜晖. C 语言程序设计. 高等教育出版社. 2008 年 4 月第一版. 八、附录 #include #include #include int count=0; int queen[8]; 二列上） //定义一个整型变量 count 来统计正确解法的个数 //定义数组表示皇后所处的位置（queen[3]=2 表示皇后在第三行和第 //检测皇后是否在同列或者同一斜线上 //皇后在同一列上的情况 int judge(int *p, int j) { int i; for(i=0;i
    } 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; } 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;jqueen[i];j--)//皇后后面输出"+" { printf(" +"); }; printf("\n"); } printf("press anykey to show next answer:"); getchar(); //接收字符 } void go(int queen[], int i) { //递归函数 if(i>=8) { //一个棋盘上摆满 8 个皇后时 count++; print(queen); //统计一次方法 //输出一个正确的解法 } else { int j; for(j=0;j<8;j++) { queen[i]=j; if(check(queen, i)) { go(queen,i+1); //函数递归
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

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

    热门标签

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

    最新资料