CSDN
CSDN社区
专题开发/技术/项目
数据结构与算法
超超版主的问题:
如果有n对括号,组成一个式子,而且括号的最深嵌套层次为k
满足这个条件的式子一共有几种?
如果n=3,k=2则有3种:
(())()
()(())
(()())
能否找到递推公式?
------------------------------------------------------------------------------------------
tailzhou 网友的解答:
对于特定的 n,k;
深度为k的子式子最少有k个括号,最多有n个括号
对由i(i >=k and i <=n)个括号组成的深度为k的式子可以由dp数组得到;
其他的n-i个括号分布在深度为k的子式子的前后;
为了不重复统计,规定上面深度为k的子式子是 大式子中的第一个深度为k的子式子;
分别对前面有j(j >=0,j <=n-i,并且这k个括号组成的式子的最大深度不能大于k-1,也就是最大深度从1到k-1的总数的和)个括号,后面有n-i-j(并且这n-i-j个括号组成的式子的最大深度不能大于k)个括号的情况统计;
#include <stdio.h >
#define MAX_N 20
int dp[MAX_N+1][MAX_N+1];
void fun(int n,int k)
{
int i,j;
for (i=k;i <n;++i)
{
int tmp=0;
for (j=0;j <=n-i;++j)
{
int tmp_i=j;
int tmp_j=n-i-j;
int tmp_k1=0,tmp_k2=0;
if (tmp_i >k-1) tmp_i=k-1;
if (tmp_j >k) tmp_j=k;
for (;tmp_i >0 ; tmp_i--)
{
tmp_k1+=dp[j][tmp_i];
}
for (;tmp_j >0 ; tmp_j--)
{
tmp_k2+=dp[n-i-j][tmp_j] ;
}
if (tmp_k1 <1) tmp_k1=1;
if (tmp_k2 <1) tmp_k2=1;
tmp+=tmp_k1*tmp_k2;
}
dp[n][k]+=dp[i-1][k-1]*tmp;
}
dp[n][k]+=dp[n-1][k-1];
}
int main(int argc, char* argv[])
{
//最深嵌套层次为k,那么肯定存在一个层次为k-1的式子,其外围再有一对括号;
//这对括号外再没有嵌套的括号;
int n,k;
for (n=1; n <=MAX_N; n++)
{
dp[n][1]=1;
dp[n][n]=1;
}
for (n=1; n <=MAX_N; n++)
{
for (k=1; k <=n; k++)
{
if (k!=n && k!=1) fun(n,k);
printf("n:%3d k:%3d dp:%10d\n",n,k,dp[n][k]);
}
}
fun(20,2);
printf("input n{max:%d} and k{max:%d}:",MAX_N,MAX_N);
while (scanf("%d %d",&n,&k)==2)
{
printf("%d %d : %d \n" ,n,k,dp[n][k]);
printf("input n{max:%d} and k{max:%d}:",MAX_N,MAX_N);
}
return 0;
}
顺手将其改写成VB代码,如下所示:
Sub fun(ByVal n As Long, ByVal k As Long, ByRef dp())
Dim i As Long, j As Long, temp As Long, temp_i As Long, temp_j As Long, temp_k1 As Long, temp_k2 As Long
For i = k To n - 1
temp = 0
For j = 0 To n - i
temp_i = j
temp_j = n - i - j
temp_k1 = 0
temp_k2 = 0
If temp_i > k - 1 Then temp_i = k - 1
If temp_j > k Then temp_j = k
While temp_i > 0
temp_k1 = temp_k1 + dp(j, temp_i)
temp_i = temp_i - 1
Wend
While temp_j > 0
temp_k2 = temp_k2 + dp(n - i - j, temp_j)
temp_j = temp_j - 1
Wend
If temp_k1 < 1 Then temp_k1 = 1
If temp_k2 < 1 Then temp_k2 = 1
temp = temp + temp_k1 * temp_k2
Next
dp(n, k) = dp(n, k) + dp(i - 1, k - 1) * temp
Next
dp(n, k) = dp(n, k) + dp(n - 1, k - 1)
End Sub
Sub main()
Dim n As Long, k As Long, max_n As Long
max_n = 23
ReDim dp(1 To max_n, 1 To max_n)
For n = 1 To max_n
dp(n, 1) = 1
dp(n, n) = 1
Next
For n = 1 To max_n
For k = 1 To n
If k > 1 And k < n Then fun n, k, dp
Next
Next
[a1].Resize(max_n, max_n) = dp
[a1].Resize(max_n, max_n).Columns.AutoFit
End Sub
在EXCEL中返回:
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
3 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
7 |
5 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
15 |
18 |
7 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
31 |
57 |
33 |
9 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
63 |
169 |
132 |
52 |
11 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
127 |
482 |
484 |
247 |
75 |
13 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
255 |
1341 |
1684 |
1053 |
410 |
102 |
15 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
511 |
3669 |
5661 |
4199 |
1975 |
629 |
133 |
17 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1023 |
9922 |
|
分享到:
相关推荐
Response-for-Brackets, 用于中括号的响应式设计工具 如何安装括号响应黑括号不再需要 hack 括号了从扩展管理器安装扩展打开扩展管理器查找"。括号响应- 原始"扩展并安装它手动安装扩展选择 help> 显示扩展...
利用栈编写满足下列要求的括号匹配检验程序:假设表达式中允许包含两种括号:圆括号和方括号,其嵌套的顺序随意,即([]())或[([][])]等为正确的格式,[(]或([())或(()])均为不正确的格式。输入一个包含上述括号的...
假设一个算术表达式中可以包含三种括号:园括号“(”和“)”、方括号“[”和“]”、花括号“{”和“}”,且这三种括号可按任意的次序嵌套使用。编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已...
2. 令所给的式子中出现()[ ]{ }这几种括号形式。 3. 所给的参考代码是用C实现的,要求(1)用C++实现;(2)改进教材P95程序3.7,可以判断所给的式子出现()[ ]{ }这几种括号。测试的表达式expression要在主控main...
某个序列完全由圆括号组成,一个“(”和“)”称为一对括号,且序列中的括号成对出现。设n为序列中出现的括号对数,k为序列中括号的最大嵌套深度;那么,序列“((()()()))()(())”的n为8,k为3,请...
假设一个算术表达式中包括圆括号、方括号和花括号三种形式的括号,判别表达式中括号是否正确配对。 对于输入的表达式,输出以下四种结果之一: 1、左右括号匹配正确 2、左右括号配对次序不正确; 3、右括号多于左...
假设一个算术表达式中包含圆括号、方括号两种类型的括号,试编写一个判断表达式中括号是否匹配的程序,匹配返回Match succeed!,否则返回Match false!。 例 [1+2*(3+4*(5+6))]括号匹配 (1+2)*(1+2*[(1+2)+3)...
给定一个字符串,其中的字符只包含三种括号:花括号{ }、中括号[ ]、圆括号( ),即它仅由 “( ) [ ] { }” 这六个字符组成。设计算法,判断该字符串是否有效,即字符串中括号是否匹配。括号匹配要求括号必须以正确的...
1 假设一个算术表达式中可以包含三种括号:圆括号“(”和“)”、方括号“[”和“]”和花括号“{”和“}”,且这三种括号可按任意的次序嵌套使用,利用栈的基本运算,设计程序,判断给定的表达式中所含括号是否正确...
假设在表达式中允许有三种括号:圆括号、方括号和花括号,其嵌套的顺序是随意。要求设计测试数据,如果在表达式中括号使用正确,输出结果为“此表达式中括号匹配合法”,否则输出结果为“此表达式中括号匹配不合法”...
(1)、括号匹配的算法设计 利用一个栈结构保存每个出现的左括号,当遇到右括号时,从栈中弹出左括号,检验匹配情况。在检验过程中,若遇到以下几种情况之一,就可以得出括号不匹配的结论。 (1)当遇到某一个右括号...
目前的工作需要写大量的、很长的、内含很多括号的表达式,需要一个括号匹配检测工具,于是就自己做了一个,也发上来分享一下。 使用说明: 1.将要检查的表达式复制到“请将要检查的表达式复制到该文件.txt”文件内...
括号匹配
举几个例子如下: 例如对于"( ()",最长的有效的括号中的子字符串是"()" ,有效双括号数1个,故它的长度为 2。 再比如对于字符串") () () )",其中最长的有效的括号中的子字符串是"() ()",有效双括号数2个,故它的...
利用栈实现括号匹配的检验,存储括号字符的数组通过malloc实现动态分配长度,匹配函数的第一个参数为指向字符的指针(即为存储括号字符的数组的首地址)和一个整数(即为括号字符的总数,为括号个数的2倍),将左...
2、假设一个算术表达式中可以包含三种括号:园括号“(”和“)”、方括号“[”和“]”、花括号“{”和“}”,且这三种括号可按任意的次序嵌套使用。编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式...
C++实现,识别依次读入的一个以@`...圆括号"("和")"、方括号"["和"]"和花括号"{"和"}",且这三种括号可按任意的次序嵌套 使用如:…[…{…}…[…]…]…[…]…(…)…)。判别给定表达式所含括号是否正确配对出现的算法
缺少左括号 缺少右括号 括号数目相等但不匹配 等等 用栈实现
括号嵌套问题(非括号匹配),输入括号序列,求出嵌套深度和括号对数
顺序栈实现括号配对