正领老师讲解|高数/数竞同学戳这里:适用于解决FP、STEP问题的一种通用思路
2022-01-07 正领国际教育

FP难题不会解?STEP难题无从下手?

别着急,本文先带你解析思考一类递归问题的通用方法,需要抽出一点时间集中精力阅读,如时间有限可先收藏后看哦~

递归问题带来的启发:汉诺塔问题

我们首先来看一个小的谜题,汉诺塔问题,它由法国数学家卢卡斯(Edouard Lucas)于1883年发明。

01.jpg

有三个空柱子,最左侧的柱子上叠放着从小到大8个圆盘,圆盘的大小从上到下依次递增,如上图所示。

我们的目标是将所有的圆盘从最左侧的柱子移动到最右侧的柱子上,但有两个要求:一次只移动一个圆盘,小的圆盘必须落在大的圆盘上方。

我们的问题是:至少需要多少步才能将所有8个圆盘移到最右边的柱子上?

卢卡斯甚至将他发明的谜题包装成了一个印度的古老传说:梵天塔。印度教的主神梵天在创造世界的时候,在一块黄铜板上插着三根钻石针,并在其中一根针上从下到上地穿好了由大到小的64片金片。不论白天黑夜,总有僧侣在移动这些金片:一次只移动一片,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

回到问题中来,对于这类问题,我们不妨将其推广到n个圆盘的情况,这样做的一个好处是可以进一步减小问题的规模。

求解的第一步是建立直觉,而直觉往往是通过先看小的数字得到的。通过少量实验,可以很容易得知只有2~3个圆盘时所需要的步数。

01.jpg

*因无法编辑某些数学符号,以下讲解截图至郭老师文章内容。

01.jpg

汉诺塔问题是一类典型问题的代表。通过汉诺塔问题的研究,我们得到了解决求通项公式的一种通用思路:

1. 看小的数字的情况:解决规模小的问题可以帮助我们理解问题的本质

2. 发现并证明递推公式:建立大数字与小数字之间的联系

3. 发现并证明通项公式:用递推公式计算小的数字,猜想通项公式,并用数学归纳法证明

好了,这期的内容就是这些。如果觉得有用,记得分享给身边需要的人,我们下期见!

上一篇:老师课堂| 提升雅思口语流利度的小妙招! 下一篇:老师课堂|伦敦政经(LSE)最热商科介绍!