回溯算法解决符号三角形问题

《算法分析与设计》实验报告2015-2016年第2学期实验班级：学生姓名：学号：指导老师：信息工程学院实验项目名称：回溯算法解决符号三角形问题实验日期：2016年5月25日一、实验类型：□√验证性□设计性二、实验目的掌握符号三角形问题的回溯算法；三、实验内容及要求在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。四、实验步骤#includeiostreamusingnamespacestd;typedefunsignedcharuchar;intsum;uchar**p;//符合条件的三角形计数；//表示满足要求的三角形个数charch[2]={'+','-'};intn;//第一行符号总数inthalf;intcount;//全部符号总数一半;1计数,用来计算‘-’的个数voidBackTrace(intt)//t，第一行第t个符号{if(tn){//符号填充完毕sum++;//打印符号cout第sum个三角形：endl;for(inti=1;i=n;i++){for(intj=1;ji;j++)cout;for(j=1;j=n-i+1;j++)coutch[p[i][j]];coutendl;}}else{for(inti=0;i=1;i++){p[1][t]=i;//确定第一行第t个的值；count+=i;//用来计算‘-’的个数,因为+的值是0for(intj=2;j=t;j++)//当第一行符号=2时，可以运算出下面行的某些符号，j可代表行号{p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];//第一行大于等于2时确定后面从第2行开始增加的一,为了便于运算，设+为0，-为1，这样可以使用异或运算符表示符号三角形的关系,++为+即0^0=0,--为+即1^1=0,+-为-即0^1=1,-+为-即1^0=1;通过异或运算下行符号，t-j+1确定的很巧count+=p[j][t-j+1];//列中符号，计算‘-’个数；}if(count=half&&(t*(t+1)/2-count)=half)//约束条件,若符号统计未超过半数，并且另一种符号也未超过半数，同时隐含两者必须相等才能结束{BackTrace(t+1);//在第一行增加下一个符号}for(j=2;j=t;j++)//回溯，判断另一种符号情况；{count-=p[j][t-j+1];}count-=p[1][t];}}}intmain(){cout请输入第一行符号的个数：;cinn;count=0;sum=0;half=n*(n+1)/2;if(half%2==0){/总数须为偶数，若为奇数则无解half=half/2;p=newuchar*[n+1];for(inti=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满足要求的三角形符号共有：sum个;}else{cout不存在这样的三角形符号！;}return0;}五、实验结果1、实验图形2、结果分析当输入第一行符号的个数为4时，构成的三角形中的“+”号和“-”号个数都为5个。如下图所示满足要求的三角形符号为6个。3、实验总结本次的实验中主要是让我们学会用回溯法解决问题，回溯法解决问题的时候我们首先应明确定义问题的解空间，问题的解空间至少包含问题的一个最优解，然后定义了问题的解空间后，将解空间组织起来，使得能用回溯法来方便的搜索整个解空间，通常将解空间组织成树或图的形式，最后利用回溯法，逐次对第一行每一个位置的符号做出选择，并且扩充新的三角形边。总之本次的实验我学到了很多不会的东西，但是依然有很多不明白的地方。希望自己能通过今后的学习弄懂，回溯法还是一知半解的感觉。