首页 > 代码库 > 华为OJ训练 之 括号配对数目问题

华为OJ训练 之 括号配对数目问题

题目如下

括号配对问题

输入n个括号,输出能组合的n个括号组合,例如——

输入1时,只有()一种;

输入2时,有()()和(())两种;

输入3时,有()()(),()(()),(())(),(()())和((())),共5种。

输入4时有14种。。依次类推。


我想到的笨方法,类推找规律,因为我相信这个肯定有个公式的。找了好一会。没总结出来,于是翻书,因为印象中看过类似的题。

然后找到了公式。哈哈。


import java.util.Scanner;  

public class Main {  
  
    public static void main(String[] args) {  
  
        Scanner scanner = new Scanner(System.in);  
        int n = scanner.nextInt();  
        scanner.close();  
        if (n == 0) {
        	System.out.println(0);
	}else{
		  System.out.println((int) (jiecheng(2 * n) / (jiecheng(n) * jiecheng(n) * (n + 1))));  
	}
      
    }  
  
    private static long jiecheng(int n) {  
        long result = 1;  
        for (int i = 1; i <= n; i++) {  
            result *= i;  
        }  
        return result;  
    }  
}