《算法设计与分析》实验三-林声恒2107120604.docVIP

学号2107120604

《算法设计与分析》

实验报告三

学生姓名

林声恒

专业、班级

21计算机二班

指导教师

唐国峰

成绩

计算机与信息工程学院计算计系

2023年9月28日

实验三：回溯算法运用练习

一、实验目的

本次实验是针对回溯算法的设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。

二、实验步骤与要求

1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；

2．学生独自完成实验指定内容；

3．实验结束后，用统一的实验报告模板编写实验报告。

4．提交说明：

（1）电子版提交说明：

a需要提交Winrar压缩包，文件名为“《算法设计与分析》实验三_学号_姓名”，

如“《算法设计与分析》实验三张三”。

b压缩包内为一个“《算法设计与分析》实验三_学号_姓名”命名的顶层文件夹，

其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验

报告电子版”。其下分别放置对应实验成果物。

（2）打印版提交说明：

a不可随意更改模板样式。

b字体：中文为宋体，大小为10号字，英文为TimeNewRoman，大小为10号

字。

c行间距：单倍行距。

（3）提交截止时间：2023年10月12日16:00。

实验项目

1．请用回溯法对下列问题进行求解。

题目（5选3）：

（1）数读问题（标准数读）；

（2）n后问题；

（3）符号三角形问题；

（4）0-1背包问题；

（5）四城市旅行商问题。

四、实验过程

（一）题目一：n后问题；

题目分析

在n×n棋盘上放彼此不受攻击的n个皇后。按照国际象棋规则，皇后可以攻击同行、同列、同一斜线的棋子。等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上.。所以建立q[N]记录各行皇后所在的列，即i行皇后在第q[i]列。

算法构造

在此论证算法设计中的一些必要的设计依据。

n代表皇后数量首先递归函数n_queens(1,n)对整个空间进行回溯搜索，它从第k行开始，试探每一列，通过isSafe(k,j)检查在给定的位置(k,j)上放置皇后是否安全。如果在一列上放置皇后是安全的，就递归到下一行。当所有行都试探完之后，就找到了一种解法，然后调用print(n)输出这个解。

算法实现

#includestdio.h

#includestdlib.h

#defineN20//皇后的数量

intq[N];//各行皇后所在的列

intcount=0;//统计N皇后问题解的个数

//输出N皇后问题的解决方案

voidprint(intn)

{

inti,j;

count++;

printf(第%d个解：\n,count);

for(i=1;i=n;i++)//行

{

for(j=1;j=n;j++)//列

{

if(q[i]!=j)

printf(x);

else

printf(Q);

}

printf(\n);

}

printf(\n);

}

//检验第k行第j列上是否可以摆放皇后

intisSafe(intk,intj)

{

inti;

for(i=1;ik;i++){

//如果有其它皇后位置同一列上，或者位于该位置的斜线位置上，则该位置无法使用

if(q[i]==j||abs(i-k)==abs(q[i]-j))

return0;

}

return1;

}

//放置皇后到棋盘上

voidn_queens(intk,intn)

{

intj;

if(kn)//递归的出口

print(n);

else

{

for(j=1;j=n;j++)//试探第k行的每一列，找到符合要求的列

{

if(isSafe(k,j))

{

q[k]=j;