作者stimim (qqaa)
看板Programming
标题Re: [问题] 一题演算法
时间Sun Dec 12 22:24:44 2010
※ 引述《waterboy0705 (哈罗你好吗??)》之铭言：
: 在下正在在职进修
: 这一门科目为演算法
: 教授要大家抽题目上台报告
: 我抽到了这题
: The Fibonacci polynomials are defined by the recurrence relation
: Fn(X) = X˙Fn-1(X) + Fn-2 where F0(X)=1, F1(X)=X and X>=2
^^^^ 是不是少了 (X) ?
: (不知怎麽表示下标真的很抱歉)
: How many memory spaces are actually needed to hold the
: Fibonacci polynomials F0,F1,…,F100?
: (a) below 4000
: (b) 4000~4500
: (c) 4501~5000
: (d) 5001~5500
: (e) Above5500
: 拿去跟教授讨论
: 他却说太简单了不跟我说
: 我自认上课也很认真也都有做笔记
: 但我就是不会...
: 也求助了很多朋友orz
: 说真的
: 不知道在这里发问适不适合(因为我自己根本搞不懂这是哪种问题><)
: 如果有违反板规真的很抱歉
: 如果OK的话
: 希望有高手能够给在下指点一下
: 谢谢您~~~
假设题目是 Fn(x) = x Fn-1(x) + Fn-2(x)
用 Mathematica 算算看：
In: A = {{x , 1}, {1, 0}}
In: F[n_] := Expand[Tr[MatrixPower[A, n - 1].{x, 1}.{{1}, {0}}]]
In: F[20]
Out: 1 + 55 x^2 + 495 x^4 + 1716 x^6 + 3003 x^8 + 3003 x^10 +
1820 x^12 + 680 x^14 + 153 x^16 + 19 x^18 + x^20
如果把 Fn(x), n = 0 ~ 9 的系数印出来：
{1}
{0,1}
{1,0,1}
{0,2,0,1}
{1,0,3,0,1}
{0,3,0,4,0,1}
{1,0,6,0,5,0,1}
{0,4,0,10,0,6,0,1}
{1,0,10,0,15,0,7,0,1}
{0,5,0,20,0,21,0,8,0,1}
可以看到，最高次 (x^n) 总是 1 ，而且和 n 奇偶性不同的 k , x^k 系数为 0
(这应该很好证明) ，如果常数项不为0，则一定是1，
所以：x^0 系数都不用记，x^n也不用，k % 2 != n % 2 时的x^k系数也不用记，
现在来看看要记的有多少：
F0(x) 0 // 什麽都不用记
F1(x) 0 // 一样
F2(x) 0 // 一样
F3(x) 1
F4(x) 1
F5(x) 2
F6(x) 2
F7(x) 3
F8(x) 3
.
.
.
现在假设记任意数字都只要一单位记忆体，共需要：
0 + 0 + 0 + 1 + 1 + 2 + 2 + ... + 49 + 49 = (1 + 49) * 49 = 2450
<- 有 100 项 ->
注：F100(x) 的系数中，最大的一项是 75553695443676829680 大约是 2^(66)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.151.9