本文最后更新于 2019年 5月 1号 下午 6点 36分，并同步发布于 :
斐波那契数列
声明 : 请不要使用本文的代码直接用于实际项目，本文的目的是以这个示例给读者提供一点编程上的思路
本文假设读者有对如下概念有所了解 :
如何用递归计算斐波那契数列的第 100000 项 ?
有的同学可能会说 : 那还不简单, 不到一分钟便写出了如下代码 :
public static int Fibonacci(int n)
{
if (n == 1 || n == 2)
{
return 1;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
或者 :
public static int Fibonacci(int n)
=> n <= 2
? 1
: Fibonacci(n - 1) + Fibonacci(n - 2);
先测试一下斐波那契数列的第 10 项试试 :
再试试第
50 项 :
结果竟然是负数 ? 不过仔细一想, 是因为结果值超出了
int 类型的存储范围。而且用了 一分多钟 的时间 ！
第 100 项呢 :
emmmmmmm... ... 由于我生命有限, 就不测试这个了, 估计我睡完一觉了还没得出结果 orz
如果计算更大的项时, 很可能出现下面的情况 : (具体多大的项 因电脑配置而异)
程序计算比较大的项时, 发生了 堆栈溢出 异常。
递归计算斐波那契数列时, 函数调用的次数是 指数级 增加的
在解决问题之前我们先看一下递归求斐波那契数列的函数调用情况 :
可以看到, 在计算结果时, 出现了很多重复计算
这也是为什么计算比较大的项时， 用时非常长
将值缓存起来
那么应该如何改写上面写的函数呢 ？
我们可以通过把已经计算过的值存储在一个容器中， 等下次需要计算时， 直接从中取值。
这样可以大幅度的减少函数递归调用的次数
当然还有一个问题 ：
计算比较大的项时， 值可能非常大， 超出了所有C#内置的基本整数类型的最大存储范围。
所以我们需要使用 System.Numerics 命名空间下的大整数类型 : BigInteger, 这个类型可以存储任意大的整数。当然也可以自己手写一个大整数类型。至于怎么写一个大整数类型，不在本文的讨论范围。
.NET framework程序需要添加程序集引用:System.Numerics.dll
现在开始修改刚刚写的递归函数
修改之后的 Fibonacci 函数
这样的话, 就避免了大量的重复计算。
先试试计算斐波那契数列的第 50 项 :
仅仅用了 10 毫秒 !
再试试第 5000 项呢 ?
仅仅用了 19 毫秒 ! 第 5000 项的值已经非常非常大了
虽然使用缓存避免了大量的重复计算，使得计算时间大幅降低
但是需要计算的项非常大时， 调用栈还是会发生溢出 ！
渐进式计算 :
前面我们通过把中间结果缓存到集合中，以避免重复计算，也就是说 ：
如果前 5000 项已经计算过，那么再计算第 5001 项时，只需一次计算 (第 5000 项和第 4999 项相加)
现在假设计算第 6000 项时会发生 栈溢出，那么我们可以 :
- 先计算第
5000项 ( 不会 栈溢出) - 再计算第
6000项 ( 也不会 发生栈溢出 !)
因为前
5000项已经被缓存到集合中，所以再计算第6000项时，只需计算第5001 ~ 6000项。
那么我们需要计算第 100000 (十万) 项呢 ?
- 计算第
5000项 - 计算第
10000项 - 计算第
15000项 - 计算第
20000项
... ...
以此类推
最后计算第 100000 项
现在我们修改上面的代码，使得能计算 任意大 的项 (只要运行内存够大)：
.NET Framework 4.0及以下版本，单个对象不能大于2GB
修改之后的 Fibonacci 函数
使用上图中的代码计算斐波那契数列的第 100000 (十万)项 :
斐波那契数列的第十万项的值
这是一个
20900 位的整数，用时 0.9 秒
如果想达到这样的效果, 又不想在外面定义一个类成员怎么办?
-
可以把缓存结果值的容器直接放在函数中，
但是每次调用函数时， 都会创建一个集合对象， 开销会比较大。
-
使用 闭包 。
使用闭包延长局部变量的生命周期 :
当
Fibonacci函数执行结束时,cache这个局部变量仍可以从函数外部访问，不会被GC释放
返回一个函数的函数
如何使用 ?
这三次函数调用不会创建集合对象
调用
如果只需要调用一次则可以直接调用返回的函数 :
源代码 : 点击这里获取源代码
---END---
网友评论