回溯算法的实验报告.doc

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

1、实验报告一、实验目的：通过分析求符号三角形问题的回溯法并编程实现，掌握回溯法的算法框架。二、实验任务：分析求符号三角形问题的回溯算法，编程实现，调试运行程序并对运行结果进行分析，分析算法的时空复杂度。三、实验内容：1、实现回溯法求符号三角形问题描述2、算法描述3、程序设计四、实验结果与分析：问题描述:一般情况下，符号三角形的第一行有n个符号，三角形中任意位置都为“+”或“-”，且满足以下两个规则：1）三角形中任意行的下一行的符号由以下规则确定：2个同号下面是“+”，2个异号下面是“-”；2）三角形中“+”或“-”数目相同。对于给定的n，计算有

2、多少个不同的符号三角形。问题分析：对于符号三角形问题，用n元组x[1：n]表示符号三角形的第一行的n个符号。当x[i]=1时，表示符号三角形的第一行的第i个符号为“+”号；当x[i]=0时，表示符号三角形的第一行的第i个符号为“-”号；1≤i≤n。由于x[i]是二值的，所以在用回溯法解符号三角形问题时，可以用一棵完全二叉树来表示其解空间。在符号三角形的第一行的前i个符号x[1：i]确定后，就确定了一个由i*（i+1）/2个符号组成的符号三角形。下一步确定了x[i+1]的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为x[1：i+

3、1]所相应的符号三角形。最终由x[1：n]所确定的符号三角形中包含的“+”号个数与“-”号个数同为n*（n+1）/4。因此在回溯搜索过程中可用当前符号三角形所包含的“+”号个数与“-”号个数均不超过n*（n+1）/4作为可行性约束，用于剪去不满足约束的子树。对于给定的n，当n*（n+1）/2为奇数时，显然不存在所包含的“+”号个数与“-”号个数相同的符号三角形。程序代码：#includeclassTriangle{friendintComputer(intn);public:voidBacktrack(intt);in

4、tn,//第一行的符号个数half,//每个三角形总符号数的一半count,//统减号的个数**p;//指向三角形的二维指针longsum;//统计符合条件的的三角形的个数};voidTriangle::Backtrack(intt){if((count>half)

5、

6、(t*(t-1)/2-count>half)){return;//如果加号或减号的个数大于符号三角形中总符号数的一半则退出函数}if(t>n)//符号填充完毕{nsum++;//打印符号for(inti=1;i<=n;i++)//第i行{for(intk=i;k>=0;k--)

7、//先输出必要的空格{cout<<'';}for(intj=1;j<=n-i+1;j++)//输出符号三角形第i行第i-1+k个位置{if(p[i][j]==0)//如果该位为0,输出“+”{cout<<"+";}else{if(p[i][j]==1)//如果该位为1,输出“-”{cout<<"-";}}}cout<

8、定，对应三角形的该斜行可以确定{p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];//通过异或运算下行符号count+=p[j][t-j+1];//减号数}Backtrack(t+1);//对第一行的第t+1个位置进行回溯算法for(j=2;j<=t;j++)//回溯，减去该斜行的减号数{count-=p[j][t-j+1];}count-=i;//减去第一行第t个位置的减号数}}intComputer(intn)//友元函数调用Triangle类的成员函数{TriangleX;X.n=n;X.count=0;X

9、.sum=0;X.half=n*(n+1)/2;if(X.half%2==1){return0;//如果是一个三角形符号的总数是奇数则不符合条件，返回0}X.half=X.half/2;int**p=newint*[n+1];//分配新行for(inti=0;i<=n;i++)p[i]=newint[n+1];//分配新列for(i=0;i<=n;i++)for(intj=0;j<=n;j++)p[i][j]=0;//给p所指向的二维数组赋值为0X.p=p;X.Backtrack(1);returnX.sum;}voidmain(){intn

10、;//第一行的符号数cout<<"请输入第一行符号个数"<>n;intsum=Computer(n);cout<