如何理解Java數(shù)據(jù)結(jié)構(gòu)與算法

本篇內(nèi)容介紹了“如何理解Java數(shù)據(jù)結(jié)構(gòu)與算法”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！

基本介紹

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 斐波那契是指把一條線段分割成兩部分，使其中一部分與全長之比等于另一部分與這部分之比。取其前三位數(shù)字的近似值是0.618。由于按此比例設(shè)計的造型十分美麗，因此也稱為黃金分割，也稱中外比。

3. 斐波那契數(shù)列{1,1,2,3,5,8,13,21,34,55}發(fā)現(xiàn)斐波那契數(shù)列的兩個相鄰數(shù)的比例，無限接近黃金分割值0.618.

斐波那契查找原理

斐波那契查找原理與二分查找和插值查找相似，僅僅改變了中間點(mid)的位置，mid不再是中間或插值得到的，而是位于黃金分割點附近，即mid =  low+F(k-1)-1,F代表斐波那契數(shù)列，如下圖

對F(k-1)-1的理解：

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 由于斐波那契數(shù)列F[k] = F[k-1]+F[k-2]的性質(zhì)，可以得到**(F[k]-1) =  (F[k-1]-1)+(F[k-2]-1)+1**。該公式說明：主要順序表的長度為F[k]-1,則可以將該表分成長度為**F[k-1]和F[k-2]**的兩段，即如上圖所示。從而中間位置為：mid  = low+F(k-1)-1。

3. 類似的，每個字段也可以才用相似的方式分割。

4. 但順序表長度n不一定剛好等于F[k]-1，所以需要將原來的順序表長度n增加至F[k]-1。這里的k值只要能使得F[k]-1恰好大于等于n即可，由以下代碼得到，順序表長度增加后，新增的位置(從n+1到F[k]-1),都賦為n位置的值即可.

while(n>fib(k)-1){    k++; }

代碼案例

package com.xie.search;  public class Fibonacci {      public static void main(String[] args) {         int arr[] = {1, 8, 10, 89, 1000, 1234};         int n = 6;         int x = 1;  //        int[] arr = new int[100]; //        for (int i = 0; i < 100; i++) { //            arr[i] = i; //        } //        int n = 100; //        int x = 1;          System.out.println("Found at index: " +                 fibMonaccianSearch(arr, x, n));     }      /**      * 返回x和y最小的數(shù)      *      * @param x      * @param y      * @return      */     public static int min(int x, int y) {         return (x <= y) ? x : y;     }      /**      * 斐波那契搜索x的索引，找到就返回索引位置，否則返回-1      * <p>      * 算法說明：      * 令arr[0..n-1]為輸入數(shù)組，要搜索的元素為x。      * 1.找到大于或等于n的最小斐波那契數(shù)。將此數(shù)字設(shè)為fibM [第m個斐波納契數(shù)],      * 設(shè)其前面的兩個斐波那契數(shù)為fibMm1 [第（m-1）個斐波那契數(shù)]和fibMm2 [第（m-2）個斐波那契數(shù)]。      * 2.當(dāng)數(shù)組中有要檢查的元素時：      *  a.將x與fibMm2覆蓋范圍的最后一個元素進行比較,如果x匹配，則返回索引;      *  b.如果x小于元素，則將三個Fibonacci變量向前移動兩個Fibonacci，表示消除了剩余數(shù)組的大約后三分之二；      *  c.如果x大于元素，則將三個斐波那契變量向后移動一個斐波那契。將偏移量重置為索引。這些加在一起表明消除了其余陣列的大約三分之一；      * 3.由于可能還有一個元素需要比較，因此請檢查fibMm1是否為1。如果是，則將x與該剩余元素進行比較。如果匹配，則返回索引。      *      * @param arr 數(shù)組      * @param x   查找的值      * @param n   數(shù)組的長度      * @return x索引位置或者-1      */     public static int fibMonaccianSearch(int arr[], int x, int n) {         // 初始化斐波那契數(shù)         //第（m-2）個斐波那契編號         int fibMMm2 = 0;         //第（m-1）個斐波那契編號         int fibMMm1 = 1;         //第 m個斐波那契數(shù)         int fibM = fibMMm2 + fibMMm1;          /* fibM將存儲最小的斐波那契數(shù)大于或等于n*/         while (fibM < n) {             fibMMm2 = fibMMm1;             fibMMm1 = fibM;             fibM = fibMMm2 + fibMMm1;         }          // 從前面標(biāo)記消除的范圍         int offset = -1;          /* 循環(huán)檢查元素,注意，我們將arr[fibMm2]與x進行了比較,當(dāng)fibM變?yōu)?時，fibMm2變?yōu)? */         while (fibM > 1) {             // 檢查fibMm2是否為有效位置             int i = min(offset + fibMMm2, n - 1);              /* 如果x大于索引fibMm2處的值，則將從offset到i切割為子數(shù)組 */             if (arr[i] < x) {                 fibM = fibMMm1;                 fibMMm1 = fibMMm2;                 fibMMm2 = fibM - fibMMm1;                 offset = i;             } else if (arr[i] > x) {                 /*如果小于索引fibMm2處的值，則將從i+1到arr.length-1進行切割數(shù)組*/                 fibM = fibMMm2;                 fibMMm1 = fibMMm1 - fibMMm2;                 fibMMm2 = fibM - fibMMm1;             } else {                 /*找到了，就返回索引*/                 return i;             }         }          /* 將最后一個元素與x比較 */         if (fibMMm1 == 1 && arr[offset + 1] == x) {             return offset + 1;         }          /*沒有找打，返回-1 */         return -1;     } }

“如何理解Java數(shù)據(jù)結(jié)構(gòu)與算法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！