回溯法实验报告.doc

数学与计算机学院实验报告版面要求:A3页面,双面打印学年学期2015-2016学年03学期课程名称算法设计与分析专业计算机科学与技术班级2014级一班学号LX14115150姓名申畅恒任课教师苏鹏一、实验项目信息项目名称:回溯法实验时间:2016/06/08实验学时:03学时实验地点:工科楼503二、实验目的及要求理解回溯法的深度优先搜索策略、掌握用回溯法解题的算法框架、掌握回溯法的设计策略三、、实验内容及实验步骤排兵布阵问题某游戏中,不同的兵种处在不同的地形上其攻击能力不一样,现有n个不同兵种的角色{1,2,...,n},需安排在某战区n个点上,角色i在j点上的攻击力为Aij。试设计一个布阵方案,使总的攻击力最大。数据:防卫点角色123451604080506029060807020330504050804904030709056080906050回溯法:程序:#include<>intposition[10];inta[10][10];intcheck(intk){//每个节点检查的函数 inti; for(i=0;i<k;i++) if(position[i]==position[k])return0;//重复返回0 return1;}voidgameSort(intn){ inti,k; intmax=0; intans[10]; intsum; 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; elseposition[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 po