用C语言及递归分治法写一个程序：n对括号有多少种匹配方式

以下是用C语言及递归分治法实现n对括号匹配的程序：

#include <stdio.h>

// 递归函数，求解n对括号的匹配方式
int count(int n) {
    // 如果n为0，则括号已经匹配完毕，返回1
    if (n == 0) {
        return 1;
    }
    
    int i, j, res = 0;
    // 枚举左右括号的数量
    for (i = 0, j = n - 1; i < n; i++, j--) {
        res += count(i) * count(j);
    }
    
    return res;
}

int main() {
    int n;
    printf("请输入括号对数：");
    scanf("%d", &n);
    printf("%d对括号有%d种匹配方式。\n", n, count(n));
    return 0;
}

程序中的count函数采用递归分治法，枚举左右括号的数量，然后计算左右括号的匹配方式数相乘，最终返回所有情况的总和。程序运行时，先输入括号对数，然后输出匹配方式数。

相关问题

用C语言及递归分治法写一个程序：n对括号有多少种匹配方式并给出相应的字符串

以下是基于C语言及递归分治法的程序，可以求解n对括号的匹配方式，并输出所有匹配的字符串：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void generateParenthesis(int n, int left, int right, char *str, int index);

int main()
{
    int n;
    printf("Enter the number of pairs of parentheses: ");
    scanf("%d", &n);
    char *str = (char *)malloc(sizeof(char) * (2 * n + 1));
    str[2 * n] = '\0';
    generateParenthesis(n, 0, 0, str, 0);
    free(str);
    return 0;
}

void generateParenthesis(int n, int left, int right, char *str, int index)
{
    if (left == n && right == n) {
        printf("%s\n", str);
        return;
    }
    if (left < n) {
        str[index] = '(';
        generateParenthesis(n, left + 1, right, str, index + 1);
    }
    if (right < left) {
        str[index] = ')';
        generateParenthesis(n, left, right + 1, str, index + 1);
    }
}

程序中使用 generateParenthesis 函数递归生成括号匹配字符串。该函数的参数包括：

- n：括号对数
- left：当前已经添加的左括号数量
- right：当前已经添加的右括号数量
- str：存储括号匹配字符串的缓冲区
- index：当前缓冲区的下标

递归的终止条件是 left 和 right 都等于 n，此时就可以输出匹配的字符串。否则，如果 left 小于 n，就在缓冲区中添加一个左括号，并递归调用 generateParenthesis 函数。如果 right 小于 left，就在缓冲区中添加一个右括号，并递归调用 generateParenthesis 函数。

运行程序，输入 n=3，输出如下：

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

n对括号有多少种匹配方式分治法求解该问题的思路

对于给定的n对括号，我们可以使用分治法来求解其匹配方式的数量。

首先，考虑最外层的一对括号，它要么与最后一个右括号匹配，要么与中间的某个左括号匹配。因此，我们可以将问题分成两个子问题：

1. 在n-1对括号中，有多少种匹配方式。
2. 在n-1对括号中，最外层的左括号与哪个右括号匹配。

对于第一个子问题，我们可以使用递归来求解。对于第二个子问题，我们需要考虑所有左括号与右括号的匹配方式，然后将它们的数量相加即可。

具体地，我们可以使用一个for循环来枚举最外层的左括号，然后计算它与哪个右括号匹配。在计算匹配方式的数量时，我们可以将问题转化为在n-2对括号中，有多少种匹配方式的问题，然后使用递归来解决。

最后，将第一步和第二步的结果相乘即可得到n对括号的匹配方式数量。

以下是求解该问题的伪代码：

function count(n):
    if n == 0:
        return 1
    else:
        result = 0
        for i from 0 to n-1:
            result += count(i) * count(n-1-i-1)
        return result

其中，`count(n)`表示n对括号的匹配方式数量。