算法之美——魔鬼序列


《趣学算法》在线章节:http://www.epubit.com.cn/book/details/4825

趣味故事1-2:神奇兔子数列

假设第1个月有1对刚诞生的兔子,第2个月进入成熟期,第3个月开始生育兔子,而1对成熟的兔子每月会生1对兔子,兔子永不死去……那么,由1对初生兔子开始,12个月后会有多少对兔子呢?

兔子数列即斐波那契数列,它的发明者是意大利数学家列昂纳多•斐波那契(Leonardo Fibonacci,1170—1250)。1202年,他撰写了《算盘全书》(《Liber Abaci》)一书,该书是一部较全面的初等数学著作。书中系统地介绍了印度—阿拉伯数码及其演算法则,介绍了中国的“盈不足术”;引入了负数,并研究了一些简单的一次同余式组。

(1)问题分析

我们不妨拿新出生的1对小兔子分析:

第1个月,小兔子①没有繁殖能力,所以还是1对。

第2个月,小兔子①进入成熟期,仍然是1对。

第3个月,兔子①生了1对小兔子②,于是这个月共有2(1+1=2)对兔子。

第4个月,兔子①又生了1对小兔子③。因此共有3(1+2=3)对兔子。

第5个月,兔子①又生了1对小兔子④,而在第3个月出生的兔子②也生下了1对小兔子⑤。共有5(2+3=5)对兔子。

第6个月,兔子①②③各生下了1对小兔子。新生3对兔子加上原有的5对兔子这个月共有8(3+5=8)对兔子。

……

为了表达得更清楚,我们用图示来分别表示新生兔子、成熟期兔子和生育期兔子,兔子的繁殖过程如图1-10所示。

图1-10 兔子繁殖过程

这个数列有十分明显的特点,从第3个月开始,当月的兔子数=上月兔子数+当月新生兔子数,而当月新生的兔子正好是上上月的兔子数。因此,前面相邻两项之和,构成了后一项,即:

当月的兔子数=上月兔子数+上上月的兔子数

斐波那契数列如下:

1,1,2,3,5,8,13,21,34,…

递归式表达式:

那么我们该怎么设计算法呢?

哈哈,这太简单了,用递归算法很快就算出来了!

(2)算法设计

首先按照递归表达式设计一个递归算法,见算法1-8。

//算法1-8 
Fib1(int n) 
{  
  if(n<1)   
     return -1;
if(n==1||n==2)   
     return 1;
  return Fib1(n-1)+Fib1(n-2);
}

写得不错,那么算法设计完成后,我们有3个问题:

  • 算法是否正确?
  • 算法复杂度如何?
  • 能否改进算法?

(3)算法验证分析

第一个问题毋庸置疑,因为算法1-8是完全按照递推公式写出来的,所以正确性没有问题。那么算法复杂度呢?假设T(n)表示计算Fib1(n)所需要的基本操作次数,那么:

n=1时,T(n)=1;
n=2时,T(n)=1;
n=3时,T(n)=3;//调用Fib1(2)、Fib1(1)和执行一次加法运算Fib1(2)+Fib1(1)

因此,n>2时要分别调用Fib1(n−1)、Fib1(n−2)和执行一次加法运算,即:

n>2时,T(n)= T(n-1)+ T(n-2)+1;

递归表达式和时间复杂度T(n)之间的关系如下:

由此可得:

那么怎么计算F(n)呢?

有兴趣的读者可以看本书附录A中通项公式的求解方法,也可以看下文中的简略解释。

斐波那契数列通项为:

当n趋近于无穷时,

由于

,这是一个指数阶的算法!

如果我们今年计算出了F(100),那么明年才能算出F(101),多算一个斐波那契数需要一年的时间,爆炸增量函数是算法设计的噩梦!算法1-8的时间复杂度属于爆炸增量函数,这在算法设计时是应当避开的,那么我们能不能改进它呢?

(4)算法改进

既然斐波那契数列中的每一项是前两项之和,如果记录前两项的值,只需要一次加法运算就可以得到当前项,时间复杂度会不会更低一些?我们用数组试试看,见算法1-9。

//算法1-9 
Fib2(int n) 
{  
  if(n<1)   
     return -1;
  int *a=new int[n];//定义一个数组
  a[1]=1;
  a[2]=1;
  for(int i=3;i<=n;i++)
     a[i]=a[i-1]+a[i-2];
  return a[n];
}

很明显,算法1-9的时间复杂度为О(n)。算法仍然是按照F(n)的定义,所以正确性没有问题,而时间复杂度却从算法1-8的指数阶降到了多项式阶,这是算法效率的一个巨大突破!

算法1-9使用了一个辅助数组记录中间结果,空间复杂度也为О(n),其实我们只需要得到第n个斐波那契数,中间结果只是为了下一次使用,根本不需要记录。因此,我们可以采用迭代法进行算法设计,见算法1-10。

//算法1-10 
Fib3(int n) 
{
  int i,s1,s2; 
  if(n<1)   
     return -1;
  if(n==1||n==2)   
     return 1;
  s1=1;
  s2=1;
  for(i=3; i<=n; i++)
  {
     s2=s1+s2; //辗转相加法
     s1=s2-s1; //记录前一项
  }
  return s2;
}

迭代过程如下。

初始值:s1=1;s2=1;

      当前解    记录前一项

i=3时  s2=s1+s2=2  s1=s2−s1=1

i=4时  s2=s1+s2=3  s1=s2−s1=2

i=5时  s2=s1+s2=5  s1=s2−s1=3

i=6时  s2=s1+s2=8  s1=s2−s1=5

……      ……      ……

算法1-10使用了若干个辅助变量,迭代辗转相加,每次记录前一项,时间复杂度为О(n),但空间复杂度降到了О(1)。

问题的进一步讨论:我们能不能继续降阶,使算法时间复杂度更低呢?实质上,斐波那契数列时间复杂度还可以降到对数阶О(logn),有兴趣的读者可以查阅相关资料。想想看,我们把一个算法从指数阶降到多项式阶,再降到对数阶,这是一件多么振奋人心的事!

有趣的是:这样一个完全是自然数的数列,通项公式却是用无理数来表达的。而且当n趋向于无穷大时,斐波那契数列前一项与后一项的比值越来越逼近黄金分割比0.618:1÷1 = 1,1÷2 = 0.5,2÷3 = 0.666,…,3÷5 = 0.6,5÷8 = 0.625,…,55÷89 = 0.617977,…,144÷233 = 0.618025,…,46368÷75025 = 0.6180339886……

越到后面,这些比值越接近黄金分割比:

斐波那契数列起源于兔子数列,这个现实中的例子让我们真切地感到数学源于生活,生活中我们需要不断地通过现象发现数学问题,而不是为了学习而学习。学习的目的是满足对世界的好奇心,如果我们怀着这样一颗好奇心,或许世界会因你而不同!斐波那契通过兔子繁殖来告诉我们这种数学问题的本质,随着数列项的增加,前一项与后一项之比越来越逼近黄金分割的数值0.618时,我彻底被震惊到了,因为数学可以表达美,这是令我们叹为观止的地方。当数学创造了更多的奇迹时,我们会发现数学本质上是可以回归到自然的,这样的事例让我们感受到数学的美,就像黄金分割、斐波那契数列,如同大自然中的一朵朵小花,散发着智慧的芳香…… 


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号