内容发布更新时间 : 2025/5/10 12:33:35星期一 下面是文章的全部内容请认真阅读。
由于算法Backtrack在每一个节点处耗费O(1)计算时间，故在最坏情况下，整个算法计算时间复杂性为O(n!)。程序运行结果如下：
2、符号三角形问题 (1)问题描速
下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。
在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。
(2)算法设计
解向量：用n元组x[1:n]表示符号三角形的第一行。当x[i]=1时表示符号三角形第一行的第i个符号为\；当i=0时，表示符号三角形第一行的第i个符号为\；1<=x<=n。由于x[i]是二值的，所以可以用一棵完全二叉树来表示解空间。
可行性约束函数：在符号三角形的第一行前i个符号x[1:i]确定后，就确定了一个由i(i+1)/2个符号组成的符号三角形。下一步确定x[i+1]的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为x[1:i+1]所相应的符号三角形。最终由x[1:n]所确定的符号三角形中包含\号个数与\个数同为n(n+1)/4。因此，当前符号三角形所包含的“+”个数与“-”个数均不超过n*(n+1)/4 。
无解的判断：对于给定的n，当n*(n+1)/2为奇数时，显然不存在包含的\号个数与\号个数相同的符号三角形。此时，可以通过简单的判断加以处理。
程序的具体代码如下：
[cpp] view plain copy
1. #include \ 2. #include
5. class Triangle 6. {
7. friend int Compute(int); 8. private:
9. void Backtrack(int i); 10. int n, //第一行的符号个数 11. half, //n*(n+1)/4 12. count, //当前\号个数 13. **p; //符号三角矩阵
14. long sum; //已找到的符号三角形数 15. }; 16.
17. int Compute(int n); 18.
19. int main() 20. {
21. for(int n=1;n<=10;n++) 22. {
23. cout<<\<
29. void Triangle::Backtrack(int t) 30. {
31. if ((count>half)||(t*(t-1)/2-count>half)) 32. {
33. return; 34. } 35.
36. if (t>n) 37. {