符号三角形问题（Java）

1、 前置介绍

符号三角形定义

如下图所示，符号三角形是由14个“+” 号和14个"-"号组成的符号三角形。两个同号下面都是“+” 号， 两个异号下面都是”-“。

在一般情况下， 符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n, 计算有多少
个不同的符号三角形，使其所含的"+ “和” - "的个数相同。

2、算法设计

对于符号三角形问题，用n元组X[l:n]表示符号三角形的第一行的n个符号。

当x[i]=1时，表示符号三角形的第一行的第t个符号为“+” ；当x[i]=0时，表示符号三角形的第一行的第t个号为"-"。

由于x[i]是2值的， 所以在用回溯法解符号三角形问题时，可以用一棵完全二叉树来表示其解空间。

在符号三角形的第一行的前i个符号x[1:i]确定后， 就确定了一个由i*(i + 1)/2个符号组成的符号三角形。下一步确定x[i+l]的值后，只要在前面已确定的符号三角形的右边加一条边， 就可以扩展为x[1:i+l] 所相应的符号三角形。最终由x[l:n]所确定的符号三角形中包含的“+”个数与"-"个数同为n*(n+l)/4。

• 可行性约束条件

因此在回溯搜索过程中可用当前符号三角形所包含的“+”个数与"-"个数均不超过n*(n+l)/4 作为可行性约束， 用于剪去不满足约束的子树。

对于给定的n, 当n*(n+l)/2 为奇数时， 显然不存在所包含的“+” 个数与"-"个数相同的符号三角形。这种情况可以通过简单的判断加以处理。

3、程序代码

说明：

• backtrack(level)：搜索解空间中第level层子树

• 主类的数据成员记录解空间中结点信息，以减少传给backtrack 的参数。

• sum：记录当前已找到的“+”个数与"-"个数相同的符号三角形数。

• 在算法backtrack中， 当i>n时，算法搜索至叶结点， 得到一个新的"+“个数与”-"个数相同的符号三角形，当前已找到符号三角形数sum增l 。

• 当i<=n时， 当前扩展结点Z是解空间中的内部结点。该结点有x[i]=1 和x[i]=0共两个儿子结点。对当前扩展结点Z的每一个儿子结点， 计算其相应的符号三角形中“+”个数count与"-"个数，并以深度优先的方式递归地对可行子树搜索， 或剪去不可行子树。

public class Solution {

    static int n;           // 第一行符号个数
    static int half;        // n * (n+1) / 4        "+"/"-"符号个数
    static int count;       // 当前"+"个数
    static int[][] p;       // 符号三角形矩阵
    static long sum;        // 已找到的符号三角形数量

    public static void main(String[] args) {
        n = 4;
//        n = 7;
        count = 0;
        sum = 0;
        half = n * (n + 1) / 2;     // 先初始化为符号三角形中的符号总个数

        p = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                p[i][j] = 0;
            }
        }

        System.out.println("不同的符号三角形分别为：");
        compute(n);
        System.out.println("首行" + n + "个符号且符合题目要求的一共有" + sum + "种不同的符号三角形");
//        System.out.println("这" + sum + "种不同的符号三角形分别为：");

    }

    public static long compute(int firstCnt) {
        if (half % 2 == 1) {    // 符号总个数为奇数 不可能出现“+”、“-”个数相等的情况
            return 0;
        }
        half /= 2;             // 符号总个数为偶数   将 half设置为“+”(“-”)的个数
        backtrack(1);
        return sum;
    }

    private static void backtrack(int t) {
        // 当前“+”或者“-”符号个数已经达到n * (n + 1) / 4
        if ((count > half) || (t * (t - 1) / 2 - count > half)) {
            return;
        }
        // TODO 已经构造出一个符合要求的符号三角形，数量加1
        if (t > n) {
            sum++;
            // 打印符号三角形
            for (int i = 1; i <= n; i++) {
                for (int k = 1; k < i; k++) {
                    System.out.print(" ");
                }
                for (int j = 1; j <= n; j++) {
                    if (p[i][j] == 0 && j <= n - i + 1) {
                        System.out.print("+" + " ");
                    } else if (p[i][j] == 1 && j <= n - i + 1) {
                        System.out.print("-" + " ");
                    } else {
                        System.out.print("  ");
                    }
                }
                System.out.println();
            }
            System.out.println("----------------------------------");
        } else {
            // “+”、“-”用 0、1 代替（构造完全二叉树）
            for (int i = 0; i < 2; i++) {
                p[1][t] = i;
                count += i;
                // 上一行种只有大于等于2个符号才可以形成其下一行的一个符号
                for (int j = 2; j <= t; j++) {
                    // TODO 通过异或的方式求其余行数的放置方式
                    p[j][t - j + 1] = p[j - 1][t - j + 1] ^ p[j - 1][t - j + 2];
                    count += p[j][t - j + 1];
                }
                backtrack(t + 1);
                for (int j = 2; j <= t; j++) {
                    count -= p[j][t - j + 1];
                }
                count -= i;
            }
        }
    }
}

运行结果

4、算法效率

计算可行性约束需要O(n)时间，在最坏情况下有0(2ⁿ)个结点需要计算可行性约束，故解符号三角形问题的回溯算法backtrack所需的计算时间为O(n*2ⁿ)。

5、参考资料

• 算法设计与分析（第四版）

结束！