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