求助1个递推式

troy

如何推出An的表达式！其中，k是常数！

mathe

所有这些线性递推式都可以用特征方程的方法来解通项，比如这里特征方程为
$x^5-k_1x^4-k_2x^3-k_3x^2-k_4x-k_5=0$
如果特征方程没有重根，如http://bbs.emath.ac.cn/viewthrea ... ;fromuid=20#pid2858，我们可以将通项写成：
$A_k=a_1 x_1^k+a_2 x_2^k +... +a_5 x_5^k$的形式。

troy

原帖由 mathe 于 2008-9-30 09:47 发表
所有这些线性递推式都可以用特征方程的方法来解通项，比如这里特征方程为
$x^5-k_1x^4-k_2x^3-k_3x^2-k_4x-k_5=0$
如果特征方程没有重根，如http://bbs.emath.ac.cn/viewthrea ... &fromuid=20#pid ...

这是1个5次方程，不知道如何用计算机求解。会给定ki的值，刚我描述有所错误。ki也是变量。它不是一成不变的。

仙剑魔

这不是今天的ACM题目么...
这个世界上有个东西名叫矩阵...
以下内容等14:00过后补充...

仙剑魔

过了14:00,可以公布答案了
|  0   1   0    0    0|  |Ai-5|   |Ai-4|
|  0   0   1    0    0|  |Ai-4|   |Ai-3|
|  0   0   0    1    0|*|Ai-3|=|Ai-2|
|  0   0   0    0    1|  |Ai-2|   |Ai-1|
|k1 k2 k3 k4 k5|  |Ai-1|   |Ai    |
也就是说后一组数据可以由前一组左乘一个方阵F得到
从A0到Ai要左乘F共i次,即F^i
求F^i存在2分快速算法,问题解决

gxqcn

$[(A_i), (A_{i-1}), (A_{i-2}), (A_{i-3}), (A_{i-4})] = [(k_1, k_2, k_3, k_4, k_5), (1,0,0,0,0), (0,1,0,0,0), (0,0,1,0,0), (0,0,0,1,0)] xx [(A_{i-1}), (A_{i-2}), (A_{i-3}), (A_{i-4}), (A_{i-5})] = [(k_1, k_2, k_3, k_4, k_5), (1,0,0,0,0), (0,1,0,0,0), (0,0,1,0,0), (0,0,0,1,0)]^{i-4} xx [(A_4), (A_3), (A_2), (A_1), (A_0)]$

用上式计算更简单（可以免除一次矩阵除法运算）。

gxqcn

对不起，之前看错了，
我楼上的方法与5# 仙剑魔的描述是一致的。
（注意：5# 的 k1～k5 顺序颠倒了）

无心人

GxQ回来了啊
回家的感觉很好吧

可惜俺们这种在本地工作的人是再也体会不到了
呵呵

大学时，
回家永远很急切
在家永远很短暂
返程永远很无奈

gxqcn

早上到的。
跟儿子挤在一个铺位，经历一夜的颠簸，所以上午睡了一觉。
小家伙倒是劲头十足，真后悔今天没把他送到幼儿园。

外地工作很累的，牵挂家中父老，也很难尽孝道。

无心人

不错啊
可以休息一天啊