作者taitin (小南)
看板Grad-ProbAsk
标题Re: [理工] [离散]-解递回式的问题
时间Wed Aug 26 22:06:03 2009
回第一题
B(x)的分母先拆解
2x^2+x^3=1-2x-x^2+2x^3-(1-2x-3x^2+x^3)
=(1-2x-x^2+2x^3)/2 -(1/2-x-5/2x^2)
得b(x)=1/2+(-1/2+x+5/2x^2)/(1-2x-x^2+2x^3)
因为是B(x)拆出来的，所以跟你直接去拆一样
b0=0 n>=1的原因是因为
如果你把 n= 0 带入 bn会得到 -3/2+1/6+5/6 !=0
因此必须而外写出来 但n=1 带入bn为0 因此>=1都成立
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.230.222.74
※ 编辑: taitin 来自: 61.230.222.74 (08/26 22:07)
1F：→ taitin:下一题概念一样，为了要让式子满足boundary 08/26 22:09
2F：→ taitin:你也可以写ar=(....) r>=1 a0=0 就可以了 08/26 22:11
※ 编辑: taitin 来自: 61.230.222.74 (08/26 22:22)
3F：推 brasil:嗯嗯 boundary的部分我懂了 不过还是不太懂为什麽要拆出1/2 08/26 23:15
4F：→ brasil:这样不是比较慢吗?? 因为我看答案 1/2也不在bn里面呀.. 08/26 23:17
其实这是比较正规的做法，因为就分母来说(1-x)(1+x)(1-2x)为三次式
但是要做部分分式时，为了要比较系数，分母要二次式才行。
ex 1/(1-x) 通分时要乘上另外两个式子，因此分子最高只有二次式。
二次式再怎麽相减也减不出三次式。因此这边要先想办法消掉x^3
但其实像课本提供用带x=1 x=-1 x=1/2 等於左式带值得方法也会正确(也就是你对的原因)
可以在不提出1/2的情况下，先把後面的生成函数算出来，也就是课本71页第五行
然而这并不是正确的生成函数，必须满足在n=0时的生成条件，因此再补加1/2上去即可。
不过这算有点偷懒的作法，不晓得会不会给满分。
生成函数的意义在 X^0的系数即是b0的值，x^1的系数是b1的值
因此1/2只会影响b0的值，但却不会影响bn(n>=1)以上的值
这也是为什麽最後答案要分两段来写的详细原因
※ 编辑: taitin 来自: 61.230.222.74 (08/27 01:15)
5F：推 brasil:嗯嗯 我懂了 谢谢你的解答~ 08/27 22:31