大家好，我叫亓官劼（qí guān jié ），在CSDN中记录学习的点滴历程，时光荏苒，未来可期，加油~博客地址为：亓官劼的博客，亓官劼的博客2。
 
 
 
第十一届 蓝桥杯 省 模拟赛 完整题目+题解地址为：第十一届 蓝桥杯 省 模拟赛 试题+题解
 
 
题目
 
问题描述
 
由1对括号，可以组成一种合法括号序列：()。
 　　由2对括号，可以组成两种合法括号序列：()()、(())。
 　　由4对括号组成的合法括号序列一共有多少种？
 
答案提交
 
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
 
题解
 
​ 这是一个填空题，只需要填写答案即可。这里深度为1的序列有一种为：()()()(),深度为2的有7种:(())()()、()(())()、()()(())、(()()())、(()())()、()(()())、(())(()),深度为3的有5种：((()))()、()((()))、((())())、(()(()))、((()())),深度为4的有1种:(((())))，所以答案为14。
 
答案为14

思路：
  括号匹配可以直接用栈匹配，这里使用递归，主要递归方式为
 
首先全部左括号，任何对数括号都会有这种形式
 
(((())))
 
由于左括号放在最前面的方式，只有这一种排列，所以需要回退，把第四个左括号先不匹配，那么左括号就会出现在右括号后面，这时候再递归，就会产生几种新的排列
 
((()()))
((())())
((()))()
 
依次这样进行下去，直到放在最左边的左括号只有1个，这是最后一种，所有对数都会有这种形式
 
()()()()
 
其实就是模拟一个栈的回退过程，栈和递归是可以互换的
 
代码：(C++)
 
#include<iostream>

using namespace std;

//括号的对数，放在这里避免递归存放太多参数
int size;  
/*
	left：左括号使用个数
	right：右括号使用个数
	result：拼接的字符串
*/
void place(int left, int right,string result)
{
	//退出条件,左括号大于最大，或者右括号大于左括号
	if(left > size || right > left)
		return;
	//打印条件
	if(left == size && right == size)
	{
		cout<<result<<endl;
	}
	else
	{
		//左括号小于最大值，还可以加
		if(left < size)
		{
			result += "(";
			place(left+1,right,result);
			//由于用的是字符串，当递归返回时，得把之前的为下一层添加的符号去掉
			result = result.substr(0,result.size()-1);
		}
		//右括号小于左括号数，还可以加
		if(right < left)
		{
			result += ")";
			place(left,right+1,result);
			//由于用的是字符串，当递归返回时，得把之前的为下一层添加的符号去掉
			result = result.substr(0,result.size()-1);
		}
	}
}

int main()
{
	cin>>size;
	place(0,0,"");
}
 
结果：
 

 
合法括号序列
 
题目
答案
题解
手算
代码
 

 
题目
 
问题描述
 由1对括号，可以组成一种合法括号序列：()。
 由2对括号，可以组成两种合法括号序列：()()、(())。
 由4对括号组成的合法括号序列一共有多少种？
 
答案提交
 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
 
答案
 
14
 
题解
 
手算
 
这是一个填空题，只需要填写答案即可。
 这里深度为1的序列有一种为：()()()(),
 深度为2的有7种:(())()()、()(())()、()()(())、(()()())、(()())()、()(()())、(())(()),
 深度为3的有5种：((()))()、()((()))、((())())、(()(()))、((()())),
 深度为4的有1种:(((())))，
 所以答案为14。
 
代码
 
public class LegalBrackets {
    public static int count = 0, n = 4;
    public static void main(String[] args) {
        f(0, 0);
        System.out.println(count);
    }

    public static void f(int left, int right) {
        if (left == n) {
            count++;
            return;
        }

        f(left + 1, right);
        if (left > right) {
            f(left, right + 1);
        }
    }
}

 
文章目录
 
题目
解题思路
解法一
解法二
 

 
题目
 
【（本科组）第十一届蓝桥杯省模拟赛】
 
由1对括号，可以组成一种合法括号序列：()。
由2对括号，可以组成两种合法括号序列：()()、(())。
由4对括号组成的合法括号序列一共有多少种？
 
解题思路
 
首先这是一道典型的括号匹配问题
 
解法一
 
关于括号匹配问题 —> 可以运用 卡特兰数（入栈顺序解法之一）
递推公式 h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
 
解法二
 
运用 递归
 
右括号的数量不能超过左括号
函数的两个参数分别为 左右括号数
 
初始一开始 左右括号为 0
 
package SimulationGame12;

public class bracket {
	
	public static int count=0,n=4;
	public static void main(String[] args) {
		f(0,0);
		System.out.println(count);
	}
	public static void f(int left,int right){
		if(left==n  ){
			
			count++;  // 有多种正确的匹配形式
			return;
		}
		
		f(left+1,right);
		if(left>right){
			f(left,right+1);
		}
	}
}

 
 
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()