内容发布更新时间 : 2024/5/24 13:55:12星期一 下面是文章的全部内容请认真阅读。

符号三角形问题

一、算法及基本思想

1、问题描述：

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

例如下图：由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。

2、基本思想

+ + - + - + +

+ - - - - + - + + + - - + + - - + - - - +

符号三角形问题用n元组x[1:n]表示符号三角形的第一行的n个符号。X[i]=1表示第一行第i个符号为“+”， X[i]=0表示第一行第i个符号为“-”；1<=i<=n 。 由于x[i]是2值的，所以在用回溯法解符号三角形问题时，可以用完全二叉树来表示其解空间。可行性约束函数：当前符号三角形所包含的“+”个数与“-”个数均不超过n*(n+1)/4 。

在算法中递归方法backtrack(1)实现对整个解空间的回溯搜索。backtrack(i)搜索整个解空间中第i层子树。类Triangles的数据成员记录解空间中节点信息，以减少传给backtrack的参数。Sum记录当前已找到的“+”的个数与“—”个数相同的符号三角形数。

在算法backtrack中，当i>n时，算法搜索至叶节点，得到一个新的“+”个数与“—”个数相同的符号三角形，当前已找到的符号三角形数sum增1.

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

1

子树搜索，或减去不可行子树。

无解的判断：n*(n+1)/2为奇数 。

n=3时的符号三角形用完全二叉树表示的解空间。

3、复杂度分析

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

二、程序源代码

import javax.swing.*; public class Triangles {

public static void main(String []args)

{

// Create application frame.

//TrianglesFrame frame = new TrianglesFrame();

String s1=JOptionPane.showInputDialog(null,\输入第一行的符号个数\, \

符号三角形问题\,JOptionPane.QUESTION_MESSAGE);

}

int n=Integer.parseInt(s1); long sum = compute(n);

static int n; static int half;

2

static int count ; static int [][]p; static long sum;

public static long compute(int nn) {

n=nn; count=0; sum=0; half=n*(n+1)/2; if(half%2==1)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 printTriangles() {

int m=n;

System.out.println(m--); for(int i = 1;i <= n;i++) {

for(int k = 1;k < i;k++)

System.out.print(\);

//

for(int j = 1;j <= m;j++) {

if(p[i][j] == 1)

System.out.print(\);

else if(p[i][j] == 0)

3