资讯专栏INFORMATION COLUMN

斐波那契数列(求fibonacci的第N项的值)

Fundebug / 2706人阅读

摘要:今天在公司实习,实在没啥活是我能干的,就想着写一写算法打发时间,正好看到了斐波那契数列,搞起。这是斐波那契数列的通项公式以前用递归写过,今天看的时候书上说递归虽然简单,但其实内部做了很多重复的计算,而且尾递归都是可以用循环解决的。

今天在公司实习,实在没啥活是我能干的,就想着写一写算法打发时间,正好看到了斐波那契数列,搞起。

这是斐波那契数列的通项公式:

以前用递归写过,今天看的时候书上说递归虽然简单,但其实内部做了很多重复的计算,而且尾递归都是可以用循环解决的。而用循环就可以避免重复的计算。

import java.util.Scanner;

public class Jianzhi{

    public static void main (String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        n = fibonacci(n) ;
        System.out.println(n) ;
    }
    public static int fibonacci(int n ) {

        int f0 = 0;
        int f1 = 1;
        int fn = 0 ;
        if (n == 0) {
            return f0;
        }
        if (n == 1) {
            return f1;
        } else {
            for (int i = 2; i <= n; i++) {
                fn = f0 + f1;  //当前循环所得的斐波那契数等于前一个加上前前个
                f0 = f1 ;     //当前循环所得的斐波那契数的前一个数,作为下次循环的前前个次数
                f1 = fn ;     //当前循环所得的斐波那契的数,作为下次循环的前一个数
            }
            return fn;
        }
    }

}

斐波那契数列的变换:
比如,从前有一只青蛙,它一次可以跳一个台阶,也可以一次跳两个台阶,求一个N阶的台阶他会用几种跳法。

那就是假设就1个台阶 那就只有1种跳法;如果有2个台阶,那就有2种;以此类推:

  1    1
  2    2
  3    3
  4    5

完毕。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/71370.html

相关文章

  • 斐波那契数列和的js方案以及优化

    摘要:在上做了一道斐波那契数列求和的题目,做完之后做了一些简单的优化和用另一种方法实现。动态规划解决方案斐波那契数列求和除了可以用递归的方法解决,还可以用动态规划的方法解决。 在codewars上做了一道斐波那契数列求和的题目,做完之后做了一些简单的优化和用另一种方法实现。 题目 function fibonacci(n) { if(n==0 || n == 1) r...

    xinhaip 评论0 收藏0
  • js 实现斐波那契数列(数组缓存、动态规划、尾调用优化)

    摘要:根据该规则,返回第个斐波那契数。尾递归函数调用自身,称为递归。一个前端眼中的斐波那契数列解斐波那契数列的实用解法调用栈尾递归和手动优化尾调用优化译我从用写斐波那契生成器中学到的令人惊讶的件事 斐波那契数列是以下一系列数字: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在种子数字 0 和 1 ...

    赵连江 评论0 收藏0
  • JavaScript解斐波那契(Fibonacci)数列的实用解法

    摘要:下面是一个可以处理很多类型递归函数的函数其中第一个参数为原有函数,第二个参数为缓存对象,是可选参数因为并不是所有递归函数都包含初始信息。首先将缓存对象的类型从数组转换为对象,这样就可以适用于那些不是返回整数的递归函数。 JavaScript解斐波那契(Fibonacci)数列的实用解法 我们经常会在面试题中看到如下题目:输入n,求斐波那契数列的第n项,斐波那契数列的定义如下: F(0)...

    zhongmeizhi 评论0 收藏0
  • 【刷算法】斐波那契数列

    摘要:题目现在要求输入一个整数,请你输出斐波那契数列的第项。递归操作时间复杂度太高,而且用递归会产生很多重复的操作。非递归操作这种方法就是一次遍历过去就行,计算第个数时,使用了两个变量存储第和第个数,使时间复杂度降低到 题目 现在要求输入一个整数n,请你输出斐波那契数列的第n项。 递归操作O(2^n) function fibonacci(n) { if(n < 1) ...

    IamDLY 评论0 收藏0
  • JS专题之memoization

    摘要:前言在计算机领域,记忆是主要用于加速程序计算的一种优化技术,它使得函数避免重复演算之前已被处理过的输入,而返回已缓存的结果。被执行了不是素数,其他数字默认是素数。我们可以看出,如果从开始打印斐波那契数列,函数被执行了次。 前言 在计算机领域,记忆(memoization)是主要用于加速程序计算的一种优化技术,它使得函数避免重复演算之前已被处理过的输入,而返回已缓存的结果。 -- wi...

    zhisheng 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<