推 hcsoso :) 用心推! 01/10 02:37
推 xdd1524 :感謝! 01/10 08:25
※ 引述《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)