学步园

#include <iostream><br /> using namespace std;</p> <p>class Triangle<br /> {<br /> private:<br /> int num;//第一行的符号数量<br /> int **p;//存储+ -号，0表示-，1表示+<br /> int count;//记录+号数量,根据+号数量，可以用i*(i+1)/2-count求出减号数量<br /> int sum;//记录+与-数量相等且等于num*(num+1)/4的情况<br /> const int half;//加号=等号=总符号数/2<br /> public:<br /> //构造函数<br /> Triangle(int num):half(num*(num+1)/4)<br /> {<br /> this->num=num;<br /> count=0;<br /> sum=0;</p> <p> p=new int* [num+1];<br /> for(int i=0;i<=num;i++)<br /> {<br /> p[i]=new int[num+1];//开辟一个num*num的矩阵，用于在回溯过程中记录三角形符号分布<br /> }<br /> }<br /> //调用回溯<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>，并且先判断num*(num+1)/2是否为奇数<br /> void triangleSolve()<br /> {<br /> if(num*(num+1)/2%2==0)<br /> {<br /> triangle(1);<br /> display();<br /> }<br /> else<br /> {<br /> cout<<"不存在可能性"<<endl;<br /> return;<br /> }<br /> }<br /> //回溯核心算法<br /> void triangle(int i)<br /> {<br /> if(i>num)<br /> {<br /> ++sum;<br /> return;<br /> }</p> <p> for(int j=0;j<=1;j++)<br /> {<br /> p[1][i]=j;<br /> count+=j;<br /> for(int k=2;k<=i;k++)<br /> {<br /> p[k][i-k+1]=p[k-1][i-k+1]^p[k-1][i-k+2];//相同则为1，不同则为0，代表题目的规则.1为+，0为-<br /> count+=p[k][i-k+1];<br /> }<br /> if(count<=half&&i*(i+1)/2-count<=half)//剪枝函数，约束函数，如果当前的+，-都小于符号数一半，那么继续递归<br /> {<br /> triangle(i+1);<br /> }<br /> //恢复现场<br /> for(int k=2;k<=i;k++)<br /> {<br /> count-=p[k][i-k+1];//减去新加入右侧边的+符号数量<br /> }<br /> count-=j;//减去i位置的+数量<br /> }<br /> }<br /> void display()<br /> {<br /> cout<<"边长为"<<num<<"的情况下，一共有"<<sum<<"种符号三角形具有同等数量的+与-号"<<endl;<br /> }<br /> };</p> <p>void main()<br /> {<br /> Triangle test(7);//设置第一行有7个符号<br /> test.triangleSolve();//解决问题<br /> }

求+，-数量相等的三角形数量，整个三角形只与第一行的符号有关。

所以可以逐次安排第一行的每一个符号，由于每次安排好一个符号，那么就会在原确定的三角形最右侧加一条三角形边。 所以，利用回溯法，逐次对第一行每一个位置的符号做出选择，并且扩充新的三角形边。 为了实现回溯算法的优化，必须有剪枝函数，所以这里用+，-都小于总符号数的一半作为约束，只要能够递归到第n+1个字符，说明1到n个字符的安排都满足+<=half,-<=half，所以就是+与-数量相等，sum++。  为了在回溯过程中能够及时的计算出三角形的最新状况，所以设置了二维数组用于存储三角形，根据图形的关系可以求出三角形的右侧边加入到二维数组中。