Re: [理工] [離散]用生成函數解遞迴

看板Grad-ProbAsk作者pikachu123 (pika)時間14年前 (2012/01/07 20:21)推噓1(1推 0噓 5→)

留言6則, 2人參與討論串3/3 (看更多)

2 1 6x+6x _______ + _____________ A(x)= 1-2x (1-2x)(1-x)^3 解到這可以用部分分式去做令右邊那個為f(x)= a b c d ______ + _______+_______ +_______ 1-2x (1-x)^3 (1-x)^2 (1-x) 通分一下 a(1-x)^3+b(1-2x)+c(1-2x)(1-x)+d(1-2x)(1-x)^2 6x^2+6x ______________________________________________ =______________ (1-2x)(1-x)^3 (1-2x)(1-x)^3 x=1/2帶入解得a=36 x=1帶入解得b=-12 x=0帶入 ==>a+b+c+d=6 x=2帶入 ==>-a-3b+3c-3d=36 把a,b帶入解c,d 得c=-6,d=-18 1 36 -12 -6 -18 ______ + ______ + _______ + _______ + ________ 所以A(x)= (1-2x) (1-2x) (1-x)^3 (1-x)^2 (1-x) 剩下的就代公式去算 GF解遞迴比較麻煩通常都是部分分式不然其實也是蠻快的 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.162.155.113 ※ 編輯: pikachu123 來自: 1.162.155.113 (01/07 20:23)

推

justbelieve

01/07 20:46, , 1^F

01/07 20:46, 1^F

→

justbelieve

01/07 20:46, , 2^F

01/07 20:46, 2^F

→

pikachu123

01/07 20:51, , 3^F

01/07 20:51, 3^F