第 7 集 · B1 · 7 分钟
C 语言 · 第7集 · 汉诺塔
从 Hello World、循环、递归讲到汉诺塔和动态规划，句子短，适合跟读。 开头：世界中心有一块青铜圆盘，上面固定着三根钻石柱。
中俄字幕
середины мира находится бронзовый диск, на котором укреплены три алмазных стержня
世界中心有一块青铜圆盘，上面固定着三根钻石柱。
высотой в один локоть и толщиной в пчелу.
高一肘尺，粗如蜜蜂。
Давным- давно, в самом начале времен, языческий бог Брахма возложил на них 64 диска,
远古时代，在时间之初，异教神祇梵天将64个圆盘置于这三根柱子上，
сделанных из чистого золота, причем так, что каждый меньший диск лежит на большем.
这些圆盘由纯金制成，且每个较小的圆盘都置于较大的圆盘之上。
Как только все 64 диска
一旦全部64个圆盘
будут переложены на другой стержень, башня вместе с храмом обратятся в пыль и под
被移到另一根柱子上，塔与寺庙将化为尘埃，
громовые раскаты погибнет мир.
并在雷鸣般的巨响中，世界将毁灭。
по крайней мере такую легенду придумал французский математик Эдуард Лука в 1883
至少，这是法国数学家爱德华·卢卡斯于1883年编造的传说，
году, когда изобрёл вот такую головоломку.
当时他发明了这样一款益智游戏。
Эта головоломка называется Ханойские башни.
这款益智游戏名为“汉诺塔”。
Ее правила таковы: перекладывать с одного стержня на другой можно только один диск,
其规则是：每次只能将一个圆盘从一个柱子移动到另一个柱子。
по одному диску.
每次只能移动一个圆盘。
Причем нельзя допускать вот такой ситуации, нельзя, чтобы диск большего диаметра
而且不能出现这种情况：即大直径圆盘放在小直径圆盘之上。
лежал на диске меньшего диаметра.
大直径圆盘不能放在小直径圆盘上。
Нужно организовывать перекладывание так, чтобы.
需要合理安排移动顺序，以确保……
все время диски меньшего диаметра лежали на большем.
所有时刻，小直径圆盘始终位于大直径圆盘之上。
Но при этом вот так можно вполне или вот так вот можно.
但此时这样放是可以的，或者这样放也可以。
То есть вот сейчас, например, для желтого диска открыт любой стержень, да, на любой.
例如，当前黄色圆盘可放置在任意柱子上，对吧？任意柱子都可以。
То есть вот эти диски сейчас для перекладывания него как бы не существуют.
也就是说，此刻这些圆盘对于它的移动而言，仿佛并不存在。
Они вот равносильны, их отсутствуют для него,
对它而言，这些圆盘等同于不存在。
для его перекладывания.
用于移动它。
Ну и собственно задачка какая?
那么，具体的问题是什么呢？
Переложить, я сейчас нарушу правила, переложить вот эти диски.
移动——我这就违规了——移动这些圆盘。
Ну их там вообще предполагается штук так восемь, да, у меня упрощенный вариант.
通常总共有八个圆盘，是的，我这里用的是简化版。
Я могу посложнее, но это лишнее время для нас.
我可以使用更复杂的版本，但那样会浪费我们的时间。
Переложить за кратчайшее время, соответственно, с первого стерженька, допустим, на
在最短时间内将圆盘从第一个柱子，比如移到
второй. Как нам поступить?
第二个柱子。我们该怎么做？
Ну вот, например, да, мы, очевидно, первый ход снять вот этот диск.
例如，显然第一步是取下这个圆盘。
Но куда его перекладывать, да?
但该把它移到哪儿呢？
Сюда или сюда?
移到这儿还是这儿？
Ну тут большой вопрос на самом деле.
嗯，这实际上是个大问题。
Вот я сейчас даже на память не помню, как правильно.
我现在甚至凭记忆都想不起来正确的做法。
Да, ну я вот предположу, давайте вот так вот.
是的，那我来猜一下，咱们就这么做吧。
А, скорее всего, я неправильно сделал, давайте вот, на раз.
啊，很可能我做错了，来，咱们重新开始。
сейчас не не не, а да нет нет нет прошу прощения этот.
现在不是……不是……不是……啊，对，不对、不对、不对，抱歉，是这个。
Да, кажется, всё.
是的，看起来都完成了。
Нет, неправильно.
不对，错了。
Я перекладываю вот так, вот так, дальше вот так, вот так, далее
我这样移动，这样，然后这样，这样，再往下……
вот так. Опа! Обратили внимание, вот этот момент ключевой, когда у меня самый
就这样！哎呀！请注意，这个时刻很关键：当我把最大的圆盘移到目标饼状物上时……
большой диск перекладывается на требуемый блинчик.
最大的圆盘移到目标饼状物上。
После этого я кладу, по моему, вот так.
之后，我把它放在这里，我觉得是这样。
да, не ошибся, все очень хорошо.
对，没错，一切都很好。
Ну вот у меня в итоге получилось все ровненько разложить, да?
那么，最后我就把所有东西都整齐地摆好了，对吧？
Но хотелось бы научиться делать это общим решением.
但我想学会用通用方法来解决这个问题。
И здесь нам поможет рекурсия.
这里，递归将帮我们解决问题。
чтобы построить общее решение, мы используем рекурсию.
为了构建通用解法，我们使用递归。
Каким образом?
具体怎么做？
Давайте рассмотрим перекладывание
我们来单独分析翻转操作。
отдельно. блинчика самого большого.
最大的那个煎饼。
и всех остальных.
以及其余所有煎饼。
Дело в том, что все остальные блинчики представляют из себя пирамиду высоты n минус
问题在于，其余所有煎饼构成一个高度为 n 减
1. Ну, если я считаю, что это n- ый блин.
1。嗯，如果我把这个算作第 n 个煎饼的话。
ну или диск. Соответственно, мне нужно переложить с первого на второй.
或者说是圆盘。相应地，我需要把它从第一个移到第二个。
Очевидно, что в качестве промежуточного я могу использовать третий.
显然，我可以把第三个作为中间过渡位置。
Давайте посмотрим, что из этого получается.
我们来看看结果如何。
Мне нужно переложить вот эту пирамидку высоты n минус 1 с
我需要把这座高度为 n 减 1 的小金字塔
первого диска на третий.
从第一个圆盘移到第三个。
Затем, что мне требуется?
接下来，我还需要做什么？
У меня диск самый большой находится еще на первом.
此时，最大的圆盘还在第一个位置上。
столбики штырьки, да?
这些柱子就是钉子，对吧？
пирамидка n минус 1 находится у меня на третьем штырьке.
n-1层的金字塔在我第三个柱子上。
я торжественно перекладываю вот этот вот, блин, я этот момент отметил, когда.
我郑重地把这一个移过去——哎呀，我特意记下了这个时刻。
делал это на головоломке, да?
我做这个谜题时，是这样做的，对吧？
Затем, что у меня получается, блин
接下来，我得到的结果是——哎呀，
размера n находится на втором штырьке, где и должен находиться, эта пирамидка
大小为n的圆盘在第二个柱子上，也就是它本该在的位置，这个金字塔
находится по- прежнему вот тут, где n минус 1, и я должен вернуть её, переложив, не
仍然在这里，即n-1所在的位置，我需要把它移回去，但不是
вернуть, в смысле, я переложить её с третьего столбика на второй столбик, ну и в
‘移回去’的意思是，我要把n-1从第三个柱子移到第二个柱子上，然后
результате получится, собственно, то, что мне требуется.
最终结果就正好是我所需要的。
Блин размера n сверху, пирамидка n минус 1, и они на втором штырьке.
大小为n的圆盘在上面，n-1层的金字塔在第二个柱子上。
Надо заметить, что задача свелась к подзадаче.
需要注意的是，这个问题已简化为一个子问题。
Но моя задача исходная была переложить пирамидку высоты n с первого на второй
但我的原始任务是将高度为n的金字塔从第一个柱子移到第二个柱子上。
штырёк, а подзадача оказалась немножко другой.
而子任务却略有不同。
В ней нужно перекладывать, точнее, их две подзадачи: пирамидку меньшей высоты, но с
它包含两个子任务：将一个较小高度的金字塔从第一个柱子移到第三个柱子上，
первого на третий столбик, да,
是的，
а потом с третьего на второй.
然后再从第三个柱子移到第二个柱子上。
Таким образом, для того чтобы сделать решение рекуррентным, мне нужно обобщить эту
因此，为了使解法具有递归性，我需要推广这个问题。
задачу. то есть мне нужно научиться перекладывать не с первого на второй,
也就是说，我需要学会的不是从第一个柱子移到第二个柱子，
а с итого на к- тый.
而是从第i个柱子移到第k个柱子。
ну тогда возникает вопрос а какой номер имеет вот этот вот третий столбец временный
那么问题来了：这个临时用到的第三个柱子编号是多少？
на который должна на время уйти пирамидка высоты на один меньше да n минус один.
那个暂时存放高度为n减1的金字塔的柱子。
да то есть это ид и это кат и а это что ну давайте назову его tmp вот этот номерочек
是的，也就是说这是 id，这是 cat，而这个是什么呢？嗯，我们把它叫做 tmp，就是这个编号。
временный tmp но как его вычислить на самом деле можно воспользоваться
临时的 tmp，但事实上，我们可以利用
простым и интересным инвариантом.
一个简单而有趣的不变量。
а именно обращая внимание что 1 плюс 2 плюс 3 равно 6.
具体来说，注意 1 加 2 加 3 等于 6。
очевидно что у меня i и k всегда будут разными номерками не важно 1 2 или 3 что там
显然，我的 i 和 k 的编号总是不同的，无论是 1、2 还是 3。
будет за i и k скрываться но я точно могу сказать что i плюс k плюс tmp
i 和 k 后面隐藏的具体数值是多少并不重要，但我可以确定的是，i 加 k 再加 tmp
равно 6 если я знаю i и k, то временный столбец имеет номер 6 минус i минус k.
等于 6；如果我知道 i 和 k，那么临时列的编号就是 6 减去 i 再减去 k。
Вот это вот основная формула, которая мне понадобится для использования, для
这就是我后续使用所需的核心公式。
вычисления номера промежуточного столбика.
计算中间柱子的编号。
на которое буду ссаживать пирамидку меньшего размера.
我将把较小的金字塔放在该柱子上。
Это рекуррентный случай, то есть то, что сейчас я описал, это по сути описание
这是递归情况，也就是说，我刚才所描述的，本质上就是一种描述
рекуррентного решения.
递归解法。
три действия на самом деле вот это это просто демонстрация результата
实际上只有三个动作，而这只是结果的演示。
действия фактически три а что такое крайний случай
实际上有三个动作，那么什么是边界情况？
来源：Тимофей Хирьянов · CC BY 3.0