Hadoop rinetd 物联网项目 drupal7 vue安装 vue组件注册 less用法 bootstrap文件上传样式 docker的安全特性有哪些 js获取月份 mysql转字符串 chrome发送post请求 mysql组合索引 svn更新本地代码 python使用正则表达式 random函数用法 python代码 java实现 java编程课程 java写入文件 java中的接口 java安装环境 javahttp java中collection 内存修改器 修改tomcat端口 微信小程序提示框 python封装 spoonwep dep mssql 鼠标速度怎么调 机械换装 mysql密码重置 cdr群组快捷键 脚本生成器 凯立德地图下载 网页音乐播放器代码 赛斯切隆废墟 ajaxsubmit
当前位置: 首页 > 学习教程  > 编程语言

查找算法——斐波那契(黄金分割法)查找算法

2020/7/24 9:31:46 文章标签:

基本介绍:

  1. 黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位 数字的近似值是 0.618。由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为中外比。这是一个神 奇的数字,会带来意向不大的效果。
  2. 斐波那契数列{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. 由斐波那契数列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]-1 和 F[k-2]-1 的两段,即如上图所示。从而中间位置为 mid=low+F(k-1)-1
  2. 类似的,每一子段也可以用相同的方式分割
  3. 但顺序表长度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++;

代码实现:


import java.util.Arrays;

/**
 * 斐波那契查找
 */
public class FibonacciSearch {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] fib = fib();
        System.out.println(Arrays.toString(fib));
        int[] arr={2,4,6,8,13,15};
        int index = fibonacciSearch(arr, 8);
        System.out.println(index);

    }

    //因为后面要用到mid=low+F(k-1)-1,需要使用德奥斐波那契数列,因此我们要先获取到一个斐波那契数列
    //非递归的方法得到一个斐波那契数列
    public static int[] fib() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < 20; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }

        return f;
    }

    /**
     * 斐波那契查找算法
     * 使用非递归的方式
     * @param arr 数组
     * @param key 我们要查找的value
     * @return 返回对应下标,如果找不到返回-1
     */
    public static int fibonacciSearch(int[] arr, int key) {
        int l = 0;//左小标
        int r = arr.length - 1;//右下标
        int mid = 0;//存放中间值
        int k = 0;//表示斐波那契分割数值的下标

        //获取到斐波那契数列
        int[] fib = fib();
        //获取到斐波那契分割数值的下标 r=5
        while (r > fib[k] - 1) {
            k++;
        }
        //因为f[k]值可能大于a的长度,因此我们需要使用Arrays,构造一个新的数组,并指向tmp[]
        //不足的部分使用0填充
        int[] tmp = Arrays.copyOf(arr, fib[k]);
        System.out.println("tmp[]= "+Arrays.toString(tmp));
        //实际上需求使用 a 数组最后的数填充 temp
        for (int i = r + 1; i < tmp.length; i++) {
            tmp[i] = arr[r];
        }

        //使用whilea循环,知道左下标l>右下标r
        while (l <= r) {
            //斐波那契(黄金分割法)求中间值
            mid = l + fib[k - 1] - 1;

            /**要查找的数值key在左边,需要往左边找
             * k--的原因
             * 1、全部的元素=前边的元素+后边的元素
             * 2、f(k)=f(k-1)+f(k-2)
             * 3、前边有f(k-1)个元素,即f(k-1)=f(k-2)+f(k-3)
             * 4、即在f(k-1) 前边继续找 k--;
             */
            if (tmp[mid] > key) {
                r = mid - 1;
                k--;
            } else if (tmp[mid] < key) {
                /**
                 * 要查找的数值key在右边,需要往右边找
                 * k-=2的原因:
                 * 1、全部的元素=前边的元素+后边的元素
                 * 2、f(k)=f(k-1)+f(k-2)
                 * 3、后边有f(k-2)个元素,即f(k-2)=f(k-3)+f(k-4)
                 * 4、即在f(k-2) 前边继续找 k-=2;
                 * */
                l = mid + 1;
                k -= 2;
            } else {//找到
                if (mid <= r) {
                    return mid;
                } else {
                    return r;
                }

            }
        }
            //找不到
        return -1;
    }
}

初学数据结构和算法,有不足的地方希望大家多多指出~~一起学习进步!!


本文链接: http://www.dtmao.cc/news_show_50112.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?