试题详情
简答题 下图是由14个“+”和14个“－”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“－”。 在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“－”的个数相同。请针对符号三角形问题设计一个尽可能高效的算法。
  • 回溯法实现
    对于符号三角形问题，用n元组x[1：n]表示符号三角形的第一行的n个符号。当x=1时，表示符号三角形的第一行的第i个符号为“+”号；当x=0时，表示符号三角形的第一行的第i个符号为“-”号；1≤i≤n。由于x是二值的，所以在用回溯法解符号三角形问题时，可以用一棵完全二叉树来表示其解空间。在符号三角形的第一行的前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为奇数时，显然不存在所包含的“+”号个数与“-”号个数相同的符号三角形。
    复杂度分析
    计算可行性约束需要O（n）时间，在最坏情况下有O（2n）个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为O（n2n）。

  • 关注下方微信公众号，在线模考后查看

热门试题