当前位置:
首页 > Python基础教程 >
-
递归和循环:斐波那契数列
题目描述
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。 n<=39
解题思路
递推公式f(n)=f(n)=
当n=0=0,当n=0 当
n=1=1,当n=1
其他=f(n−1)+f(n−2)看到这大家很容易想起递归,课堂上老师讲递归的时候的经典例子。但是当n很大的时候,就会出现堆栈溢出。堆栈溢出的主要原因是,递归重复的计算太多,很多计算是可以避免的,用循环计算结果,显根据前两项算出第三项,以后每次都是这样计算。
代码实现
递归实现
public static int Fibonacci(int n) { if (n <= 1) return n; return Fibonacci(n - 1) + Fibonacci(n - 2); }
循环实现
public static int Fibonacci2(int n) { if (n <= 1) return n; int first = 0; int second = 1; int result = 0; for (int i = 2; i <= n; i++) { result = first + second; first = second; second = result; } return result; }
斐波那契数列求和
public static int FibonacciSum(int n) { if (n <= 1) return n; int first = 0; int second = 1; int temp = 0; int result = first + second; for (int i = 2; i <= n; i++) { temp = first + second; first = second; second = temp; result = result + temp; } return result; }
斐波那契数列求和,利用公式计算
public static int FibonacciSum2(int n) { if (n <= 1) return n; int first = 0; int second = 1; int temp = 0; for (int i = 2; i <= n; i++) { temp = first + second; first = second; second = temp; } int result = 2 * second + first - 1; //Sn = 2an + an - 1 - 1 return result; }
测试
[Fact] public void Test0() { Assert.Equal(0, Coding007.Fibonacci(0)); Assert.Equal(0, Coding007.Fibonacci2(0)); Assert.Equal(0, Coding007.FibonacciSum(0)); Assert.Equal(0, Coding007.FibonacciSum2(0)); } [Fact] public void Test1() { Assert.Equal(1, Coding007.Fibonacci(1)); Assert.Equal(1, Coding007.Fibonacci2(1)); Assert.Equal(1, Coding007.FibonacciSum(1)); Assert.Equal(1, Coding007.FibonacciSum2(1)); } [Fact] public void Test2() { Assert.Equal(1, Coding007.Fibonacci(2)); Assert.Equal(1, Coding007.Fibonacci2(2)); Assert.Equal(2, Coding007.FibonacciSum(2)); Assert.Equal(2, Coding007.FibonacciSum2(2)); } [Fact] public void Test3() { Assert.Equal(2, Coding007.Fibonacci(3)); Assert.Equal(2, Coding007.Fibonacci2(3)); Assert.Equal(4, Coding007.FibonacciSum(3)); Assert.Equal(4, Coding007.FibonacciSum2(3)); } [Fact] public void Test4() { Assert.Equal(3, Coding007.Fibonacci(4)); Assert.Equal(3, Coding007.Fibonacci2(4)); Assert.Equal(7, Coding007.FibonacciSum(4)); Assert.Equal(7, Coding007.FibonacciSum2(4)); } [Fact] public void Test5() { Assert.Equal(5, Coding007.Fibonacci(5)); Assert.Equal(5, Coding007.Fibonacci2(5)); Assert.Equal(12, Coding007.FibonacciSum(5)); Assert.Equal(12, Coding007.FibonacciSum2(5)); } [Fact] public void Test6() { Assert.Equal(8, Coding007.Fibonacci(6)); Assert.Equal(8, Coding007.Fibonacci2(6)); Assert.Equal(20, Coding007.FibonacciSum(6)); Assert.Equal(20, Coding007.FibonacciSum2(6)); }
想入非非:扩展思维,发挥想象
1. 熟悉递归
2. 熟悉斐波那契数列
3. 斐波那契数列求和
4. 知道有公式的就用公式,不要自己去循环就算,就像1+2+3+......,用高斯定理直接算结果,不要再循环了
栏目列表
最新更新
nodejs爬虫
Python正则表达式完全指南
爬取豆瓣Top250图书数据
shp 地图文件批量添加字段
爬虫小试牛刀(爬取学校通知公告)
【python基础】函数-初识函数
【python基础】函数-返回值
HTTP请求:requests模块基础使用必知必会
Python初学者友好丨详解参数传递类型
如何有效管理爬虫流量?
SQL SERVER中递归
2个场景实例讲解GaussDB(DWS)基表统计信息估
常用的 SQL Server 关键字及其含义
动手分析SQL Server中的事务中使用的锁
openGauss内核分析:SQL by pass & 经典执行
一招教你如何高效批量导入与更新数据
天天写SQL,这些神奇的特性你知道吗?
openGauss内核分析:执行计划生成
[IM002]Navicat ODBC驱动器管理器 未发现数据
初入Sql Server 之 存储过程的简单使用
这是目前我见过最好的跨域解决方案!
减少回流与重绘
减少回流与重绘
如何使用KrpanoToolJS在浏览器切图
performance.now() 与 Date.now() 对比
一款纯 JS 实现的轻量化图片编辑器
关于开发 VS Code 插件遇到的 workbench.scm.
前端设计模式——观察者模式
前端设计模式——中介者模式
创建型-原型模式