• 查找算法 —— 斐波拉契查找法

    一、介绍

            斐波拉契查找法是以分割范围进行查找的，分割的方式是按照斐波拉契级数的方式来分割。好处是：只用到加减运算，计算效率较高一些。

           要使用斐波拉契查找首先需要定义一颗斐波拉契查找树，建立规则如下：

           1.斐波拉契树的左右子树均为斐波拉契树。

           2.当数据个数n确定时，若想确定斐波拉契树的层数k值，就必须找到一个最小的K值，使得斐波拉契层数的Fib（k+1）>= n+1.

           3.斐波拉契树的树根一定是一个斐波拉契树，且子节点与父节点差值的绝对值为斐波拉契数。

           4.当k>=2时，斐波拉契树的树根为Fib(k),左子树为（k-1）层斐波拉契树（其树根为Fib(k-1)）,

    右子树为（k-2）层斐波拉契树（其树根为Fib(k) + Fib(k-2)）。

           5.若n+1的值不为斐波拉契数的值，则可以找出存在一个m使用Fib(k+1)-m = n+1，m=Fib(k+1)-(n+1),再按斐波拉契树的建立原则完成斐波拉契树的建立，最后斐波拉契树的各节点减去差值m即可，并把小于1的节点去掉。

          可以先罗列一部分斐波拉契数的值，如下：

     Fib(0) = 0, Fib(1) = 1, Fib(2) = 1, Fib(3) =2, Fib(4) = 3，

     Fib(5) = 5, Fib(6) = 8, Fib(7) = 13,  Fib(8) = 21, Fib(9) = 34,

          接下来第一种情况时n+1的值是斐波拉契数的值，假设就是数1~33，也就是n=33,那么n+1 = 34,可以根据Fib(k+1) >= n+1 得出 k的值为8，则可以建立斐波拉契树，如下：       

      第二种情况就是n+1的值不是斐波拉契数的值，假设n=10,那么n+1 =11，不是斐波拉契数，按照第五条规则，可以找出一个值m,使Fib(k+1) - m = n+1成立，则Fib(k+1)=13,则m=2, k=6,按照规则建立的斐波拉契树如下：

    各节点减去m,并把小于1的节点去掉之后得到

    斐波拉契查找法步骤首先将要查找的数与树根Fib(k)比较，如果相等这个数就是Fib(k),如果比Fib(k)小则，数在1到Fib(k)-1之间，如果比Fib(k)大，则这个数在Fib(k)+1到Fib(k+1)-1之间。

    二、建立Fib树代码

    1.首先先生成Fib数储存起来，避免每次查找都要计算一遍：

    1. void FibCalc(int n)
    2. {   
    3.     fibls.Add(0);
    4.     for (int i = 1; i < n; i++)
    5.     {
    6.         if (i < 3)
    7.         {
    8.             fibls.Add(1);
    9.         }
    10.         else
    11.         {
    12.             fibls.Add(fibls[i-1] + fibls[i-2]);
    13.         } 
    14.     }
    15. }

    2.然后判断一个数是不是Fib数并且找到一个比这个数大或者相等的Fib数

    1.  bool LookUpFibAndIsFib(int val, out int ksum1)
    2.  {
    3.      ksum1 = -1;
    4.      if (val < 0)
    5.      {
    6.          Debug.LogError("输入的值不能小于0");
    7.          return false;
    8.      }
    9.         
    10.      for (int i = 0; i < fibls.Count; i++)
    11.      {
    12.          if (val == fibls[i])
    13.          {
    14.              ksum1 = i;
    15.              return true;
    16.          }
    17.          else if(val < fibls[i])
    18.          {
    19.              ksum1 = i;
    20.              return false;
    21.          }
    22.      }
    23.      Debug.LogError("没有匹配到K");
    24.      return false;
    25.  }

     3，生成Fib树

    1.   void GenerateFibTree(Node node, int k,int val)
    2.   {
    3.       if (k - 2 < 0) return;
    4.       int fibNum = node.Data - fibls[k - 2];
    5.       
    6.  
    7.       if (fibNum == node.Data) return;
    8.  
    9.       if (node.Data != 1)
    10.       {
    11.           node.LeftNode = new Node();
    12.           node.LeftNode.Data = fibNum;
    13.           node.LeftNode.PNode = node;
    14.       }
    15.  
    16.       int fibNumR = node.Data + fibls[k - 2];
    17.       if (fibNum > 1 && fibNumR != root.Data)
    18.       {
    19.  
    20.           if (fibNumR != node.PNode.Data || node.PNode == null)
    21.           {
    22.               if (node.PNode.PNode != null && fibNumR != node.PNode.PNode.Data)
    23.               {
    24.                   node.RightNode = new Node();
    25.                   node.RightNode.Data = fibNumR;
    26.                   node.RightNode.PNode = node;
    27.               }
    28.               if (node.PNode.PNode == null)
    29.               {
    30.                   node.RightNode = new Node();
    31.                   node.RightNode.Data = fibNumR;
    32.                   node.RightNode.PNode = node;
    33.               }
    34.           }
    35.       }
    36.  
    37.       if (node.LeftNode != null)
    38.           GenerateFibTree(node.LeftNode, k - 1, val);
    39.       if (node.RightNode != null)
    40.           GenerateFibTree(node.RightNode, k - 2, val);
    41.   }

     4.在需要减去m的情况下：

    1.  void FibTreeMinusM(int m,Node node)
    2.  {
    3.      if (node.LeftNode != null)
    4.      {
    5.          node.LeftNode.Data -= m;
    6.          FibTreeMinusM(m, node.LeftNode);
    7.          if (node.LeftNode.Data < 1)
    8.              node.LeftNode = null;
    9.      }
    10.      if (node.RightNode != null)
    11.      {
    12.          node.RightNode.Data -= m;
    13.          FibTreeMinusM(m, node.RightNode);
    14.          if (node.RightNode.Data < 1)
    15.              node.RightNode = null;
    16.      }
    17.  }

    5.最后按照输入的数值生成Fib树

    1.    void FibLookUpArithmetic(int val)
    2.    {
    3.        int ksum1 = 0;
    4.        if (LookUpFibAndIsFib(val+1, out ksum1))
    5.        {
    6.            int k = ksum1 - 1;
    7.            InitGenerateFibTree(k,val);
    8.        }
    9.        else
    10.        {
    11.            int k = ksum1 - 1;
    12.            InitGenerateFibTree(k, val);
    13.            int m = fibls[ksum1] - (val + 1);
    14.            root.Data -= m;
    15.            FibTreeMinusM(m, root);
    16.        }
    17.    }

     完整代码：

    1. using System.Collections.Generic;
    2. using UnityEditor.Experimental.GraphView;
    3. using UnityEngine;
    4. using UnityEngine.Rendering;
    5.  
    6. public class LookUpArithmetic : MonoBehaviour
    7. {
    8.     List<int> fibls;
    9.     Node root;
    10.     void Start()
    11.     {
    12.         fibls = new List<int>(30);
    13.         FibCalc(30);
    14.         FibLookUpArithmetic(10);
    15.     }
    16.  
    17.     void FibLookUpArithmetic(int val)
    18.     {
    19.         int ksum1 = 0;
    20.         if (LookUpFibAndIsFib(val+1, out ksum1))
    21.         {
    22.             int k = ksum1 - 1;
    23.             InitGenerateFibTree(k,val);
    24.         }
    25.         else
    26.         {
    27.             int k = ksum1 - 1;
    28.             InitGenerateFibTree(k, val);
    29.             int m = fibls[ksum1] - (val + 1);
    30.             root.Data -= m;
    31.             FibTreeMinusM(m, root);
    32.         }
    33.     }
    34.  
    35.     bool LookUpFibAndIsFib(int val, out int ksum1)
    36.     {
    37.         //首先判断是否是一个Fbi数和找到一个Fbi数两步可以合并为一步
    38.         ksum1 = -1;
    39.         if (val < 0)
    40.         {
    41.             Debug.LogError("输入的值不能小于0");
    42.             return false;
    43.         }
    44.            
    45.         for (int i = 0; i < fibls.Count; i++)
    46.         {
    47.             if (val == fibls[i])
    48.             {
    49.                 ksum1 = i;
    50.                 return true;
    51.             }
    52.             else if(val < fibls[i])
    53.             {
    54.                 ksum1 = i;
    55.                 return false;
    56.             }
    57.         }
    58.         Debug.LogError("没有匹配到K");
    59.         return false;
    60.     }
    61.  
    62.     void FibCalc(int n)
    63.     {   
    64.         fibls.Add(0);
    65.         for (int i = 1; i < n; i++)
    66.         {
    67.             if (i < 3)
    68.             {
    69.                 fibls.Add(1);
    70.             }
    71.             else
    72.             {
    73.                 fibls.Add(fibls[i-1] + fibls[i-2]);
    74.             } 
    75.         }
    76.     }
    77.  
    78.     void InitGenerateFibTree(int k, int val)
    79.     {
    80.         root = new Node();
    81.         root.Data = fibls[k];
    82.         root.LeftNode = new Node();
    83.         root.LeftNode.Data = fibls[k] - fibls[k - 2];
    84.         root.LeftNode.PNode= root;
    85.         GenerateFibTree(root.LeftNode, k - 1, val);
    86.         root.RightNode = new Node();
    87.         root.RightNode.Data = fibls[k] + fibls[k - 2];
    88.         root.RightNode.PNode = root;
    89.         GenerateFibTree(root.RightNode, k - 2, val);
    90.     }
    91.  
    92.     void GenerateFibTree(Node node, int k,int val)
    93.     {
    94.         if (k - 2 < 0) return;
    95.         int fibNum = node.Data - fibls[k - 2];
    96.       
    97.  
    98.         if (fibNum == node.Data) return;
    99.  
    100.         if (node.Data != 1)
    101.         {
    102.             node.LeftNode = new Node();
    103.             node.LeftNode.Data = fibNum;
    104.             node.LeftNode.PNode = node;
    105.         }
    106.  
    107.         int fibNumR = node.Data + fibls[k - 2];
    108.         if (fibNum > 1 && fibNumR != root.Data)
    109.         {
    110.  
    111.             if (fibNumR != node.PNode.Data || node.PNode == null)
    112.             {
    113.                 if (node.PNode.PNode != null && fibNumR != node.PNode.PNode.Data)
    114.                 {
    115.                     node.RightNode = new Node();
    116.                     node.RightNode.Data = fibNumR;
    117.                     node.RightNode.PNode = node;
    118.                 }
    119.                 if (node.PNode.PNode == null)
    120.                 {
    121.                     node.RightNode = new Node();
    122.                     node.RightNode.Data = fibNumR;
    123.                     node.RightNode.PNode = node;
    124.                 }
    125.             }
    126.         }
    127.  
    128.         if (node.LeftNode != null)
    129.             GenerateFibTree(node.LeftNode, k - 1, val);
    130.         if (node.RightNode != null)
    131.             GenerateFibTree(node.RightNode, k - 2, val);
    132.     }
    133.  
    134.     void FibTreeMinusM(int m,Node node)
    135.     {
    136.         if (node.LeftNode != null)
    137.         {
    138.             node.LeftNode.Data -= m;
    139.             FibTreeMinusM(m, node.LeftNode);
    140.             if (node.LeftNode.Data < 1)
    141.                 node.LeftNode = null;
    142.         }
    143.         if (node.RightNode != null)
    144.         {
    145.             node.RightNode.Data -= m;
    146.             FibTreeMinusM(m, node.RightNode);
    147.             if (node.RightNode.Data < 1)
    148.                 node.RightNode = null;
    149.         }
    150.     }
    151. }
    152.  
    153. class Node
    154. {
    155.     public Node LeftNode;
    156.     public Node RightNode;
    157.     public int Data;
    158.     public Node PNode = null;
    159. }

    如有不足之处，欢迎指正。

    参考书籍：

    清华大学出版社-图书详情-《图解数据结构--使用C#》 (tsinghua.edu.cn)

  • 相关阅读:
    设计表时，如何选择正确的数据类型
    redis性能优化及哨兵模式
    服务器配置Java开发环境(三)之安装mysql
    澳大利亚网络空间安全体系建设论析
    实现旅行售货员问题的回溯算法
    quartz笔记
    .NET Core使用 CancellationToken 取消API请求
    程序员是怎么分享微信二维码的
    集合深度学习10—同步类容器
    删除的短信怎么恢复？专业与非专业方法的全面比较
  • 原文地址：https://blog.csdn.net/weixin_50702814/article/details/133686070