回溯法-符号三角形问题

发表于： 分类于：
字数： 2144 阅读：≈ 5分钟 浏览：

算法思想：回溯法

实际问题：符号三角形问题

编写语言：Java

问题描述

如下图是由 14 个 + 和 14 个 - 组成的符号三角形,两个同号的下面是 +，两个异号的下面是 -。

符号三角形问题描述

设符号三角形的第一行有 n 个符号，求对于给定的 n，计算有多少个不同的符号三角形，使其所包含的 + 和 - 的数量相同。

解题思路

  1. 设 + 为1，- 为 0，这样可以使用异或运算（相同为 0，不同为 1）表示符号三角形的关系：
    • “+ +” 为 +：1 ^ 1 = 0
    • “- -” 为 +：0 ^ 0 = 0
    • “+ -” 为 -：1 ^ 0 = 1
    • “- +” 为 -：0 ^ 1 = 1。
  2. 使用 x[n] 表示第一行的总共 n 个符号的取值，并且定义：
    • x[i] = 0：第一行第 i 个符号的取值为 -。
    • x[i] = 1：第一行第 i 个符号的取值为 +。
  3. 使用递归回溯，不断改变第一行的每个符号，搜索符合条件的解。
  4. 剪枝函数（剪枝操作，或者称作递归终止条件）是：当前 + 或者 - 的符号数量大于一半，或者列数达到指定上限（因为解题时是从第一列开始找，一直找到第 n 列截止）

代码解疑

此处可以跳过，直接看代码，如果有不懂的地方，可以返回来看这里。

  1. 位操作：从效率上讲，一个移位指令占2个机器周期，而乘除法指令占4个机器周期。故在做乘除法时，使用位运算有着更高的效率。在本次博文写的代码中，主要用到了两个技巧：与运算、异或运算与移位操作。

    • 与运算：与运算是一种逻辑运算技巧，它的规则是：真与真=真、假与真=假、真与假=假、假与假=假；即满足两个条件都为真时，结果才为真。在 Java 中，与运算符是 &，& 表示按位与，并且 0 表示假，1 表示真，即 1 & 1 = 1、0 & 1 = 0、1 & 0 = 0、0 & 0 = 0。若两个数相与，如 4 和 3与为 0，就可以表示为 100 & 011 = 0，在计算机中，十进制的数是用二进制表示的，如 4 在计算机中的表示是 100。如需要了解更详细的知识，请自行百度。

      扯远了，回归正题。在代码中，我们有判断一个数的奇偶性。使用了这样的技巧：n & 1，在计算机中，奇数的最低位的值必然为 1（其他高位是2的整数倍，相加必然为偶数，最低位如果是0，就无法构成奇数），而 1 是最小的奇数，除了最低位，其他位都为 0。按照与运算的规则，**任何一个数 n 与上 1，除了最低位，其他位都是 0。如果 n 为奇数，与的结果最低位为 1，结果是 1；如果 n 为偶数，与的结果最低位为 0，结果是 0。**我们因而可以形如 n & 1 的式子来判断一个数的奇偶性。

    • 异或运算：逻辑运算的一种，前面解释过，此处不讲了。

    • 移位操作：在 Java 中，移位运算符使用 »（右移）和 «（左移）表示的。如 4 右移一位，可以表示为 4 » 1，从二进制的角度将，100（4） 变成了 010（2），即缩小了一半。如果左移，则是增大一倍，在有大量乘除操作的场景中，使用移位操作可以极大的提升效率。

  2. 剪枝操作的使用位置有两处，二选一，但应注意两个位置的判断逻辑有差别。具体的代码注释中有详细说明。

  3. 根据符号三角形的构成规则，如果三角形第一行有 n 列，那么符号三角形就有 n 行，即行数和列数相等。并且相邻两行之间的列数差 1，带入等差数列的公式，可以得出符号三角形的符号总数为 n * (n + 1) / 2。

  4. 因为 + 和 - 的数量必须相等，所以符号三角形的符号数量是偶数，即 n * (n + 1) / 2 是偶数

  5. 统计完一种构造方式后，需要还原已统计符号的数量，才能进行下一次的符号三角形构造。

Java 代码 

public class SymbolicTriangleProblem {
    // 第一行的符号个数
    public static int n;
    // half 的目标数值为 (n * (n + 1) / 2) / 2，即 n * (n + 1) / 4
    public static int half;
    // 当前"-"的个数 c：count
    public static int c;
    // 符号三角形矩阵
    public static int[][] p;
    // 符号数组 s：sign
    public static String[] s = {"+", "-"};
    // 已找到的符号三角形的个数
    public static long sum;
    
    public static void main(String[] args) {
        compute(4);
        System.out.println("符合条件的符号三角形总数： " + sum);
	}
    
    /**
     * 计算指定列数下的符号三角形
     * 
     * @param col 符号三角形第一行的列数，
     *      其必须满足 (col * (col + 1) >> 1) 是偶数，
     */
    public static void compute(int col) {
        n = col;
        c = 0;
        sum = 0;
        // >> 右移一位，表示当前数除以 2
        // 当前的符号总个数，为 1 + 2 + ... + n 的数量
        half = n * (n + 1) >> 1;
        
        // 符号数量为单数，返回
        if((half & 1) == 1) {
            return;
        }
        
        half >>= 1;
        p = new int[n+1][n+1];
        
        // 从第1行的第1个列开始查找
        backtrack(1);
    }
    
    /**
     * 回溯函数
     * 
     * @param col 当前正在查找的位置：第 col 列
     */
    public static void backtrack(int col) {
        
        /**
         * 如果将剪枝操作移动到这里，总数就不能算
         * (col * (col + 1) >> 1，而应该算 (col * (col - 1) >> 1，
         * 即算少一列的情况，因为可能会出现 col > n 的情况，导致结果出错
         */
        /*
        if(c > half || ((col * (col - 1) >> 1) - c > half)) {
            return;
        } */
        
        // 当前的列数超过规定的列数
        if(col > n) {
            sum++;
            
            // 打印符号
            System.out.println("第 " + sum + " 个符号三角形：");
            for(int i = 1; i <= n; i++) {
                // 打印符号三角形中每一行开始的空白
                for(int j = 1; j < i; j++) {
                    System.out.print(" ");
                }
                
                for(int j = 1; j <= (n - i + 1); j++) {
                    System.out.print(s[p[i][j]] + " ");
                }
                
                System.out.println();
            }
            System.out.println();
        } else {
            // 将"+"设为0，"-"设为1
            for(int i = 0; i < 2; i++) {
                p[1][col] = i;
                // 统计"-"的个数
                c += i;
                
                // 判断接下来的 n - 1 行
                // 符号三角形问题中，行的总数等于列的总数
                for(int j = 2; j <= col; j++) {
                    // 通过异或运算求其余行数的放置方式
                    p[j][col - j + 1] = 
                        p[j - 1][col - j + 1] ^ p[j - 1][col - j + 2];
                        
                    c += p[j][col - j + 1];
                }
                
                // + 或者 - 的数量未超过一半
                // 此处使用 col * (col + 1) >> 1，是因为不会出现 col > n的情况
                if(c <= half && ((col * (col + 1) >> 1) - c <= half)) {
                    backtrack(col + 1);
                }
                
                // 还原 - 的数量
                for(int j = 2; j <= col; j++) {
                    c -= p[j][col - j + 1];
                }
                c -= i;               
            }
        }
    }
 }

运行结果

下图为列数为 4 的结果： 结果实例