作者sooge (喜欢平井桃)
看板Grad-ProbAsk
标题[理工] 离散 递回
时间Fri Nov 16 23:31:21 2018
https://i.imgur.com/NpPFg6V.jpg
我要问第7题 我想了好久了
很疑惑普通的解法要怎麽去慢慢推
因为答案这种方法很像就只适用於连续数字不超过两个的问题
像是两个连续1这种
但刚刚想了一下 ，一旦题目说包含3个以上连续1 我就又不知道怎麽处理了....
我不是看不懂解答 解答的我会
但我不知道不用这种方法要怎麽推出来
简单来说就是我推到这里我就推不下去了
https://i.imgur.com/KZa8BWh.jpg
因为会牵扯到1和2，我不知道该怎麽推後面的
麻烦各位强者帮我解惑了
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 120.105.145.182
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1542382283.A.BB5.html
※ 编辑: sooge (120.105.145.184), 11/16/2018 23:35:49
2F：→ JKLee: 以上提供包含3个连续字元的解法 11/17 09:39
4F：→ JKLee: 以上是3个连续1的解法 11/17 10:04
5F：→ JKLee: 变化: 求长度n且不含12与21的三元字串总数 11/17 10:09
6F：→ sooge: 请问第一张图case2里*2是什麽意思？ X不是都有3种了为什麽 11/17 10:37
7F：→ sooge: 不是*3 所以那个*2并不是代表X是00,11,22三种可能的意思？ 11/17 10:37
8F：推 JKLee: 第一张图 case 2 11/17 10:44
9F：→ JKLee: 因 Y != X, 所以: 11/17 10:44
10F：→ JKLee: 当 Y = 1, X = 2 or 3; 11/17 10:44
11F：→ JKLee: 当 Y = 2, X = 1 or 3; 11/17 10:44
12F：→ JKLee: 当 Y = 3, X = 1 or 2. 11/17 10:44
13F：→ JKLee: Y决定好之後, X就剩2种可能. 11/17 10:44
14F：→ JKLee: sorry,我写错. 请忽略case2与3写的3种. 11/17 10:53
15F：→ sooge: 为什麽递回里可以把Y固定住 感觉怪怪的 Y固定住的情况下X是 11/17 11:19
16F：→ sooge: 两种没错 但把Y固定住那其他Y的值不用考虑吗？如果是case2 11/17 11:19
17F：→ sooge: 是*2不是*3不就代表Y只有考虑到1种数字(ex.1) 那2和3怎麽 11/17 11:19
18F：→ sooge: 办？ 11/17 11:19
19F：推 JKLee: 我不是很了解你卡在什麽地方. 11/17 11:59
20F：→ JKLee: 我再重新描述一次我的作法. 11/17 11:59
21F：→ JKLee: 见第一张图 case 2 11/17 11:59
22F：→ JKLee: 长度n的字串， 11/17 11:59
23F：→ JKLee: 切成长度n-2的字串 string 1 与长度2的字串 string 2. 11/17 11:59
24F：→ JKLee: string 1 是合法的，总共a_(n-2)种. 11/17 11:59
25F：→ JKLee: string 2 是由2个相同字元构成. 11/17 11:59
26F：→ JKLee: 我希望 string 1 後面接上的 string 2 11/17 11:59
27F：→ JKLee: 不可以与 string 1 的结尾相同. 11/17 11:59
28F：→ JKLee: 所以 string 1 接上 string 2 的方法数总共是 11/17 11:59
29F：→ JKLee: a_(n-2) * 2 11/17 11:59
30F：推 JKLee: 我举另外一个例子: 11/17 12:47
31F：→ JKLee: 有5种不同的球,取2颗作排列, 且2颗球不可相同. 11/17 12:47
32F：→ JKLee: 共有5*4种可能. 11/17 12:47
33F：→ JKLee: 第1个颗球有5种选择. 11/17 12:47
34F：→ JKLee: 第2颗球剩4种选择. 11/17 12:47
35F：推 JKLee: 感谢版友来信勘误, 红圈处应为 2*W_(n-3). 11/17 12:50
37F：→ JKLee: 後面的过程也要跟着改 11/17 12:51
38F：→ sooge: 不知道为什麽你说成string我就懂了 谢谢你！！解释的超级 11/17 13:17
39F：→ sooge: 详细 11/17 13:17