文档视界 最新最全的文档下载
当前位置:文档视界 › 江西理工贪心及回溯法实验报告

江西理工贪心及回溯法实验报告

void backtrack(int t){

if(t>n)

{

printf("第"%d"个解的答案为:",k);

k++;

sum++;

for(int i=1;i<=n;i++)printf("%d",x[i]);

}

else

{

for(int i=1;i<=n;i++)

{

x[t]=i;

if(place(t)) {

backtrack(t+1);

}

}

}

}

main(){

int nn;

printf("输入n皇后n值:");

scanf("%d %d",&n,&n);

nQueen(nn);

}

江西理工大学

《算法分析与设计》课实验报告

实验三贪心及回溯法

专业班级实验人学号

实验日期同组人

一、实验目的

1.掌握能用回溯法求解的问题应满足的条件;

2.加深对回溯法算法设计方法的理解与应用;

3.锻炼学生对程序跟踪调试能力;

4.通过本次实验的练习培养学生应用所学知识解决实际问题的能力。

二、实验内容

由N2个方块排成N行N列的正方形,称为N元棋盘,在N元棋盘上放置N个皇后,如果某两个皇后位于N元棋盘的同一行或同一列或同一斜线(斜率为±1)上,则称它们在互相攻击,试设计算法找出使N个皇后互不攻击的所有布局。

三、实验要求

(1)用回溯法算法设计方法求解N元皇后问题

(2)找出N皇后问题的互不攻击的所有解

(3)皇后数N由键盘动态输入

(4)上机实现所设计的算法;

(5)分析所设计的算法的时间/空间复杂性。

四、实验过程设计(算法设计过程)

(1)分析N皇后问题的约束条件,并将其显示化,选择存储结构建立相应的数学模型;(2)根据所建立的数学模型,设计求解该问题的粗略算法;

(3)对所设计的粗略算法求精,得具体算法;

(4)在C/C++/VC++下实现所设计的算法;

(5)分屏显示结果;

(6)分析运行结果的正确性;

(7)进行算法效率分析;

(8)课后写出实验报告。

五、实验结果和分析

六、实验体会

通解n后问题主要在于可行解,一个一个的试,(t)能走通就往(t+1)下走,走不通就倒回去(t-1)换条走,再不行再回走。就要不停的尝试,不停的回溯,直到找全可行解,或者一个也没有就停止。还有重要的事约束条件,两个皇后不能在同行同列或者斜线上。

七、附录:(源代码)#include "iostream.h"

#include "string.h"

#include

int n;

int sum=0;

int k=1;

int nQueen(int nn)

{

n=nn;

void backtrack(int t);

for(int i=0;i<=n;i++)

{

x[i]=0;

}

backtrack(1);

return sum;

}

int place(int k)

{

for(int j=1;j

{

if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))

{

return 0;

}

相关文档
相关文档 最新文档