-
递归和循环:斐波那契数列
本站最新发布 C#从入门到精通
试听地址 https://www.xin3721.com/eschool/CSharpxin3721/
试听地址 https://www.xin3721.com/eschool/CSharpxin3721/
题目描述
大家都知道斐波那契数列,现在要求输入一个整数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+......,用高斯定理直接算结果,不要再循环了
栏目列表
最新更新
python数据库连接池技术总结
成人网站性能提升 20 倍之经验谈 [Python
python动态捕获异常
python 探测网站目录的GUI程序
python实现中文字符繁体和简体中文转换
Python服务器开发 -- 网络基础
python高性能编程方法一
使用python管理Cisco设备
python抓取google搜索结果
Python 自动备份SVN版本库并复制到远程主机
基于UDP的服务器端和客户端
再谈UDP和TCP
在socket编程中使用域名
网络数据传输时的大小端问题
socket编程实现文件传输功能
如何优雅地断开TCP连接?
图解TCP四次握手断开连接
详细分析TCP数据的传输过程
图解TCP数据报结构以及三次握手(非常详
TCP协议的粘包问题(数据的无边界性)
Excel数据导入到Sql server
SQL Server like 字段
SQL Server中的LEFT、RIGHT函数
sql server 安装出现需要sqlncli.msi文件,错误
SQL Server学习内容(一)
SQLServer执行大脚本文件时,提示“无法执
数据库敏捷版本控制之3个数据库策略
将select 转为json
SQL Server 创建索引(index)
GROUP BY中的WITH CUBE、WITH ROLLUP原理测试及