斐波拉契数多种算法

川长思鸟来 2022-11-25 11:48 122阅读 0赞

/**
     * 斐波拉契数
     */
    public class Fibonacci {
    
        // 普通算法
        public static int fab(int n ){
            if (n <= 2){
                return 1;
            }
            return fab(n-1) + fab(n-2);
        }
    
        // 非递归算法  // 不用递归 O(n)
        public static int fabFor(int n ){
            if (n <= 2){
                return 1;
            }
            int f1 = 1;
            int f2 = 1;
            int now = 0;
            for (int i =3; i <= n; i++){
                now = f1 + f2;
                f1 = f2;
                f2 = now;
            }
            return now;
        }
    
        // 用数组来做缓存 将为了O(n)，空间也降至为O(n)
        public static int[] map = new int[n];
        public static int fabMap(int n ){
            if (n <= 2){
                return 1;
            }
            if (map[n] >0){
                return map[n];
            }
            int res = fabMap(n-1) + fabMap(n-2);
            map[n] = res;
            return res;
        }
    
        /**
         * 尾递归
         * last 上一次运算出来结果
         * beforeLast 上上一次运算出来的结果
         */
        public static int tailfab(int beforeLast,int last,int n) {
            if (n <= 2)
                return last; // 递归的终止条件
            return tailfab(last, beforeLast + last, n - 1);	
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，122人围观）

还没有评论，来说两句吧...

相关阅读

相关斐波那契数

1、用java代码去计算 / @Title:斐波那契数(这个数列从第3项开始，每一项都等于前两项之和) @Author: longzhou

た入场券/ 2023年06月15日 13:29/ 0 赞/ 4 阅读

相关算法初识——斐波那契数

复杂度 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

小灰灰/ 2023年03月02日 13:17/ 0 赞/ 102 阅读

相关斐波拉契数多种算法

/ 斐波拉契数 / public class Fibonacci { // 普通算法 publi

川长思鸟来/ 2022年11月25日 11:48/ 0 赞/ 123 阅读

相关斐波拉契数列

\\ 求斐波那契数列的前10项及总和 \\ !/bin/bash 编写一个脚本，求fibonacci数列的前10项及其总和 firstNumber=1;

客官°小女子只卖身不卖艺/ 2022年07月16日 13:13/ 0 赞/ 242 阅读

相关 python------斐波拉契数列

假设你现在正在爬楼梯，楼梯有 nn 级。每次你只能爬 11 级或者 22 级，那么你有多少种方法爬到楼梯的顶部？输入格式第一行输入一个整数 n(1\\leq n \

Love The Way You Lie/ 2022年06月08日 12:27/ 0 赞/ 223 阅读

相关斐波那契数

> 牛客网《剑指offer》时间限制：`1秒` 空间限制：`32768K` 热度指数：`199742` 解题思路一：如果像这样，将会有大量的计算是重复的，时空

╰+哭是因爲堅強的太久メ/ 2022年06月08日 02:46/ 0 赞/ 187 阅读

相关斐波拉契数列-黄金分割

fibonacci(斐波拉契)数列 1 0 1 1 2 1 3 2 5 3 8 5 [1, 1,

- 日理万妓/ 2022年05月30日 06:53/ 0 赞/ 229 阅读

相关算法——斐波拉契数列多种实现方法

斐波拉契数列：1，1，2，3，5，8，13，21，34，55，89，144。。。以下程序默认数列从1开始，不考虑参数为0情况。若保存以前值可以用列表保存常规写法

「爱情、让人受尽委屈。」/ 2022年04月13日 11:44/ 0 赞/ 118 阅读

相关 golang 斐波那契数

golang 斐波那契数 package main import "fmt" / 斐波那契数，亦称之为斐波

短命女/ 2021年11月02日 02:02/ 0 赞/ 299 阅读

相关 1-2求斐波拉契数

求斐波拉契数斐波拉契数为，Fib(N) = Fib(N-1)+Fib(N-2) F(0)=F(1)=1 用Java编写能求Fib(N)的程序输入为N,须输出Fib(...

亦凉/ 2021年04月24日 06:19/ 0 赞/ 359 阅读