一、问题描述
下图所示的三角形中，有14个“+“和14个“-”。2个同号下面是+，两个异号下面是-。 在一般情况下，符号三角形的第一行有n个符号。符号三角形问题，要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”相同。
二、算法分析
用n元组x[1:n]表示符号三角形的第一行的n个符号，当x[i]等于1时，表示符号三角形的第一行的第i个符号为“+”;当x[i]等于0时，表示符号三角形的第一行的第i个符号为“-”；1<=i<=n。由于x[i]是2值的。所以在用回溯法解符号三角形问题时，可以用一棵完全二叉树来表示其解空间。在符号三角形的第一行的前i个符号x[1:i]确定后，就确定了一个有i*(i+1)/2个符号组成的符号三角形。
（i*(i+1)/2来自首项为1、公差为1的等差数列的求和公式）
下一步确定x[i+1]的值后，只要在前面已确定的符号三角形的右边加一条边，就可以拓展为x[1:i+1]所对应的符号三角形。最终由x[1:n]所确定的符号三角形包含的“+”个数与“-”同为n(n+1)/4（n(n+1)/2的一半，也就是一半的符号）。因此，在回溯可将“+”、“-”个数均 不超过n(n+1)/4为约束条件。同时，对于给定的n当n(n+1)/2为奇数时，显然不存在“+”和“-”个数相同的符号三角形。
这里举一个第1行是4个字符的符号三角形的子集树
对于这道题只要确定第1行的n个符号其实最后画出的符号三角形一定是唯一的，在求第1行n个符号的时，每次确定一个符号时，由该字符与之前已有的字符能组合出一个符号三角形，该符号三角形为最终要求的符号三角形的子集，新确定的符号可以作为右边如图红色箭头那样，将路径上的符号得到。
import java.io.*;
import java.util.*;
public class Triangles {
public static int n, half, count;// 第一行的符号个数n，当前“+”个数count，
public static int[][] p;// 符号三角形矩阵
public static long sum;// 符合条件的符号三角形个数
public static long computs(int nn) {
n = nn;
count = 0;
sum = 0;
half = n * (n + 1) / 2;
if (half % 2 == 1)// 无解的判断：n*(n+1)/2为奇数
{
return 0;
}
half = half / 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;
}
}
backtrack(1);
return sum;
}
public static void backtrack(int t) {
if ((count > half) || (t * (t - 1) / 2 - count > half))
return;// 若符号统计未超过半数，并且另一种符号也未超过半数
if (t > n) {
sum++;
} // 当i>n时，算法搜索至叶节点，得到一个新的“+”个数与“—”个数相同的符号三角形，当前已找到的符号三角形数sum增1.
else {
for (int i = 0; i < 2; i++) {
p[1][t] = i;
count += i;
for (int j = 2; j <= t; j++) {
if (p[j - 1][t - j + 1] == p[j - 1][t - j + 2]) {
p[j][t - j + 1] = 1;
// 2个同号下面都是“+”
}
else {
p[j][t - j + 1] = 0;
// 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;
}
}
}
public static void main(String[] args) {
System.out.println("请输入第一行符号值：");
Scanner read = new Scanner(System.in);
int n = read.nextInt();
System.out.println("个数：" + computs(n));
}
}
三、算法效率
参考链接
发表评论