什么好的主题做网站,建设网站所需的费用的估算,手机视频网站建设,外贸论坛网站有哪些前阵子#xff0c;日剧“轮到你了”终于大结局了#xff0c;虽然结局有点一言难尽#xff0c;但黑岛和二阶堂两个学霸之间的爱情#xff0c;还是很甜呢呐#xff01;两个学霸之间的默契的斐波那契数列也被许多网友认为是凶手行凶的依据。到底这数列有啥神奇之处#xff0… 前阵子日剧“轮到你了”终于大结局了虽然结局有点一言难尽但黑岛和二阶堂两个学霸之间的爱情还是很甜呢呐两个学霸之间的默契的斐波那契数列也被许多网友认为是凶手行凶的依据。到底这数列有啥神奇之处又该如何使用代码实现呢一起往下看吧斐波那契数列又称黄金分割数列指的是这样一个数列11235813213455…… 我们不难发现从第三项开始每一项都等于前两项之和。以递归的方法定义就是F00F11FnFn-1Fn(n2n∈N*)。(为了与数组下标的概念对应F0为第0项)。通过上面的解释相信你对斐波那契数列有一定的了解了吧那我们来看看今天的题目吧。今天的题目就是当你输入一个整数n后输出斐波那契数列的第n项(从0开始第0项为0n39)。脑袋里有什么想法了么没有的话来看看下面的三种解法吧。一、递归解法斐波那契数列具有天然的递归性,根据数学上的定义可以得出其递推公式为:FnFn-1Fn-2(n2n∈N*),基础情况为 F01,F11。对于递归解法我们可以把问题转化为规模缩小了的同类问题的子问题,找出明确的不需要继续进行递归的条件(即基本情况base case)在本题中的基本情况为F00,F11, 当递归至基本情况后,无需继续递归最后把子问题的解汇聚成大问题的解。可画递归树解决递归问题public class Solution { public int Fibonacci(int n) { //base case if (n0){ return 0; } if(n1){ return 1; } return Fibonacci(n-1)Fibonacci(n-2); }}复杂度分析:①子问题个数即递归树中节点的总数而二叉树节点总数为指数级别所以子问题个数为 O(2^n)而解决一个子问题的时间在本算法中没有循环只有 f(n - 1) f(n - 2)f(n−1)f(n−2) 一个加法操作所以时间为O(1)。故我们可以得到这个算法的时间复杂度为 O(2^n),指数级别。②而在递归过程中,需要在存储递归过程中的运算结果,最大空间为树的高度h(即n)而时间复杂度:O(2^n)故空间复杂度:O(h) 即O(n)。问题分析:观察递归树很明显发现了算法低效的原因存在大量重复计算运算的规模与n的大小成指数关系因此这个暴力递归算法虽然简洁明了,但运行效率低下。二、动态分析由于暴力递归存在大量的重复运算,降低了算法的性能。所以我们可以用动态规划方法把运算结果存储起来,从第0项推导至第n项,避免重复运算。我们可以先思考其暴力递归的解法,把暴力递归的过程抽象成状态转移方程,确定可变参数,从基本情况(base case)开始推理,通过状态转移方程,得出最优解,从而减少冗余运算。public class Solution { public int Fibonacci(int n) { //基本情况 if (n0){ return 0; } if (n1){ return 1; } int dp[]new int[n1]; dp[0]0; dp[1]1; for(int i2;i //状态转移方程 dp[i]dp[i-1]dp[i-2]; } return dp[n]; }}复杂度分析: 需要开辟长度为n1的dp数组,同时遍历整个数组故时间复杂度为O(n)空间复杂度为O(n)。细心的你会发现根据斐波那契数列的状态转移方程当前状态只和之前的两个状态有关其实并不需要那么长的一个 DP 数组来存储所有的状态只要想办法存储之前的两个状态就行了。所以可以进一步优化把空间复杂度降为 O(1)。 三、斐波那契数列通项公式 对于这道题目我们还可以通过斐波那契数列通项公式求解,但这个数学方法仅限于标准的斐波那契数列问题求解,无法应对斐波那契数列的变种问题。公式如下 public class Solution { public int Fibonacci(int n) { Long fib Math.round((Math.pow((1 Math.sqrt(5)) / 2, n) - Math.pow((1 - Math.sqrt(5)) / 2, n)) / Math.sqrt(5)); return fib.intValue(); }}复杂度分析:将n代入公式即可得到答案,其中Math.pow(a,b)为求a的b次方、Math.sqrt(a)为求a的正平方根、Math.round(a)为取a最接近的整数(可简单理解为四舍五入取整).对于pow、sqrt、round方法,我们都可以放心地认为其时间复杂度为O(1),因而总的时间复杂度为O(1)。我们使用变量fib存储运算结果,因此空间复杂度为O(1)。 斐波那契数列来自实现生活,有着诸多的变种问题,例如自然界中向日葵花蕊的排列线条顺时针排列线条数为21逆时针排列线条数为34是两个相邻的斐波那契数树木也是以斐波那契数列的方式生长而黄金比例也经常被用于艺术和建筑的设计规划和建造许多建筑物如教堂寺庙祭坛住房以及创造宗教艺术品。(但其实 斐波那契数列在“轮到你了”就真的只是个数列。)更多精彩内容(点击即可阅读)用两个栈实现队列用队列实现栈持续更新中.....后续我们还会持续更新一些有意思的算法基础题目有兴趣的可以持续关注一下~ 信析团队持续招新有兴趣了解的小可爱可以来科技楼232详谈哦(*╹▽╹*)祝祖国生日快乐
