※ 引述《xdd1524 (...)》之铭言： : 1.a(n)为长度n的2进位串个数, : 且各串"无连续的1"且第一个位置跟最後一个位置都不是1 : 求一个递回关系给a(n) : 2.a(n)为长度n的3进位串个数 : 各串不含连续的1也不含连续的2 : 求一个递回关系给a(n) : 该如何讨论各种情况? : 原本列出a(1),a(2)...来看规律 : 第一题比较简单还看出是a(n)=a(n-1)+a(n-2) : 第二题就看不出来. 第一题的看法其实类似这样: 由最後面(或者最前面也可以)的一位跟两位来判断 因为最後一位不为1 =>必为0 那麽a(n)一定有一部分的解可表示成前n-1位为 a(n-1) 最後一位摆0 但又最後a(n-1)的最後面必不为1 所以还要考虑最後两位为10的状况 所以就是前n-2位摆a(n-2) 最後两位摆10 虽然这边不会讨论到最後三位110的状况 但因为所求不能有连续1 所以讨论到这边就可以了 这就是为何a(n) = a(n-1) + a(n-2) 同样的道理 第二小题 从字串尾部来判断可以变成类似这样: a(n-1) 0 a(n-2) 01 a(n-2) 02 a(n-3) 021 a(n-3) 012 . . . a(0)012......1212121 a(0)021......2121212 212......1212121 121......2121212 =>递回式: a(n) = a(n-1)+2*[a(n-2)+a(n-3)+...+a(0)+1] 其中a(0)代表字串长度为0 => a(0) = 1 a(1) = a(0) + 2*[1] = 3 a(2) = a(1)+2*[a(0)+1] = 7 ... 如果是要求出a(n)... 好像不太好求XDDDDD --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.113.139.83 ※ 编辑: jameschou 来自: 140.113.139.83 (01/09 23:56) 刚刚我想说来把a(n)求出来好了 所以开始假设.. a(n) = a(n-1)+2*[a(n-2)+a(n-3)+...+a(0)+1] ^ ^ | | | 设系数为t(0) 设系数为s(0) = ... = s(n-1)a(0) + t(n-1)*[1] = s(n-1) + t(n-1) 又s跟t的递回关系如下: s(n) = s(n-1)+t(n-1) ... (1) t(n) = 2s(n-1) + t(n-1) ... (2) s(0)=1 , s(1)=3 , s(2)=7 , s(3)=17 ... t(0)=2 , t(1)=4 , t(2)=10, t(3)=24 ... (1) => t(n-1) = s(n) - s(n-1) => t(n) = s(n+1) - s(n) ... (3) 代入(2) => s(n+1) - s(n) = 2s(n-1) + s(n) - s(n-1) => s(n+1) = 2s(n) + s(n-1) 特徵多项式 x^2 - 2x -1 = 0 => x = 1±√2 n n 令s(n) = c (1+√2) + c (1-√2) 0 1 代入s(0),s(1) => c + c = 1 , 1 + √2(c -c )=3 0 1 0 1 1+√2 1-√2 => c = ------- , c = ------- 0 2 1 2 n+1 n+1 => s(n) = (1/2)(1+√2) + (1/2)(1-√2) 将s(n)代回 (3) n+1 n+1 => t(n) = (1/√2)(1+√2) - (1/√2)(1-√2) 所以a(n) = s(n-1) + t(n-1) n n n n = (1/2)(1+√2) + (1/2)(1-√2) +(1/√2)(1+√2) - (1/√2)(1-√2) n+1 n+1 = (1/2)(1+√2) + (1/2)(1-√2) ..................................竟然跟s(n)一样 a(n)求出来竟然等於s(n) 那就表示递回式为a(n) = 2a(n-1) + a(n-2) 所以以上当作发疯好了= =... 重新看到这个式子: a(n) = a(n-1)+2*[a(n-2)+a(n-3)+...+a(0)+1] ......(1) => a(n-1) = a(n-2)+2*[a(n-3)+a(n-4)+...+a(0)+1] ......(2) 把(2)左式跟右式顺序对调然後跟(1)相加=> a(n)+a(n-2)+2*[a(n-3)+...+a(0)+1] = 2a(n-1)+2*[a(n-2)+a(n-3)...+a(0)+1] => a(n) + a(n-2) = 2a(n-1) + 2*a(n-2) => a(n) = 2a(n-1) + a(n-2) 其实这样就可以求出a漂亮的递回式了.. 然後解这个递回式用前面求s的方法就好 因为同一个递回式= =... n+1 n+1 总之, a(n) = (1/2)(1+√2) + (1/2)(1-√2) ※ 编辑: jameschou 来自: 140.113.139.83 (01/10 02:21)