[理工] [DS]-Fibonacci Search
假設 n=33 筆，Fib. search decisio tree 如下：
21
/ \ -----1
13 29
/ \ / \ -----2
08 18 26 32
/ \ / \ / \ /\ -----3
05 04 16 20 24 28 31 33
/ \ / / \ \ / -----4
15 17 19 23 25 27 30
/ / -----5
14 22
樹也太難打..= =
這是洪X上課所講的例題，
先找出 Fa => m = (n+1) - Fa => Fa = 34，
不過不懂的是..為什麼最多比較次數是七次？
34不是 Fib.數列 的第九項嗎，所以要九次？
換種看法，如果從樹的root作top-down下來這樣也頂多五次？
還是說我觀念錯誤了..還麻煩指教了><
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.57.105.199
推
01/02 22:21, , 1F
01/02 22:21, 1F
→
01/02 22:25, , 2F
01/02 22:25, 2F
→
01/02 22:38, , 3F
01/02 22:38, 3F