数学与计算机学院实验报告
一、实验项目信息
项目名称：回溯法
实验时间： 2016/06/08 实验学时： 03 学时
实验地点：工科楼503 二、实验目的及要求
理解回溯法的深度优先搜索策略、
掌握用回溯法解题的算法框架、
掌握回溯法的设计策略
三、实验环境
计算机Ubuntu Kylin14.04
CodeBlock软件四、实验内容及实验步骤
排兵布阵问题
某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n个不同兵种的角色{1,2,...,n}，需安排在某战区n个点上，角色i在j点上的攻击力为A ij。

试设计一个布阵方案，使总的攻击力最大。

数据：
防卫点
角
色
1 2 3 4 5
1
2
3
4
5
回溯法：
程序：
#include<stdio.h>
int position[10];
int a[10][10];
int check(int k){//每个节点检查的函数
int i;
for(i=0;i<k;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<n;i++)
position[i]=0;
k=0;
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<n;i++)
{
sum+=a[i][position[i]-1];
}
if(max<sum){
max=sum;
for(i=0;i<n;i++)
ans[i]=position[i];
}
}
if(position[k]<=n&&k<n-1)
k=k+1;
else
position[k--]=0;
}
printf("answer is:");
for(i=0;i<n;i++)
printf("(%d,%d) ",i+1,ans[i]);
printf("\n");
printf("the largest number is:%d",max); }
void main()
{
int i,j,n;
printf("please input n:");
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
gameSort(n);
printf("\n");
} 五、实验结果分析
程序运行：得到正确结果
六、实验总结
通过实验对回溯法求解的概念更加熟悉，对回溯法的程序算法深入理解。

掌握如何编写回溯法的框架以及回溯法的检测（check()）函数。

能够对一个问题进行分析是否能够使用回溯法求解。

七、教师评价。