算法之美——魔鬼序列

《趣学算法》在线章节: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时,我彻底被震惊到了,因为数学可以表达美,这是令我们叹为观止的地方。当数学创造了更多的奇迹时,我们会发现数学本质上是可以回归到自然的,这样的事例让我们感受到数学的美,就像黄金分割、斐波那契数列,如同大自然中的一朵朵小花,散发着智慧的芳香…… 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

2924 数独挑战

2924 数独挑战  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Descripti...

29930
来自专栏落影的专栏

程序员进阶之算法练习(十一)有感而发

前言 经过这几年的观察,我发现,国内本科高校的ACM集训队,往往汇聚着该校相对靠谱的那一批人。 拿本校举例,队内的众学长学姐毕业之后,有去国内top2的高校...

386100
来自专栏数据结构与算法

BZOJ1965: [Ahoi2005]SHUFFLE 洗牌(exgcd 找规律)

为了表彰小联为Samuel星球的探险所做出的贡献,小联被邀请参加Samuel星球近距离载人探险活动。 由于Samuel星球相当遥远,科学家们要在飞船中度过相当长...

6110
来自专栏数据结构与算法

P1796 汤姆斯的天堂梦_NOI导刊2010提高(05)

题目描述 汤姆斯生活在一个等级为0的星球上。那里的环境极其恶劣,每天12小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为N的星球上天堂般的生活。 有一些航班将...

28880
来自专栏HansBug's Lab

2748: [HAOI2012]音量调节

2748: [HAOI2012]音量调节 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 719  Solve...

30680
来自专栏JetpropelledSnake

Python实现简单的三级菜单

话不多说,直奔代码 # 要处理的字典 dic1 = { '北京': { '东城': { ...

68090
来自专栏老九学堂

干货|轻松掌握C语言的6个经典程序~

? 全程干货! 老九君为大家整理的一些学习C语言必背经典的程序 希望小伙伴们可以在练习的过程中 记住它,理解它,并且熟练应用 ? 1、/*输出9*9口诀。共9...

50490
来自专栏小樱的经验随笔

BZOJ 1192: [HNOI2006]鬼谷子的钱袋(新生必做的水题)

1192: [HNOI2006]鬼谷子的钱袋 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 3557  So...

28370
来自专栏ACM小冰成长之路

HDU-6008-Worried School

ACM模版 描述 ? 题解 简单的模拟题,题意不是特别容易翻译,但是模拟的规则十分简单,和 WFWF 晋级资格相似,大致是一共 X+Y=GX + Y = G 个...

21380
来自专栏web前端教室

重学javascript 红皮高程(5)

JS这项技术,细节到位了,就会一通百通。经常在网上看到说学一个框架,最有效的办法是去看它的源码。但我经常看不懂,为什么呢?因为我基础不好,不明白源码中的一些写法...

21450

扫码关注云+社区

领取腾讯云代金券