作者Peter1986110 (Self-reference)
看板tutor
标题Re: [解题] GrayChu 板友的题目
时间Wed May 5 17:04:19 2010
※ 引述《TOOYA (在草地等流星)》之铭言:
: ※ 引述《vvbird (vv)》之铭言:
: : 用 A、B、C、D、E、F 六个字母形成一个 9 个字母的单字
: : 至少出现一组三个连续字母 BAD 的机率为何?
: :(恕删)
: -----------------------------------------------------------------------
: 刚想了一下 这里的排容又跟之前的不是完全一样 这里没有三个圈圈(AUBUC之类)
: 我在这里解释一下
: ┌───┬───┬───┬───┬───┐
: │ │ 没有 │ 恰一 │ 恰二 │ 恰三 │
: ├───┼───┼───┼───┼───┤
: │ 任意 │ ˇ│ ˇ│ ˇ│ ˇ│
: ├───┼───┼───┼───┼───┤
: │ 一组 │ │ ˇ│ ˇˇ│ˇˇˇ│
: ├───┼───┼───┼───┼───┤
: │ 二组 │ │ │ ˇ│ˇˇˇ│
: ├───┼───┼───┼───┼───┤
: │ 三组 │ │ │ │ ˇ│
: ├───┼───┼───┼───┼───┤
: │ +-+- │ ˇ│ │ │ │
: └───┴───┴───┴───┴───┘
: ˇ个数表在这个计算[N组(以上)]下,恰N被算到的次数
: 一组的情形 有 B A D _ _ _ _ _ _
: _ _ _ B A D _ _ _
: 它将恰二中的 B A D B A D C E F 计算了两次 所以在一组x恰二的空格记作ˇˇ
: 一组的情形 有 B A D _ _ _ _ _ _
: _ _ _ B A D _ _ _
: _ _ _ _ _ _ B A D
: 它将恰三中的 B A D B A D B A D计算了三次 所以在一组x恰三的空格记作ˇˇˇ
: 其他就类推吧
所以用万用暴力讨论法(笑)时,倒着想比较快
Note That: 恰Ni组 与 恰Nj组 在 i=\=j 时为 互斥事件,故计算完洽N组可直接加总不
用考虑
恰三组 BADBADBAD → 一种
恰两组 BAD---BAD (类数)*{(所有排法)-(此位子下出现恰三组)}
BADBAD--- 共三类 → 3 * ( 6*6*6 - 1 )= 645
---BADBAD
BAD-BAD--
--BAD-BAD
BAD--BAD- (类数)*{(所有排法)-(此位子下出现恰三组(不可能))}
-BAD--BAD 共七类 → 7 * ( 6*6*6 - 0 )= 1512
-BADBAD--
--BADBAD-
-BAD-BAD-
(用3H3=10知恰两组共十类BAD分配法)
恰一组 BAD------ (类数)*{(ALL)-(此位子恰两组(对照上面)-(三组) )
------BAD 此两类 → 2 * (6^6 - (2*(6^3)+2*(6^3-1)) - 1)= 91586
-BAD-----
-----BAD- 此两类 → 2 * (6^6 - (3*(6^3)) - 0)= 92016
--BAD----
----BAD-- 此两类 → 2 * (6^6 - (2*(6^3)) - 0)= 92448
---BAD--- 此一类 → 1 * (6^6 - (2*(6^3-1)) - 1)= 46225
(2H6=7没有其他类)
Total= 324433 (订正之前计算错误)
324433
P=Total/6^9= -------- ~= 0.0321932 = 3.21932%
10077696
其实暴力法没我想像的慢......
以上,有问题请不吝指教。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.166.198.243
※ 编辑: Peter1986110 来自: 218.166.198.243 (05/05 17:16)
1F:推 TOOYA:BADBADBAD在任意算1次 一组算3次 二组算3次 三组算1次 05/05 17:46
2F:→ TOOYA:+-+-之後刚好扣光了啊?? 看不是很懂错在哪里@@ 05/05 17:47
抱歉!是我想错了,T大的算是对的!已删掉错误想法,另外之前计算错误,更正後机率一样
注:T大算式小改:(2H6)*6^6 - (3H3)*6^3 + 1 = 324433
(其实除了7跟10可以用H来算不用慢慢穷举以外没变)
※ 编辑: Peter1986110 来自: 218.166.198.243 (05/06 00:53)
3F:推 TOOYA:我不要小改 我喜欢穷举XDDD 这种小东西穷举才是王道 05/06 11:16
4F:→ TOOYA:以不变应万变 真的大(麻烦)的东西再发展一套想法就好了 05/06 11:17
5F:→ Peter1986110:我用nHm目的也只是要验算也没有举错而已 05/06 12:26
6F:→ Peter1986110:当然,我个人倾向要穷举就从头到尾穷举 05/06 12:27
7F:→ Peter1986110:要用想的就从头到尾用想的,像这题既然都想的到用排容 05/06 12:29
8F:→ Peter1986110:以学生的能力想不到用H来算是有点奇怪,当然假如是自 05/06 12:30
9F:→ Peter1986110:己上课我会顺便会提nHm的,毕竟比教有教学意义 05/06 12:31
10F:→ Peter1986110:而且nHm可以回学生问:你保证你举完了吗?的问题 05/06 12:33
11F:推 TOOYA:不是想得到想不到的问题 像这麽小的东西 数一数就完了 05/06 16:30
12F:→ TOOYA:而且说实在的 我不知道也不想理解H怎麽来的 05/06 16:32
13F:→ TOOYA:如果今天一个特别的算法可以解决复杂的计算 我会说它好 05/06 16:32
14F:→ TOOYA:但是 它处理的东西这麽单纯 又何必要多教一个增加负担的东西 05/06 16:33
15F:推 TOOYA:像是#1Br-1O6O 透过这样一个转换可以简化题目到这种地步 05/06 16:39
16F:→ TOOYA:我会觉得这个想法很好 但像是拘泥在要写4C2还是4!/(2!2!) 05/06 16:40
17F:→ TOOYA:我就觉得有点无聊了 05/06 16:40
无聊?我的确是无聊到想要一般化这个问题才搬出H:
排n个,有m种,给定完全不自重复字串k个字(之所以说不自重复像规定这种字串:BADBA因
为字串有自重复会导致BADBA---在填BAD就算重复两次),问至少出现一次之机率
用排容&手算只能做到:
(手数)m^(n-k)-(手数)*m^(n-2k)+(手数)*m^(n-2k)-...+......../m^n
不手算而用 H or C or whatever 公式算出几组特殊字串排法种类数 就很清楚是:
(2H(n-k))m^(n-k)-(3H(n-2k))*m^(n-2k)+.../m^n
其中第t项为: (-1)^(t+1)*[(t+1)H(n-tk)]*m^(n-tk)
尾项之t为 t=t0 s.t. n-tk<k
i.e. 通式为:(n=字串长,m=字种类,k=特定不自重复字串长)
t
P(至少出现一次字串)=[Σ (-1)^(i+1)*[(i+1)H(n-ik)]*m^(n-ik)]/m^n
i=1
其中 t=min[{t|n-tk<k,t属於自然数}]
18F:推 phxcon:你算错了。BAD的中间还是可以放ABD, 三个字母 05/06 21:35
对不起,我不太懂ph大的意思,可否详述之?
※ 编辑: Peter1986110 来自: 218.166.192.105 (05/07 23:14)
19F:推 TOOYA:复杂的地方暴力 简单的地方刁别人的算式 实在看不出高明在哪 05/08 21:06
20F:→ TOOYA:一开始指正我的算式错 後来确认是自己错又要嫌我的算式麻烦 05/08 21:09
21F:→ TOOYA:难道不值得无聊两个字吗?? 我好话说尽了 本来想笑笑带过 05/08 21:10
22F:→ TOOYA:如果手算都不敢相信自己没算错 学生又怎麽相信nHm没想错?? 05/08 21:12
23F:→ TOOYA:更何况你连暴力也暴错 05/08 21:12
我那个时候赶出门随便算算你也要鞭......
我暴力算并非我的本意,但是想算算看暴力算法在可用计算机的情况下有多难算才算的
24F:推 TOOYA:排容加手算"只能得到"正确的答案 暴力+过度延伸能得到什麽? 05/08 21:36
老实说,我只是想要讨论这个问题而已,因为我对这个问题的一般化有兴趣,T大之前所言
亦让我受惠良多,但我不懂得T大为何要如此恶言相向?假如你觉得我的用语让你情感上有
不悦之处,那我道歉,假如我在学问上有所不足,那还请你多多指教
但假如你质疑我nHm的用法有错,请证明我下面的论述是错误的,毕竟数学的方法要用数学
解决:
Q:对一个特定字串长k,重复取m种字排n长度字串,在特定字串长k重复t次的种类数
pf:
考虑 特定字串 特定字串 .....t个特定字串(共kt个字已填)
^ ^ ^ t+1个可填其他字的位置
剩下n-kt字可以填在这t+1个位置
即为特定字串视为符号A(t个),其他字元视为符号B(n-kt个)之直线排列
故有(t+n-kt)!/t!(n-kt)!种可能,亦等於(t+1)H(n-kt)种可能 //
-----
我的确很无聊,我现在在思考的是不考虑回文视为同字串情况下,有哪些情况会导致那个
一般式挂掉?(虽然我知道T大对我的公式存疑,但在我自己实验下我还看不到反例,同时我
也还看不出我的证明那里有问题),以及所有会让我的一般式挂掉的状况是否亦有自己的一
般解,现在已知指定一自重复(如AA、BABA)、或部分自重复字串(如BAB、BACB)会出事,想
找一般解中......
※ 编辑: Peter1986110 来自: 61.231.24.163 (05/09 13:37)
25F:推 TOOYA:我一开始也已经好言相告 不希望你修改我的东西 在我认为那是 05/09 18:36
26F:推 TOOYA:没有必要的前提之下 第二段我也说明了我之所以认为没必要的 05/09 18:38
27F:→ TOOYA:原因 这一题真的有必要做这样的延伸?? 即使有请你自己写一个 05/09 18:39
28F:→ TOOYA:方法 因为在我认为没有必要的情况 你执意要修改我的东西 我 05/09 18:39
29F:→ TOOYA:认为你没有尊重别人的东西 所以我也不想再顾虑你的感受了 05/09 18:41
30F:→ TOOYA:我说过 在这一题我根本不想用H去做这种小东西 所以你写的那 05/09 18:42
31F:→ TOOYA:一整段我根本连看都没看 我也不会去找你哪里有错 你如果想找 05/09 18:43
32F:→ TOOYA:人跟你讨论你有兴趣的主题 或许重发一篇文章会有更多回响 05/09 18:44
33F:→ TOOYA:我有空我也会去跟你讨论 但是在这一题 我认为"没必要" 05/09 18:45
34F:→ TOOYA: ^又有兴趣的话 05/09 18:56