关键词:
在每一种编程语言里,斐波那契数列的计算方式都是一个经典的话题。它可能有很多种计算方式,例如:递归、迭代、数学公式。哪种算法最容易理解,哪种算法是性能最好的呢?
这里给大家分享一下我对它的研究和总结:下面是几种常见的代码实现方式,以及各自的优缺点、性能对比。
Iteration
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
public class Program
public static void Main()
var watch = new Stopwatch();
watch.Start();
var r = Fibonacci().Take(40).Last();
watch.Stop();
Console.WriteLine($"计算结果:r,耗时:watch.Elapsed");
Console.ReadLine();
private static IEnumerable<int> Fibonacci()
int current = 1, next = 1;
while (true)
yield return current;
next = current + (current = next);
计算结果:102334155,耗时:00:00:00.0029930
Recursion
using System;
using System.Diagnostics;
public class Program
public static void Main()
var watch = new Stopwatch();
watch.Start();
Func<int, int> fib = null;
fib = x => x < 2 ? x : fib(x - 1) + fib(x - 2);
var r = fib(40);
watch.Stop();
Console.WriteLine($"计算结果:r,耗时:watch.Elapsed");
Console.ReadLine();
计算结果:102334155,耗时:00:00:00.7022325
Tail Recursion
using System;
using System.Diagnostics;
using System.Threading;
public class Program
public static void Main()
var watch = new Stopwatch();
watch.Start();
Func<int, int, int, int> fib = null;
fib = (n, a, b) => n == 0 ? a : fib(n - 1, b, a + b);
var r = fib(40, 0, 1);
watch.Stop();
Console.WriteLine($"计算结果:r,耗时:watch.Elapsed");
Console.ReadLine();
计算结果:102334155,耗时:00:00:00.0001280
这几种实现方式总结:
- 迭代
代码逻辑清晰,容易理解,性能中等。
- 递归
代码最为简洁,逻辑最清晰,最容易理解,性能最差。
- 尾递归
性能最好,代码逻辑稍微复杂。
由此可见,不同的算法对程序的性能影响是十分巨大的,甚至是上千倍以上的差距。
求斐波那契数列(代码片段)
斐波那契数列-`f(0)=0`-`f(1)=1`-`f(n)=f(n-1)+f(n-2)`前两个值的和递归/***斐波那契数列(递归)*@paramnn*/functionfibonacci(n:number):numberif(n<=0)return0if(n===1)return1returnfibonacci(n-1)+fibonacci(n-2)递归计算但这种方式会导致很多重复计算。 查看详情
01-封装函数求斐波那契数列第n项
<!DOCTYPEhtml><html><headlang="en"><metacharset="UTF-8"><title></title></head><body><script>//需求:封装一个函数,求斐波那契数列的第n项alert(getValue());//定义一个函数funct 查看详情
递归求斐波那契数列
参考技术A如果要使用递归的方法,求菲波列那契数,那还要看这个斐波那契数列,他的第一项是零还是一?如果是零的话,可以这样写,就是递归函数以n为参数,如果N=0,或者n=1,那就直接返回n的值,否则就返回前面两项的函... 查看详情
斐波那契数列及青蛙跳台阶问题
题目1:写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。斐波那契(Fibonacci)数列定义例如以下:f(n)=?????0,1,f(n?1)+f(n?2),n=0n=1n>2egin{equation}f(n)=left{egin{array}{cc}0,&n=01,&n=1f(n-1)+f(n-2),&n>2end{array} ight.end 查看详情
编写一递归函数求斐波那契数列的前40项
以下是使用递归函数来计算斐波那契数列的前40项的Python代码:pythonCopycodedeffibonacci(n):ifn<=1:returnnelse:return(fibonacci(n-1)+fibonacci(n-2))#计算前40项斐波那契数列foriinrange(40):print(fibonacci(i),end="")在这个代码中,fibonacci(n)函数使用递归... 查看详情
poj3070求斐波那契数列第n项——矩阵快速幂(代码片段)
题目:http://poj.org/problem?id=3070用矩阵快速幂加速递推。代码如下:#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intn,p=10000;structMatrixinta[3][3];Matrixoperator*(constMatrix 查看详情
求斐波那契数列的第n项(代码片段)
斐波那契数列介绍斐波那契数列(Fibonaccisequence),又称黄金分割数列,因数学家列昂纳多·斐波那契(LeonardodaFibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13... 查看详情
求斐波那契数列
文章目录一、求斐波那契数列1.题目描述2.题目链接3.解题思路一、求斐波那契数列1.题目描述2.题目链接 查看详情
python递归求斐波那契数列前10项
...写递归程序,求出斐波那契数列前10项。具体代码如下:求斐波那契数列前10项参考技术A单击窗体后在窗体上输出前20个斐波那契数(5个一行)privatesubfrm_click()dimf(20)asintegerf(1)=1f(2)=1fori=3to20f(i)=f(i-2)+f(i-1)nextifori=1to20ifimod5=0thenprin... 查看详情
快速求斐波那契数列(矩阵乘法+快速幂)
...大请对答案mod10^9+7;1<=n<=10^100; 用矩阵乘法+快速幂求斐波那契数列是经典应用;矩阵公式Cij=Cik*Ckj;根据递推式构造2*2矩阵;原始矩阵1001矩阵21110原始矩阵与矩阵2相乘达到转化状态效果;对矩阵二进行快速幂乘法;达到快... 查看详情
剑指offer面试题10.斐波那契数列
题目一:求斐波拉契数列的第n项。写出一个函数,输入n,求斐波拉契(Fibonacci)数列的第n项。斐波拉契数列定义如下:C++实现://斐波拉契数列#include<iostream>usingnamespacestd;//递归实现longlongFibonacci1(unsignedintn){if(n<=1){returnn;}r... 查看详情
javascript之斐波那契数列的几种实现方法兔子数列黄金分割数列递归for解构(代码片段)
目录1、递归实现2、for循环+解构实现3、相关链接1、递归实现functionfibonacciSequenceRecursion(n) n=Number(n); if(!n)returnalert('请正确输入值'); if(n==1||n==2)return1; returnfibonacciSequenceRecursion(n-2)+fibonacciSequenceRecursion(n-1)... 查看详情
斐波那契数列的语言实现
输入一个正数n,求斐波那契数列的第n个数。斐波那契数列特点:第一个数和第二个数都是一,从第三个数开始,后面的数都是前面两个数的和。要求输入整数n不超过50。C语言实现:#include<stdio.h>intmain(){ inta=1,b=1,c,i,n;&nbs... 查看详情
使用递归方式和非递归方式求斐波那契数
/***非递归斐波那契数列*@paramargs*/publicstaticintgetFieibolaLie(intnumber){ intdata=0; intn=1; intm=1; if(number<=0){ return-1; } if(number==1||number==2){ return1; } while(number>=2){ data+=n; n=m; 查看详情
java用递归编程求斐波那契数列第n项
publicclassFibonacci publicstaticvoidmain(Stringargs[])intn,fn;//n为第n项,fn为第n项的值java.util.Scanners=newScanner(System.in);n=s.nextInt();fn=function(n);System.out.println("斐波那契数列第"+n+"项为:"+fn); publicstaticintfunction(intn)if(n==1||n==2)return1... 查看详情
javascript求斐波那契数列
斐波那契数列:1,1,2,3,5,8,....<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>斐波那契数列</title><styletype="text/css">html,body{padding:0;margin:0;width:1 查看详情
实现斐波那契数列
#斐波那契数列#1,1,2,3,5,8,13....1)用递归函数实现斐波那契数列: (指定第几个斐波那契数)deffib(n):ifn==1orn==2:return1returnfib(n-1)+fib(n-2)print(fib(100)) 查看详情
类似斐波那契数列的递归
...)|*(k阶矩阵行列式)^(n-k)这个n-k是这么推断出来的,咱们先求斐波那契问题,斐波那契是2阶问题,就是每个N位置和前面两个位置有关的意思。而它通过以下的式子可以得出最后乘以2阶矩阵的n-2次方假设你正在爬楼梯。需要n阶你... 查看详情