劇多
首頁
資訊
體育
娛樂
汽車
投資
財經
軍事
科技
數碼
科學
遊戲
歷史
健康
政治
影視
旅遊
育兒
美食
時尚
房產
農業
社會
文化
教育
技術
美文
情感
故事
家居
職場
自然
闢謠
心理
攝影
漫畫
生活
其它
Club
Tips
熱門話題
搜尋
註冊
登入
首頁
>
Club
>
2021-02-24 12:07
斐波那契數列如何用VB求和?
5
回覆列表
1 # 使用者6237634906850
鄧老師的示例程式碼如下
約定以下的敘述中用fib(n)代指斐波那契數列的第n項
的確需要建立一個斐波那契數列備用,用到了Fib數列類建立到第lo - hi項,因為當n > 5時,fib(n) > n,肯定能夠找到不大於lo - hi的最大的斐波那契數作為mi - lo的值;當n < 5時,經驗證也能找到查詢區間的長度不一定要為斐波那契數的某一項減一。如2所說,分割的方法是找到不大於lo - hi的最大的斐波那契數作為mi - lo的值,此時有三種可能情況目標剛好是mi處的值,那麼查詢結束目標位於長度為fib(k - 1) - 1的前段, 那麼深入前段查詢,前段變成了新的查詢區間,此時查詢區間已經為某個斐波那契數減一。而且根據斐波那契數列的定義,有fib(k) - 1 = (fib(k - 1) - 1) + 1 + (fib(k - 2) - 1),即“總長 = 前段長度+ 界樁寬度 + 後段長度,且總長、前段長度、後段長度均為某個斐波那契數減一”,那麼不論目標位於何處,後續查詢中的查詢區間的長度恆為某個斐波那契數減一目標位於長度大於等於fib(k - 2) - 1的後段,那麼深入後段查詢,後段變成了新的查詢區間。此時的處理模式與之前處理得到該後段的模式相同為什麼不直接用(hi-lo)*0.618來尋找分割點?這個問題我個人的看法是乘法的開銷較大,而且對於查詢效果的提高有限。斐波那契數前後項之比 fib(n) / fib(n - 1) 也只是在n比較大的時候才接近黃金比例1.618…,而且區間的長度不一定為某個斐波那契數減一(也有可能查詢的目標是最後一個數嘛),所以斐波那契查詢的意義應該是在效果與開銷之間找到一個平衡,使效率儘可能的最大化
個人對於演算法開銷的衡量仍處於一知半解的懵懂階段。最後一點(斐波那契查詢的優勢)如有錯誤之處,歡迎指正。
發表回復
相關內容
斐波那契數列有什麼用處?
斐波那契數列的通項公式?
斐波那契數列的合理性證明?
倒數數列求和公式?
數列求和快捷公式?
斐波那契數列的公式是什麼?
python做斐波那契數列?
斐波那契數列通項公式是什麼?
用C語言編寫能計算斐波那契數列的程式?
∧
中秋節和大豐收的關聯?
∨
為什麼讀《三國演義》時感覺劉備、關羽、張飛就是背上行囊、出門打工的?
熱門排行
千戶苗寨現在關了嗎?
外地車能進浦東新區紅楓路嗎?
大林寺桃花的解釋?
自駕遊需要準備的清單?
雲上大陸11階裝備條件?
幾月份的菱角最好?
13ultra處理器是超頻版的嗎?
太陽能沒有熱水還會繼續流出冷水嗎?
雷紫go的水友賽怎麼進?
80厘米的桌子配多高的凳子?
鄧老師的示例程式碼如下
約定以下的敘述中用fib(n)代指斐波那契數列的第n項
的確需要建立一個斐波那契數列備用,用到了Fib數列類建立到第lo - hi項,因為當n > 5時,fib(n) > n,肯定能夠找到不大於lo - hi的最大的斐波那契數作為mi - lo的值;當n < 5時,經驗證也能找到查詢區間的長度不一定要為斐波那契數的某一項減一。如2所說,分割的方法是找到不大於lo - hi的最大的斐波那契數作為mi - lo的值,此時有三種可能情況目標剛好是mi處的值,那麼查詢結束目標位於長度為fib(k - 1) - 1的前段, 那麼深入前段查詢,前段變成了新的查詢區間,此時查詢區間已經為某個斐波那契數減一。而且根據斐波那契數列的定義,有fib(k) - 1 = (fib(k - 1) - 1) + 1 + (fib(k - 2) - 1),即“總長 = 前段長度+ 界樁寬度 + 後段長度,且總長、前段長度、後段長度均為某個斐波那契數減一”,那麼不論目標位於何處,後續查詢中的查詢區間的長度恆為某個斐波那契數減一目標位於長度大於等於fib(k - 2) - 1的後段,那麼深入後段查詢,後段變成了新的查詢區間。此時的處理模式與之前處理得到該後段的模式相同為什麼不直接用(hi-lo)*0.618來尋找分割點?這個問題我個人的看法是乘法的開銷較大,而且對於查詢效果的提高有限。斐波那契數前後項之比 fib(n) / fib(n - 1) 也只是在n比較大的時候才接近黃金比例1.618…,而且區間的長度不一定為某個斐波那契數減一(也有可能查詢的目標是最後一個數嘛),所以斐波那契查詢的意義應該是在效果與開銷之間找到一個平衡,使效率儘可能的最大化個人對於演算法開銷的衡量仍處於一知半解的懵懂階段。最後一點(斐波那契查詢的優勢)如有錯誤之處,歡迎指正。