抽象的意义

学习的困境

学习的最终目的是为了解决问题。可是我们经常发现,学习了很多东西,却不能解决面对的问题。

我们先看两个具体的案例。

代码:

# 将 N 个圆盘从 A 经过 BUFFER 移动到 C
def hano(n, A, buffer, C):
    # 基础情况
    if n == 1:
        print('%s --> %s'%(A,C))
    # 递归情况
    else:
        # 将前 n-1 个圆盘从 A 经过 C 移动到 buffer
        hano(n-1, A, C, buffer)
        # 将第 n 个圆盘从 A 移动到 C
        hano(1, A, buffer, C)
        # 将前 n-1 个圆盘从 B 经过 A 移动到 C
        hano(n-1, buffer, A, C)

汉诺塔:

汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

简单描述:将 A 上 N 个盘子经过 B 移动到 C。

  1. 首先考虑最简单的情况,A 柱上只有一个圆盘,这时候只需要将该圆盘从 A
    –> C 即可。
  2. 然后考虑 A 柱上有两个圆盘, 这时候需要将第一个圆盘 A –> B
    ,然后将第二个圆盘 A –> C ,最后 B –> C,就完成了移动。
  3. 关键一步,谨记递归的思想是不考虑细节。
  4. 现在有 N 个圆盘,我们需要将其分为两部分,第 N 个圆盘和第 N-1
    以上的圆盘,比如现在 N=4,那么就将圆盘分为 [4, (3,2,1)]
    两部分,按照第二步中的想法,我们的思想是 (3,2,1) 移动到 B,然后将 4
    移动到 C,最后将(3,2,1) 移动到 C 完成。
  5. 现在的问题是 (3,2,1) 并不是一个圆盘,我们要将 (3,2,1) 移动到
    B,就可以将此抽象为另一个汉诺塔问题,将 A 上 N-1 个盘子经过 C 移动到
    B。

案例二

在喜马拉雅山一些村庄的民宿里,有一种考究的茶道表演。这种表演需要一位主人和两名客人,不能多也不能少。当地的客人抵达并在桌边坐下时,主人会为他们表演三项节目。

这些节目的顺序是按照喜马拉雅人认为的高贵程度从低到高排列的:烧火、扇风、沏茶。在表演过程中,任何一个在场的人都可以问别人:“尊敬的先生,我可以为你表演这项节目吗?”值得注意的是,一个人只能向另一个人询问比他正在表演的项目高贵程度低的项目;其次,正在表演的人不能向人询问比他已经表演过的更加高贵的项目。习俗规定,茶道表演结束时,所有表演都要从主人转交给客人中较年长的那位。

请问,该如何操作呢?

“茶道表演”问题其实和下图所示的汉诺塔问题系出同门。

汉诺塔是根据一个传说形成的数学问题:

有三根柱子A,B,C。A柱上有N个穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C柱:

  • 每次只能移动一个圆盘;
  • 大盘不能叠在小盘上面。

    图片 1Hanoi
    Tower

主人和两位客人就像三根柱子,表演项目就像要从左传到右的三个圆盘。

从上面两个案例可以发现,现实中很多问题都在我们已知的范围内。关键是如何才能把现实问题映射/对应到已有的知识点上

解法:

所有的递归问题都由两部分组成: 基础情况 和 递归情况

  • 基础情况简单来说就是该递归函数的终点。汉诺塔的基础情况就是 A
    上只有一个圆盘时,将 A 移动到 C
  • 递归情况就是该递归函数继续递归的条件。递归情况就是 A
    上有不止一个圆盘,需要把该(些)圆盘经过 C 移动到 B

代码:

# 将 N 个圆盘从 A 经过 BUFFER 移动到 C
def hano(n, A, buffer, C):
    # 基础情况
    if n == 1:
        print('%s --> %s'%(A,C))
    # 递归情况
    else:
        # 将前 n-1 个圆盘从 A 经过 C 移动到 buffer
        hano(n-1, A, C, buffer)
        # 将第 n 个圆盘从 A 移动到 C
        hano(1, A, buffer, C)
        # 将前 n-1 个圆盘从 B 经过 A 移动到 C
        hano(n-1, buffer, A, C)

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*
*
Website