n皇后实验报告.docx

该【n皇后实验报告 】是由【大于振】上传分享，文档一共【8】页，该文档可以免费在线阅读，需要了解更多关于【n皇后实验报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。实验报告
实验名称n皇后问题
课程名称计算机算法设计与解析
专业班级:学生姓名:
学号:成绩:
指导老师:实验日期:
1/8
一、实验内容
要求在一个n*n的棋盘上放置n个皇后,使得它们互相不受攻击。
一个皇后能够攻击与之处在同一行或同一列或同一斜线上的任何其
他棋子。
二、实验基本思想
典型深度优先遍历,假设某一行为当前状态,不断检查该行全部
的地址可否能放一个皇后,检索的状态有两种:
(1)先从首位开始检查,若是不能够放置,接着检查该行第二个位
置,依次检查下去,直到在该行找到一个能够放置一个皇后的地方,
尔后保存当前状态,转到下一行重复上述方法的检索。
(2)若是检查了该行全部的地址均不能够放置一个皇后,说明上一
行皇后放置的地址无法让全部的皇后找到自己适合的地址,因此就要
回溯到上一行,重新检查该皇后地址后边的地址。
三、算法设计
问题的解可表示为x[1:n],表示皇后i放在棋盘的第i行的第
2/8
x[i]列。
a)x[i]≠x[j],i≠j:不一样意将任何两个皇后放在同一列上;
b)|j-i|≠|x[j]-x[i]|:不一样意两个皇后位于同一条斜线上。
问题的解空间的形式为:
要找出”四皇后”问题的解,最可靠的方法就是把各种情况全部检核一遍,将吻合条件A的解找出来。但这样做,你要有相当耐心才行,这是很费时的。采用回溯算法进行求解,在找寻的过程中,将不满足条件要求的分支树减去,能够有效的降低算法的时间复杂性。
后问题的算法描述以下:
剪枝函数:
boolOk(intt)
{
inti;
3/8
for(inti=0;i<t;i++){
if(x[t]==x[i]||abs(t-i)==abs(x[t]-x[i]))
return0;
}
return1;
}
voidBacktrack(intt)
{
if(t>=n){
cout<<"第"<<sum<<"个方案:\n";
for(inti=1;i<=n;i++){
for(intj=1;j<=n;j++){
if(j==x[i])
cout<<"1";
else
cout<<"0";
}
cout<<endl;
}
sum++;
}
else{
for(inti=0;i<n;i++){
4/8
x[t]=i;
if(Ok(t))
Backtrack(t+1);
}
}
}
四、实验结果
5/8
五、实验代码
#include<iostream>
usingnamespacestd;
int*x;//当前解
intn;//皇后的个数N
intsum=1;
boolOk(intt)//检查参数所指示的这一行皇后放置方案可否满足要求
{
inti;
for(inti=0;i<t;i++){
if(x[t]==x[i]||abs(t-i)==abs(x[t]-x[i]))
return0;
}
return1;
}
voidBacktrack(intt)
{
if(t>=n){
cout<<"第"<<sum<<"个方案:\n";
for(inti=1;i<=n;i++){
for(intj=1;j<=n;j++){
if(j==x[i])
6/8
cout<<"1";
else
cout<<"0";
}
cout<<endl;
}
sum++;
}
else{
for(inti=0;i<n;i++){
x[t]=i;
if(Ok(t))
Backtrack(t+1);
}
}
}
voidmain()
{
cout<<"输入皇后个数:";
cin>>n;
x=(int*)malloc(sizeof(int)*n);
Backtrack(0);
cout<<"一共的方案数为:"<<sum-1<<"\n";
system("pause");
}
7/8
六、实验心得
经过本次实验的学习,让我认识到了用回溯法能够找寻问题的全部解。它是一个既带有系统性又带有跳跃性的找寻算法,是依照深度优先策略,从根节点出发找寻解空间树。算法找寻至某一节点时,利用判断函数先判断该节点内可否包含问题的解,若是不包含则直接跳过,节约时间。相关的判断函数要依照实责问题来编写,此比较适合求解组合数较大的问题。
总的来说,此次实验不但让我基本掌握递归的思想,而且进一步提高了自己的自学能力和编程能力,使我对算法的解析与设计有更深刻的认识。程序不是一时之事,需要长时间的积累,渐渐付诸实践才能真切的掌握,我会连续努力学习,争取做得更好。
8/8