作者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