天津常规网站建设系列,wordpress去掉评论界面,重庆市工程安全建设信息网官网,重庆网站商城一、介绍 斐波拉契查找法是以分割范围进行查找的#xff0c;分割的方式是按照斐波拉契级数的方式来分割。好处是#xff1a;只用到加减运算#xff0c;计算效率较高一些。 要使用斐波拉契查找首先需要定义一颗斐波拉契查找树#xff0c;建立规则如下#xff1a; 1.斐波拉契…一、介绍 斐波拉契查找法是以分割范围进行查找的分割的方式是按照斐波拉契级数的方式来分割。好处是只用到加减运算计算效率较高一些。 要使用斐波拉契查找首先需要定义一颗斐波拉契查找树建立规则如下 1.斐波拉契树的左右子树均为斐波拉契树。 2.当数据个数n确定时若想确定斐波拉契树的层数k值就必须找到一个最小的K值使得斐波拉契层数的Fibk1 n1. 3.斐波拉契树的树根一定是一个斐波拉契树且子节点与父节点差值的绝对值为斐波拉契数。 4.当k2时斐波拉契树的树根为Fib(k),左子树为k-1层斐波拉契树其树根为Fib(k-1),
右子树为k-2层斐波拉契树其树根为Fib(k) Fib(k-2)。 5.若n1的值不为斐波拉契数的值则可以找出存在一个m使用Fib(k1)-m n1mFib(k1)-(n1),再按斐波拉契树的建立原则完成斐波拉契树的建立最后斐波拉契树的各节点减去差值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, 接下来第一种情况时n1的值是斐波拉契数的值假设就是数1~33也就是n33,那么n1 34,可以根据Fib(k1) n1 得出 k的值为8则可以建立斐波拉契树如下 第二种情况就是n1的值不是斐波拉契数的值假设n10,那么n1 11不是斐波拉契数按照第五条规则可以找出一个值m,使Fib(k1) - m n1成立则Fib(k1)13,则m2, k6,按照规则建立的斐波拉契树如下
各节点减去m,并把小于1的节点去掉之后得到 斐波拉契查找法步骤首先将要查找的数与树根Fib(k)比较如果相等这个数就是Fib(k),如果比Fib(k)小则数在1到Fib(k)-1之间如果比Fib(k)大则这个数在Fib(k)1到Fib(k1)-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(val1, 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
{Listint fibls;Node root;void Start(){fibls new Listint(30);FibCalc(30);FibLookUpArithmetic(10);}void FibLookUpArithmetic(int val){int ksum1 0;if (LookUpFibAndIsFib(val1, 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)
