1. 编程号首页

斐波那契搜索法_排序算法有哪些

编程小号 • • 未分类

斐波那契搜索法_排序算法有哪些学习记录_裴波那契树

一、介绍

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

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

       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数储存起来，避免每次查找都要计算一遍：

void FibCalc(int n)
{   
    fibls.Add(0);
    for (int i = 1; i < n; i++)
    {
        if (i < 3)
        {
            fibls.Add(1);
        }
        else
        {
            fibls.Add(fibls[i-1] + fibls[i-2]);
        } 
    }
}

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

 bool LookUpFibAndIsFib(int val, out int ksum1)
 {
     ksum1 = -1;
     if (val < 0)
     {
         Debug.LogError("输入的值不能小于0");
         return false;
     }
        
     for (int i = 0; i < fibls.Count; i++)
     {
         if (val == fibls[i])
         {
             ksum1 = i;
             return true;
         }
         else if(val < fibls[i])
         {
             ksum1 = i;
             return false;
         }
     }
     Debug.LogError("没有匹配到K");
     return false;
 }

 3，生成Fib树

  void GenerateFibTree(Node node, int k,int val)
  {
      if (k - 2 < 0) return;
      int fibNum = node.Data - fibls[k - 2];
      

      if (fibNum == node.Data) return;

      if (node.Data != 1)
      {
          node.LeftNode = new Node();
          node.LeftNode.Data = fibNum;
          node.LeftNode.PNode = node;
      }

      int fibNumR = node.Data + fibls[k - 2];
      if (fibNum > 1 && fibNumR != root.Data)
      {

          if (fibNumR != node.PNode.Data || node.PNode == null)
          {
              if (node.PNode.PNode != null && fibNumR != node.PNode.PNode.Data)
              {
                  node.RightNode = new Node();
                  node.RightNode.Data = fibNumR;
                  node.RightNode.PNode = node;
              }
              if (node.PNode.PNode == null)
              {
                  node.RightNode = new Node();
                  node.RightNode.Data = fibNumR;
                  node.RightNode.PNode = node;
              }
          }
      }

      if (node.LeftNode != null)
          GenerateFibTree(node.LeftNode, k - 1, val);
      if (node.RightNode != null)
          GenerateFibTree(node.RightNode, k - 2, val);
  }

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

 void FibTreeMinusM(int m,Node node)
 {
     if (node.LeftNode != null)
     {
         node.LeftNode.Data -= m;
         FibTreeMinusM(m, node.LeftNode);
         if (node.LeftNode.Data < 1)
             node.LeftNode = null;
     }
     if (node.RightNode != null)
     {
         node.RightNode.Data -= m;
         FibTreeMinusM(m, node.RightNode);
         if (node.RightNode.Data < 1)
             node.RightNode = null;
     }
 }

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

   void FibLookUpArithmetic(int val)
   {
       int ksum1 = 0;
       if (LookUpFibAndIsFib(val+1, out ksum1))
       {
           int k = ksum1 - 1;
           InitGenerateFibTree(k,val);
       }
       else
       {
           int k = ksum1 - 1;
           InitGenerateFibTree(k, val);
           int m = fibls[ksum1] - (val + 1);
           root.Data -= m;
           FibTreeMinusM(m, root);
       }
   }

 完整代码：

using System.Collections.Generic;
using UnityEditor.Experimental.GraphView;
using UnityEngine;
using UnityEngine.Rendering;

public class LookUpArithmetic : MonoBehaviour
{
    List<int> fibls;
    Node root;
    void Start()
    {
        fibls = new List<int>(30);
        FibCalc(30);
        FibLookUpArithmetic(10);
    }

    void FibLookUpArithmetic(int val)
    {
        int ksum1 = 0;
        if (LookUpFibAndIsFib(val+1, out ksum1))
        {
            int k = ksum1 - 1;
            InitGenerateFibTree(k,val);
        }
        else
        {
            int k = ksum1 - 1;
            InitGenerateFibTree(k, val);
            int m = fibls[ksum1] - (val + 1);
            root.Data -= m;
            FibTreeMinusM(m, root);
        }
    }

    bool LookUpFibAndIsFib(int val, out int ksum1)
    {
        //首先判断是否是一个Fbi数和找到一个Fbi数两步可以合并为一步
        ksum1 = -1;
        if (val < 0)
        {
            Debug.LogError("输入的值不能小于0");
            return false;
        }
           
        for (int i = 0; i < fibls.Count; i++)
        {
            if (val == fibls[i])
            {
                ksum1 = i;
                return true;
            }
            else if(val < fibls[i])
            {
                ksum1 = i;
                return false;
            }
        }
        Debug.LogError("没有匹配到K");
        return false;
    }

    void FibCalc(int n)
    {   
        fibls.Add(0);
        for (int i = 1; i < n; i++)
        {
            if (i < 3)
            {
                fibls.Add(1);
            }
            else
            {
                fibls.Add(fibls[i-1] + fibls[i-2]);
            } 
        }
    }

    void InitGenerateFibTree(int k, int val)
    {
        root = new Node();
        root.Data = fibls[k];
        root.LeftNode = new Node();
        root.LeftNode.Data = fibls[k] - fibls[k - 2];
        root.LeftNode.PNode= root;
        GenerateFibTree(root.LeftNode, k - 1, val);
        root.RightNode = new Node();
        root.RightNode.Data = fibls[k] + fibls[k - 2];
        root.RightNode.PNode = root;
        GenerateFibTree(root.RightNode, k - 2, val);
    }

    void GenerateFibTree(Node node, int k,int val)
    {
        if (k - 2 < 0) return;
        int fibNum = node.Data - fibls[k - 2];
      

        if (fibNum == node.Data) return;

        if (node.Data != 1)
        {
            node.LeftNode = new Node();
            node.LeftNode.Data = fibNum;
            node.LeftNode.PNode = node;
        }

        int fibNumR = node.Data + fibls[k - 2];
        if (fibNum > 1 && fibNumR != root.Data)
        {

            if (fibNumR != node.PNode.Data || node.PNode == null)
            {
                if (node.PNode.PNode != null && fibNumR != node.PNode.PNode.Data)
                {
                    node.RightNode = new Node();
                    node.RightNode.Data = fibNumR;
                    node.RightNode.PNode = node;
                }
                if (node.PNode.PNode == null)
                {
                    node.RightNode = new Node();
                    node.RightNode.Data = fibNumR;
                    node.RightNode.PNode = node;
                }
            }
        }

        if (node.LeftNode != null)
            GenerateFibTree(node.LeftNode, k - 1, val);
        if (node.RightNode != null)
            GenerateFibTree(node.RightNode, k - 2, val);
    }

    void FibTreeMinusM(int m,Node node)
    {
        if (node.LeftNode != null)
        {
            node.LeftNode.Data -= m;
            FibTreeMinusM(m, node.LeftNode);
            if (node.LeftNode.Data < 1)
                node.LeftNode = null;
        }
        if (node.RightNode != null)
        {
            node.RightNode.Data -= m;
            FibTreeMinusM(m, node.RightNode);
            if (node.RightNode.Data < 1)
                node.RightNode = null;
        }
    }
}

class Node
{
    public Node LeftNode;
    public Node RightNode;
    public int Data;
    public Node PNode = null;
}

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

参考书籍：

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

今天的文章斐波那契搜索法_排序算法有哪些分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/81461.html

赞 (0)
编程小号编程小号
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注