回溯法实验报告

数学与计算机学院实验报告

版面要求：A3页面，双面打印 学年学期 2015-2016 学年 03学期 课程名称 算法设计与分析 专 业 计算机科学与技术 班 级 2014级一班 学 号 LX14115150 姓 名 申畅恒 任课教师 苏鹏

一、实验项目信息

项目名称： 回溯法 实验时间： 2016/06/08 实验学时： 03 学时

实验地点： 工科楼503 二、实验目的及要求

理解回溯法的深度优先搜索策略、 掌握用回溯法解题的算法框架、 掌握回溯法的设计策略

三、实验环境

计算机Ubuntu Kylin14.04 CodeBlock软件

；.

..

四、实验内容及实验步骤

排兵布阵问题

某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n个不同兵种的角色{1,2,...,n}，需安排在某战区n个点上，角色i在j点上的攻击力为Aij。试设计一个布阵方案，使总的攻击力最大。

数据：

防卫点

1 2 3 4 5 1 60 40 80 50 60 角2 90 60 80 70 20 色

3 30 50 40 50 80 4 90 40 30 70 90 5

60 80 90 60 50

回溯法： 程序：

#include int position[10]; int a[10][10];

int check(int k){//每个节点检查的函数 int i;

for(i=0;i

if(position[i]==position[k])return 0;//重复返回0 return 1; }

void gameSort(int n){ int i,k; int max=0; int ans[10]; int sum;

for(i=0;i

while(k>=0) {

sum=0;

position[k]=position[k]+1; while(position[k]<=n)

if(check(k))break;

else position[k]=position[k]+1; if(position[k]<=n && k==n-1) {

for(i=0;i

sum+=a[i][position[i]-1]; }

if(max

for(i=0;i

ans[i]=position[i]; } }

if(position[k]<=n&&k

position[k--]=0; }

printf(\ for(i=0;i

printf(\ printf(\

printf(\ }

void main() {

int i,j,n;

printf(\ scanf(\

for(i=0;i

scanf(\

gameSort(n); printf(\}

；.

..

五、实验结果分析

程序运行：得到正确结果

六、实验总结

通过实验对回溯法求解的概念更加熟悉，对回溯法的程序算法深入理解。掌握如何编写

回溯法的框架以及回溯法的检测（check()）函数。能够对一个问题进行分析是否能够使用回溯法求解。

七、教师评价 批阅教师 成绩 批阅时间 教师评语