tutor 板


LINE

※ 引述《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







like.gif 您可能会有兴趣的文章
icon.png[问题/行为] 猫晚上进房间会不会有憋尿问题
icon.pngRe: [闲聊] 选了错误的女孩成为魔法少女 XDDDDDDDDDD
icon.png[正妹] 瑞典 一张
icon.png[心得] EMS高领长版毛衣.墨小楼MC1002
icon.png[分享] 丹龙隔热纸GE55+33+22
icon.png[问题] 清洗洗衣机
icon.png[寻物] 窗台下的空间
icon.png[闲聊] 双极の女神1 木魔爵
icon.png[售车] 新竹 1997 march 1297cc 白色 四门
icon.png[讨论] 能从照片感受到摄影者心情吗
icon.png[狂贺] 贺贺贺贺 贺!岛村卯月!总选举NO.1
icon.png[难过] 羡慕白皮肤的女生
icon.png阅读文章
icon.png[黑特]
icon.png[问题] SBK S1安装於安全帽位置
icon.png[分享] 旧woo100绝版开箱!!
icon.pngRe: [无言] 关於小包卫生纸
icon.png[开箱] E5-2683V3 RX480Strix 快睿C1 简单测试
icon.png[心得] 苍の海贼龙 地狱 执行者16PT
icon.png[售车] 1999年Virage iO 1.8EXi
icon.png[心得] 挑战33 LV10 狮子座pt solo
icon.png[闲聊] 手把手教你不被桶之新手主购教学
icon.png[分享] Civic Type R 量产版官方照无预警流出
icon.png[售车] Golf 4 2.0 银色 自排
icon.png[出售] Graco提篮汽座(有底座)2000元诚可议
icon.png[问题] 请问补牙材质掉了还能再补吗?(台中半年内
icon.png[问题] 44th 单曲 生写竟然都给重复的啊啊!
icon.png[心得] 华南红卡/icash 核卡
icon.png[问题] 拔牙矫正这样正常吗
icon.png[赠送] 老莫高业 初业 102年版
icon.png[情报] 三大行动支付 本季掀战火
icon.png[宝宝] 博客来Amos水蜡笔5/1特价五折
icon.pngRe: [心得] 新鲜人一些面试分享
icon.png[心得] 苍の海贼龙 地狱 麒麟25PT
icon.pngRe: [闲聊] (君の名は。雷慎入) 君名二创漫画翻译
icon.pngRe: [闲聊] OGN中场影片:失踪人口局 (英文字幕)
icon.png[问题] 台湾大哥大4G讯号差
icon.png[出售] [全国]全新千寻侘草LED灯, 水草

请输入看板名称,例如:BabyMother 或 站内搜寻

TOP