内容发布更新时间 : 2024/12/27 11:07:42星期一 下面是文章的全部内容请认真阅读。
由于算法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. { 38. sum++; 39. } 40. else 41. { 42. for (int i=0;i<2;i++) 43. { 44. p[1][t]=i;//第一行符号 45. count+=i;//当前\号个数 46. 47. for(int j=2;j<=t;j++) 48. { 49. p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2]; 50. count+=p[j][t-j+1]; 51. } 52. Backtrack(t+1); 53. for (int j=2;j<=t;j++) 54. { 55. count-=p[j][t-j+1]; 56. } 57. count-=i; 58. } 59. } 60. } 61. 62. int Compute(int n) 63. { 64. Triangle X; 65. X.n=n; 66. X.count=0; 67. X.sum=0; 68. 69. X.half=n*(n+1)/2; 70. if(X.half%2==1)return 0; 71. X.half=X.half/2; 72. 73. int**p=new int*[n+1]; 74. 75. for(int i=0;i<=n;i++) 76. { 77. p[i]=new int[n+1]; 78. } 79. 80. for(int i=0;i<=n;i++) 81. { 82. for(int j=0;j<=n;j++) 83. { 84. p[i][j]=0; 85. } 86. } 87. 88. X.p=p; 89. X.Backtrack(1); 90. for(int i=0;i<=n;i++) 91. { 92. delete []p[i]; 93. } 94. delete []p; 95. p=0; 96. return X.sum; 97. } 计算可行性约束需要O(n)时间，在最坏情况下有 O(2^n)个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为 O(n2^n)。程序运行结果如图：