符号三角形_hdu_2510(深搜).java
http://acm.hdu.edu.cn/showproblem.php?pid=2510
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 729 Accepted Submission(s): 361


Problem Description
符号三角形的 第1行有n个由“+”和”-“组成的符号 ，以后每行符号比上行少1个，2个同号下面是”+“，2个异 号下面是”-“ 。计算有多少个不同的符号三角形，使其所含”+“ 和”-“ 的个数相同 。 n=7时的1个符号三角形如下:
+ + - + - + +
+ - - - - +
- + + + -
- + + -
- + -
- -
+


Input
每行1个正整数n <=24,n=0退出.


Output
n和符号三角形的个数.


Sample Input
15
16
19
20
0


Sample Output
15 1896
16 5160
19 32757

20 59984

*import java.util.Scanner;public class Main{//打表static int n,sum;public static void main(String[] args) {Scanner input=new Scanner(System.in);for(n=1;n<25;n++){sum=0;String b=new String("");dfs(0,b);System.out.print(sum+",");}}private static void dfs(int id, String b) {if(id==n){//System.out.println(b);jc(b);return;}dfs(id+1,b+"+");dfs(id+1,b+"-");}private static void jc(String str) {char s[]=str.toCharArray();long a1=0,a2=0;for(int i=0;i<s.length;i++){if(s[i]=='+')a1++;else a2++;}for(int i=1;i<=n-1;i++){for(int j=1;j<=n-i;j++){if(s[j-1]==s[j]){a1++;s[j-1]='+';}else{a2++;s[j-1]='-';}}}if(a1==a2){//System.out.println("&&&&"+str);sum++;}}}