Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: [合集]也许可以换一个思路(about括号问题）
发信站: 哈工大紫丁香 (2002年08月28日17:28:10 星期三), 站内信件


────────────────────────────────────────
 parser (行路难，多歧路)              于 Wed Aug 21 17:07:09 2002) 说道:

there are 13 men,3 of them must be father,10 of them can not be father  .
How many familytrees can we draw?


────────────────────────────────────────
 sino (茶水)                          于 2002年08月21日20:04:07 星期三 说道:

有帮助吗？

────────────────────────────────────────
 parser (行路难，多歧路)              于 Wed Aug 21 21:55:13 2002) 说道:

好像是没啥用处，too simple,hoho.
but i have another idea:
退一步，不考虑一对括号阔一个字符的情况。
m个字符，i对括号。
首先用i对括号阔i+1个字符。这是一个Catalan数，已有定论。
然后把其余的字符丢到2i+1个空个当中。





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

强！
可是丢空的方案需要讨论吧，怎么做呢？

────────────────────────────────────────
 parser (行路难，多歧路)              于 Wed Aug 21 22:26:00 2002) 说道:

yes,需要讨论:i个相同的球丢到j个不同的桶中有多少可能。



────────────────────────────────────────
 sino (茶水)                          于 2002年08月22日13:36:16 星期四 说道:

有所不同，这里的剩余数字不是随便捡出来的

────────────────────────────────────────
 parser (行路难，多歧路)              于 Thu Aug 22 14:22:17 2002) 说道:

相同，我们不指定是哪一个数字，只是一个占位符号。比如首先阔aaaa,然后再丢六个a.
完事之后，从左到右依次把a换成0-9。



────────────────────────────────────────
 parser (行路难，多歧路)              于 Thu Aug 22 14:23:53 2002) 说道:

在0123456789之间插入3对括号，有多少种可能。
在aaaaaaaaaa之间插入3对括号，有多少种可能。
是一个问题。




────────────────────────────────────────
 Lerry (想不开·撞树)                 于 2002年08月22日14:47:01 星期四 说道:

呵呵，争论了这么久，你的答案是多少呢？
首先保证结果的正确性，才能讨论他的方法是对是错啊

────────────────────────────────────────
 parser (行路难，多歧路)              于 Thu Aug 22 14:54:00 2002) 说道:

俺还没有算呢，只是线讨论一下，hoho.

────────────────────────────────────────
 sino (茶水)                          于 2002年08月22日17:43:37 星期四 说道:

这个我再考虑一下，感觉你说的是对的
昨天你说（n字符,n-1括号）是Catalan数，这好像有点问题，
pn除了p1*pn-1+...pn-1*p1之外，还有一些其它的情况，
比如((aa))(aa) --> (((aa)))(aa)这种第n-1层括号不是
括在整个式子上的情况

────────────────────────────────────────
 sino (茶水)                          于 2002年08月22日17:47:21 星期四 说道:

ft.建议你把你的思路和已有的结果一次说清，方便
大家讨论

────────────────────────────────────────
 sino (茶水)                          于 2002年08月22日17:51:55 星期四 说道:

BTW:往里丢计算起来还是挺方便的

────────────────────────────────────────
 parser (行路难，多歧路)              于 Thu Aug 22 17:53:12 2002) 说道:


是有问题。
那就再退一步，不考虑括号位置从复的情况。
事实上，((aa))(aa) --> (((aa)))(aa) 是2个括号，4个数字的问题。




────────────────────────────────────────
 parser (行路难，多歧路)              于 Thu Aug 22 17:59:31 2002) 说道:

能解决，不过我的方法很不利索。
下一步，我们应该讨论如何取消一个括号不能仅仅阔一个字符的限制。




────────────────────────────────────────
 sino (茶水)                          于 2002年08月22日18:01:42 星期四 说道:

你最终想得到什么样的结果？我已经有点糊涂了的说 ~

────────────────────────────────────────
 sino (茶水)                          于 2002年08月22日18:05:14 星期四 说道:

母函数，是吧
不很明白..是不是跟你具体的使用环境有关..

────────────────────────────────────────
 parser (行路难，多歧路)              于 Thu Aug 22 18:08:09 2002) 说道:

 至少有一个括号在最外层，不加任何其它限制。



────────────────────────────────────────
 parser (行路难，多歧路)              于 Thu Aug 22 18:11:39 2002) 说道:




────────────────────────────────────────
 sino (茶水)                          于 2002年08月23日20:22:11 星期五 说道:

这个排列组合怎么做？谢谢

────────────────────────────────────────
 parser (行路难，多歧路)              于 Fri Aug 23 21:05:04 2002) 说道:

事实上，有了SoonFaye的解法，以足够了。
 【 在 sino (茶水) 的大作中提到: 】
//比如5个球丢到10个桶里，总共分五大类：
只有1个桶有球p(10,1)*C(4,0)
只有2个桶有球p(10,2)*C(4,1)
只有3个桶有球p(10,3)*C(4,2)
只有4个桶有球p(10,4)*C(4,3)
只有5个桶有球p(10,5)*C(4,4)
p:排列
c:组合



────────────────────────────────────────
 sino (茶水)                          于 2002年08月23日21:07:33 星期五 说道:

你说的对，是我想多了，3x ~

────────────────────────────────────────
--
※ 修改:·Lerry 於 08月28日17:33:22 修改本文·[FROM: 218.7.33.123]