回溯法实验报告

《回溯法实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、回溯法实验报告专业：网络工程班级：组别：2012——2013学年第一学期课程名称计算机算法设计与分析指导教师本组成员学号姓名实验地点一号楼机房5实验时间2012.12.5实验名称实验五回溯法实例编程实验类型综合性实验环境：一台PC实验内容：1.符号三角形问题。符号三角形定义为等边三角形，共n行，第i（0=

2、  +  -  -  +  +  -  -  +  -  -  -  +给定行数n，编程输出所有符号三角形。输入：n：符号三角形的边长（首行中符号的个数）；输出：（1）count：符号三角形的个数；（2）所有符号三角形。2.给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?输入：第一行：n，c,分别表示物品数量和背包容量；第二行：n件物品的重量和价值。输出：最大价值和装包方案。实验目的与要求：1.掌握回溯法的基本思想。2.能够使用回溯法解决具体问题。3.能准确地分析回溯法的效率及稳定性。

3、设计思路：（设计原理、设计方案及流程等）1、回溯法的基本思想2、解空间树的表示和构造3、回溯法算法的递归实现关键技术分析：实验一分析：（1）边长为n的任一符号三角形中总符号数为：n/(n+1)/2；（2）n/(n+1)/2不能为奇数，“+”和“-”的个数相同，均为n/(n+1)/4（3）当符号三角形的首行符号确定时，符号三角形唯一确定；（4）穷举所有符号三角形即：穷举首行符号的所有可能组合；（5）回溯法遍历过程中，剪枝函数可定义为：底边符号数为i个时所确定的子三角形中“+”或“-”的个数不超过n/(n+1)/4；（6）当遍历到达叶结点时，需判断是否满足符号三角形的所有

4、约束；（7）当遍历到达叶结点时，需根据底边符号的选取，构造并输出整个符号三角形（不大于2n）实验步骤：实验程序代码：实验1.符号三角形问题#includeusingnamespacestd;typedefunsignedcharuchar;charcc[2]={'+','-'};//便于输出intn,//第一行符号总数half,//全部符号总数一半counter;//1计数，即“-”号计数uchar**p;//符号存储空间longsum;//符合条件的三角形计数t，第一行第t个符号voidBacktrace(intt){inti,j;if(t>n)

5、{//符号填充完毕sum++;//打印符号cout<<"第"<=2时，可以运算出下面行的某些符号{p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-

6、j+2];//通过异或运算下行符号counter+=p[j][t-j+1];}if((counter<=half)&&(t*(t+1)/2-counter<=half)){//若符号统计未超过半数，并且另一种符号也未超过半数Backtrace(t+1);//在第一行增加下一个符号}//回溯，判断另一种符号情况for(j=2;j<=t;++j){counter-=p[j][t-j+1];}counter-=i;}}}intmain(){cout<<"请输入第一行符号个数n：";cin>>n;counter=0;sum=0;half=n*(n+1)/2;inti=0;if

7、(half%2==0){//总数须为偶数，若为奇数则无解half/=2;p=newuchar*[n+1];for(i=0;i<=n;++i){p[i]=newuchar[n+1];memset(p[i],0,sizeof(uchar)*(n+1));}Backtrace(1);for(i=0;i<=n;++i){delete[]p[i];}delete[]p;}cout<<"总共"<usingnamespac