学习
实践
活动
工具
TVP
写文章

《算法图解》读书笔记 Chapter 3

阅读文本大概需要 6 分钟。

今天突然想起了一个笑话,话说把大象放进冰箱要几步呢?。。。。

……

不,不,不!

我当然不是来讲笑话的,其实我是来讲故事的!

这是一个源自古印度的神话故事:

梵天神告诉侍奉他的婆罗门,只要能实现以下目标,世界就会在一个闪电中毁灭,咱们一起来看下吧!

怎么样,想到解决办法了嘛,没想到也没关系,毕竟咱保卫了全世界不是吗!

下面来解决一下这个问题:

其实这是一个可用递归算法解决的问题。

可将问题分解:

第一步:将A柱上的n-1个盘移到B上;

第二步:将A上的第n号盘移到C;

第三步:将B上的n-1 个盘子移到C上去;

那么具体怎么用程序解决呢,就涉及到今天的笔记内容了,开始总结笔记了!

递归

基线条件和递归条件

调用栈和递归调用栈

斐波那契数列和汉诺塔

小结

如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。

1. 递归

每个递归函数都有两部分:基线条件(base case)和递归条件(recursive case)。

递归条件指的是函数调用自己。

基线条件则指的是函数不再调用自己,从而避免形成无限循环,避免产生栈溢出。

2. 栈

(stack)又称为堆叠,是计算机科学中一种特殊的串列形式的抽象资料型别,其特殊之处在于只能允许在连结串列或阵列的一端(top)进行加入数据(push)和输出数据(pop)的运算。另外栈也可以用一维数组或连结串列的形式来完成。

编程实现:

len(stack) != 0 — 判断stack是否为空

stack[-1] — 取栈顶元素,不移除

pop() — 移除栈顶元素并返回该元素

append(item) — 向栈顶添加元素

内建数据类型 list 实现栈的数据结构:

调用栈(call stack)

计算机在内部使用被称为调用栈的栈。

调用另一个函数时,当前函数暂停并处于未完成状态

递归调用栈

代价:存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存,如果栈很高,就意味着计算机存储了大量函数调用的信息。在这种情况下,你有两种选择。

重新编写代码,转而使用循环。

使用尾递归。另外,并非所有的语言都支持尾递归。

思考:尾递归的优化

3. 斐波那契数列和汉诺塔

斐波那契数列

思考:用递推法和矩阵法实现斐波那契数列

汉诺塔游戏

4. 小结

递归指的是调用自己的函数。

每个递归函数都有两个条件:基线条件和递归条件。

栈有两种操作:压入和弹出。

所有函数调用都进入调用栈。

调用栈可能很长,这将占用大量的内存。

END

一个好奇的探索者,

生命不息,折腾不止,Just do it!

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180528G11G3A00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券