如何理解Java数据结构与算法

本篇内容介绍了“如何理解Java数据结构与算法”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

基本介绍

1. 鸿蒙官方战略合作共建——HarmonyOS技术社区

2. 斐波那契是指把一条线段分割成两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此也称为黄金分割，也称中外比。

3. 斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例，无限接近黄金分割值0.618.

斐波那契查找原理

斐波那契查找原理与二分查找和插值查找相似，仅仅改变了中间点(mid)的位置，mid不再是中间或插值得到的，而是位于黄金分割点附近，即mid =  low+F(k-1)-1,F代表斐波那契数列，如下图

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

1. 鸿蒙官方战略合作共建——HarmonyOS技术社区

2. 由于斐波那契数列F[k] = F[k-1]+F[k-2]的性质，可以得到**(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));     }           public static int min(int x, int y) {         return (x <= y) ? x : y;     }           public static int fibMonaccianSearch(int arr[], int x, int n) {         // 初始化斐波那契数         //第（m-2）个斐波那契编号         int fibMMm2 = 0;         //第（m-1）个斐波那契编号         int fibMMm1 = 1;         //第 m个斐波那契数         int fibM = fibMMm2 + fibMMm1;                   while (fibM < n) {             fibMMm2 = fibMMm1;             fibMMm1 = fibM;             fibM = fibMMm2 + fibMMm1;         }          // 从前面标记消除的范围         int offset = -1;                   while (fibM > 1) {             // 检查fibMm2是否为有效位置             int i = min(offset + fibMMm2, n - 1);                           if (arr[i] < x) {                 fibM = fibMMm1;                 fibMMm1 = fibMMm2;                 fibMMm2 = fibM - fibMMm1;                 offset = i;             } else if (arr[i] > x) {                                  fibM = fibMMm2;                 fibMMm1 = fibMMm1 - fibMMm2;                 fibMMm2 = fibM - fibMMm1;             } else {                                  return i;             }         }                   if (fibMMm1 == 1 && arr[offset + 1] == x) {             return offset + 1;         }                   return -1;     } }

“如何理解Java数据结构与算法”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站，小编将为大家输出更多高质量的实用文章！