欢迎来到天天文库
浏览记录
ID:18872580
大小:59.06 KB
页数:9页
时间:2018-09-26
《数据结构课程实践》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、——课程实践数据结构课程设计报告学校:哈尔滨理工大学学院:管理学院专业:信息管理与信息系统姓名:苏雅班级:信管11——2学号:1106040213N皇后问题一、设计要求与分析1.设计要求在一个n*n的棋盘上放置n个皇后,要求放置的n个皇后不会互相吃掉;皇后棋子可以吃掉它所在的那一行、那一列,以及那两条对角线上的任何棋子。2设计分析此问题由八皇后问题演变而来,是八皇后问题的升级版,你可以随意输入一个比4大的数字,本程序将自动求出相关的某皇后问题。回溯算法是尝试搜索算法中最为基本的一种算法,并采用了一种“走不通就掉头”的思想,当
2、发现已不满足求解条件时,就“回溯”返回,尝试跌的路径。解决8皇后的算法有多种,其中加约束条件的枚举算法拥有最好的可读性,也能从中体会到回溯的思想,但是它职能解决皇后“个数为常量”的问题,却不能解决任意的n皇后问题,因此也不是典型的回溯算法模型。非递归算法可以说是典型的回溯算法模型但是对于回溯算法,更方便的是用递归控制方式实现,用这种方法可以解决任意的n皇后问题。算法思想同样实现用深度优先搜索,并在不满足约束条件时及时回溯二、算法求精这个问题包括了行,列,两条对角线; 列:规定每一列放一个皇后,不会造成列上的冲突; 行:当
3、第i行被某个皇后占领后,则同一行上的所有空格都不能再放皇后,要把以i为下标的标记置为被占领状态; 对角线:对角线有两个方向。在这我把这两条对角线称为:主对角线和从对角线。在同一对角线上的所有点(设下标为(i,j)),要么(i+j)是常数,要么(i-j)是常数。因此,当第i个皇后占领了第j列后,要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。/*-------------------------回溯法--------------------------*///static:避免命名有冲突//棋盘初始化时,空格的地
4、方为+,放置皇后的地方为?staticcharQueen[20][20];staticinta[20];//数组a[i]:a[i]表示第i个皇后放置的列,i的范围:----8staticintb[40];//主对角线数组staticintc[40];//从对角线数组,根据程序的运行,去决定主从对角线是否放入皇后staticintiQueenNum=0;//记录总的棋盘状态数staticintNum=1;intn;voidiQueen(introw);//参数i代表行voidlocation(){introw;//横行intc
5、ow;//纵行for(row=0;row6、row+cow]==0)//如果无冲突{Queen[row][cow]='?';//放皇后a[cow]=1;//标记,下一次该列上不能放皇后b[row-cow+n-1]=1;//标记,下一次该主对角线上不能放皇后c[row+cow]=1;//标记,下一次该从对角线上不能放皇后if(row7、"<8、+;cout<
6、row+cow]==0)//如果无冲突{Queen[row][cow]='?';//放皇后a[cow]=1;//标记,下一次该列上不能放皇后b[row-cow+n-1]=1;//标记,下一次该主对角线上不能放皇后c[row+cow]=1;//标记,下一次该从对角线上不能放皇后if(row7、"<8、+;cout<
7、"<8、+;cout<
8、+;cout<
此文档下载收益归作者所有