内容发布更新时间 : 2024/11/16 20:22:08星期一 下面是文章的全部内容请认真阅读。

由于算法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 3. using namespace std; 4.

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)。程序运行结果如图：