求Fibonacci数列:1,1,2,3,5,8,...第40个数的值。
实际Fibonacci斐波那契数列满足以下递推公式:
F(1) = 1, F(2) = 1
F(N) = F(N - 1) + F(N - 2)
public class Fibonacci
{
/**
* 用递归的方式实现Fibonacci
* @param n
* @return
*/
public int fibonacciRecursive(int n)
{
if (n <= 2)
{
return 1;
}
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
/**
* 用非递归的方式实现Fibonacci
* @param n
* @return
*/
public int finonacciNormal(int n)
{
if (n <= 2)
{
return 1;
}
int a1 = 1;
int a2 = 1;
int an = 0;
for (int i = 1; i < n; i++)
{
an = a1 + a2;
a1 = a2;
a2 = an;
}
return an;
}
public static void main(String[] args)
{
Fibonacci fibonacci = new Fibonacci();
System.out.println("fibonacciRecursive==="
+ fibonacci.fibonacciRecursive(40));
System.out.println("finonacciNormal==="
+ fibonacci.finonacciNormal(40));
}
}
分享到:
相关推荐
面试题 1:二维数组中的查找(考点...面试题 7:斐波那契数列(考点: 递归和循环) 7 面试题 8:跳台阶(考点: 递归和循环) 7 面试题 9:变态跳台阶(考点: 递归和循环) 8 面试题 10:矩形覆盖(考点: 递归和循环) 8
常见代码面试题精选记录:包括斐波那契数列、递归方法求斐波那契数列第n项、动态规划方法求斐波那契数列第N项、数组最大最小值、输入数组重复元素以及个数、数组交集,补集,并集、数组结构加工、.数组求和
剑指Offer(Python多种思路实现):斐波那契数列 面试10题: 题目:大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。n<=39 n=0时,f(n)=0 n=1时,f(n)=1 n>1时,f(n)=f(n-1)+f(n-2)...
程序来打印斐波那契数列,例如 1 1 2 3 5 8 13 ... 。 达到给定的数量。 我们准备交叉问题,例如使用迭代而不是递归以及如何使用缓存和记忆优化解决方案。 一个质数(解决方案) 编写一个 Java 程序来检查给定的数...
面试题09:用两个栈实现队列 +2 双栈 面试题10 - I:斐波那契数列 +2 动态规划+递归 面试题10 - II:青蛙跳台阶问题 +2 动态规划+递归 面试题11:旋转数组的最小数字 +2 二分查找 面试题12:矩阵中的路径 +2 DFS ...
│ ├── Fibonacci.php 斐波那契数列 │ ├── StealingApples.php 偷苹果求余 │ ├── HanoiGames.php 汉诺塔游戏 │ ├── BidirectionalQueue.php 双向队列 │ ├── ColorBricks....
leetcode第685题 leetcode-js 力扣js解题记录 树 -> 图论 -> 递归 -> 回溯 -> DFS ...递归解法,迭代解法 ...递归 ...斐波那契数列 剑指 Offer 07. 重建二叉树 剑指 Offer 10- II. 青蛙跳台阶问题 面试题 16
第一篇 面试题 ................................................................................ 8 1.1. 简介 ................................................................................................
14 迭代器协议实现斐波那契数列 16 描述符答疑 17 描述符优先级 18 软件开发规范 19 pycharm干的好事 第28章 01 上节课复习 02 上下文管理协议 04 异常的构成简单了解 05 描述符应用 08 类的装饰器的基本原理 09 ...
对于一个斐波那契数列的求解,你能想到多少种方法? 最简单的---递归: function fib(n){ if(n == 1 || n == 2){ return 1; } return fib(n - 2) + fib(n - 1); } 运行fib(50)的时候,在我笔记本上跑了将近107秒,如...