精华区文章阅读

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: [合集]请教一个问题（在0123456789之间插入3对括�...
发信站: 哈工大紫丁香 (2002年08月21日15:18:06 星期三), 站内信件

────────────────────────────────────────
parser (行路难，多歧路)              于 Tue Aug 20 17:07:10 2002) 说道:

在0123456789之间插入3对括号，有多少种可能。
当然，括号可以潜套，不可以交叉。
请高人指点，谢谢！

────────────────────────────────────────
parser (行路难，多歧路)              于 Tue Aug 20 17:18:03 2002) 说道:

允许。
比如((0(12)3)456789)是一种可能的情况。

────────────────────────────────────────
SoonFaye (宠辱偕忘)                  于 2002年08月20日17:18:07 星期二说道:

梅对括号间必须有数字？

────────────────────────────────────────
parser (行路难，多歧路)              于 Tue Aug 20 17:19:38 2002) 说道:

yes,必须有

────────────────────────────────────────
sino (茶水)                          于 2002年08月20日18:06:43 星期二说道:

你有正确答案吗？

────────────────────────────────────────
sino (茶水)                          于 2002年08月20日18:24:19 星期二说道:

15730,对不对呀？

────────────────────────────────────────
parser (行路难，多歧路)              于 Tue Aug 20 21:13:36 2002) 说道:

俺也不知道答案，所以才请教大家。
不过我觉得给出一个通式才好，比如n个字符中插入i对括号（i<=n-1）

────────────────────────────────────────
sino (茶水)                          于 2002年08月20日21:30:51 星期二说道:

你这是分析词法还是句法用的，hoho ~

────────────────────────────────────────
sino (茶水)                          于 2002年08月20日21:36:44 星期二说道:

估计很难，不知道有没有成熟的理论

────────────────────────────────────────
parser (行路难，多歧路)              于 Tue Aug 20 21:37:00 2002) 说道:

真是高人，用于句法。

────────────────────────────────────────
sino (茶水)                          于 2002年08月20日21:37:46 星期二说道:

//blush 俺只是接触过一点点而已 ..

────────────────────────────────────────
SoonFaye (宠辱偕忘)                  于 2002年08月21日12:09:42 星期三说道:

对于在N个单元中插入M对括号的问题
俺认为可以用递规穷举的方法解决
递归入口：
   n个单元（已经有0个()。）
   第K对括号。
递归方法：
   穷举出n+(n-1)+...+1种方法（双循环即可完成）
    每种方法将现有n个单元分成3块。...(...)...
    每一块成为新的递归入口
    返回条件：K=M
配合全局计数器即可得出方案总数。

────────────────────────────────────────
sino (茶水)                          于 2002年08月21日12:19:12 星期三说道:

有重复，因为后括号')'是就近匹配的

────────────────────────────────────────
SoonFaye (宠辱偕忘)                  于 2002年08月21日13:37:23 星期三说道:

                ~~~~~~~~~~~不会出现重复的。

────────────────────────────────────────
sino (茶水)                          于 2002年08月21日13:39:10 星期三说道:

        ~~~~~~~~~~~上边是不是已经有K-1对括号？

────────────────────────────────────────
SoonFaye (宠辱偕忘)                  于 2002年08月21日13:44:44 星期三说道:

这是递归入口，K值仅用于递归结束条件之一
每次递归都在新的（没有()的序列）上进行。

────────────────────────────────────────
sino (茶水)                          于 2002年08月21日13:51:49 星期三说道:

比如
在 ......(......)...... 的第一块上加一组括号 ..(..)..(......)......
和在..(..)..............的第三块上加一组括号 ..(..)..(......)......
就是重复阿
我还是不太理解的说 ~

────────────────────────────────────────
SoonFaye (宠辱偕忘)                  于 2002年08月21日13:57:42 星期三说道:

您说得对，是重复了，我还得仔细想想~
谢谢！！

────────────────────────────────────────
sino (茶水)                          于 2002年08月21日14:03:55 星期三说道:

您太客气了，欢迎讨论的说 ~

────────────────────────────────────────

Algorithm 版 (精华区)