1.斐波那契數列?：
數組：int[] F={1, 1, 2, 3, 5, 8, 13, 21, 34, 55 };
特點：
從第三個數開始，后邊每一個數都是前兩個數的和 。F[k]=F[k-1]+F[k-2];
如圖所示：
????????①low、mid、high都是F數組的索引，F[k]-1表示長度。
????????②為了方便計算出mid，變形：F[k]-1 = (F[k-1]-1) + (F[k-2]-1) + 1;(多出來的1，可以當作mid)
????????③high=(F[k]-1)-1;
????????mid=low+F[k-1]-1;
2.需求：
????????現在有一個數組int[] arr={1,8,10,89,1000，1234}，長度n=6；
????????需要定義一個方法，從arr數組中找到數值為80(key=80)，
????????若有，則返回索引，若沒有，就返回-1。
分析：
①黃金分割點：
????????黃金比例又稱黃金分割，是指事物各部分間一定的數學比例關系，即將整體一分為二，較大部分與較小部分之比等于整體與較大部分之比，其比值約為1:0.618或1.618:1。
結論：
????????只要順序表的長度是F[k]-1，就可以分成兩段：較大部分F[k-1]-1，和較小部分F[k-2]-1。
③黃金分割點，是按照長度來劃分，與索引有密切關系。
????????一旦確定了數組arr的黃金分割點mid，之后就可以拿著我們要找的80與黃金分割點mid索引的元素值比較。再之后與二分查找類似。
④arr數組的長度n，是固定的值6，由于(F[k]-1)是不定的，最大值可以非常大，可看成無限大。
????????所以總是會存在：(F[k]-1)的值剛好大于或等于長度6。
????????arr數組的長度n確定了，那么(F[k]-1)的值也就確定了。
因此只要arr數組中元素個數n能達到此時的(F[k]-1)，就可以把arr數組分成兩段，從而確定黃金分割點。
⑤新建一個數組brr，長度為(F[k]-1)。然后把arr這個數組中的數據全都拷貝到brr數組中，不足的部分先用0補充，最后把0換成arr的最后一個元素來補充(即arr[high])。
拿著key=80,與brr[mid]比較，
若key大，就把黃金分割點及右側的部分都刪除。
若key小,就把黃金分割點及左側的部分都刪除。
然后產生新的黃金分割點，再比較，直至兩者相等，文章來源：http://www.zghlxwxcb.cn/news/detail-475443.html
若最終一直沒找到，low>high就停止尋找。文章來源地址http://www.zghlxwxcb.cn/news/detail-475443.html
到了這里，關于斐波那契算法的理解的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
