2007年3月28日 星期三

費氏數列的特性 (3)

延伸這篇以費氏數列表示費氏數列的想法,可以找出費氏數列和巴斯卡三角形的關係。我沒仔細讀WikiPedia上的說明,好像有些差異,單純自high地記錄找到的關係。

將費氏數列拆成費氏數列的和,並用vector表示各項費氏數列係數的話,容易觀察出巴斯卡三角的特性,這裡只是示意表示,最左邊的欄位表示F(n)的係數,左邊數來第二欄表示F(n-1)的係數,以此類推:

F(n) = [1, 0]
F(n) = [0, 1, 1]
F(n) = [0, 0, 1, 2, 1]
F(n) = [0, 0, 0, 1, 3, 3, 1]
F(n) = [0, 0, 0, 0, 1, 4, 6, 4, 1]

舉例來說,F(n)可以看成 1*F(n-4) + 4*F(n-5) + 6*F(n-6) + 4*F(n-7) + 1*F(n-8),以 n = 9代入為例,即為34 = 1*5 + 4*3 + 6*2 + 4*1 + 1*1。

沒有留言:

張貼留言