符号三角形问题 回溯法
运用回溯法解题通常包含以下步骤：
（1）、针对所给问题，定义问题的解空间；
（2）、确定易于搜索的解空间结构(如子集树、排列数或图）；
（3）、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数（如约束函数、限界函数）避免无效搜索。
（4）、由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法。
对于符号三角形问题，用n元组x[1：n]表示符号三角形的第一行的n个符号。当x[i]=1时，表示符号三角形的第一行的第i个符号为“+”号；当x[i]=0时，表示符号三角形的第一行的第i个符号为“-”号；1 ≤ i≤ n。 由于x[i]是二值的，所以在用回溯法解...全部
运用回溯法解题通常包含以下步骤：
（1）、针对所给问题，定义问题的解空间；
（2）、确定易于搜索的解空间结构(如子集树、排列数或图）；
（3）、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数（如约束函数、限界函数）避免无效搜索。
（4）、由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法。
对于符号三角形问题，用n元组x[1：n]表示符号三角形的第一行的n个符号。当x[i]=1时，表示符号三角形的第一行的第i个符号为“+”号；当x[i]=0时，表示符号三角形的第一行的第i个符号为“-”号；1 ≤ i≤ 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为奇数时，显然不存在所包含的“+”号个数与“-”号个数相同的符号三角形。
以上就是解析过程，若要程序代码，需要提高悬赏分喔，嘿嘿~
。收起
