第三夜 · 神庙之夜的汉诺塔灯又亮了。第三夜。这一夜不回那间教室。上一夜散场我带走的是那个归字。递是出发归是回家接不归的棋救不回。可是回去的路上我一直在想这句话的后半截。既然要回家那条回家的路有多长这个问题一段 4 岁的故事先替我起了个头。从前有座山山里有座庙庙里有个老和尚在给小和尚讲故事。讲的什么讲的还是从前有座山山里有座庙庙里有个小和尚在听老和尚讲故事。再往里讲一层还是它自己。故事套着故事层与层一模一样全都是同一座山同一座庙同一个讲不完的老和尚。大人们拿这段话哄孩子。孩子缠着要听故事大人不肯编新的就递出这座山。孩子安静了因为这段故事真的没有底。不是讲的人偷懒是它本来就没打算讲完。下一层和上一层一模一样只是听故事的人更小夜更深。你随时可以走开故事不怪你。故事里那个小和尚到今天还在听。我第一次在两面镜子中间见到这段故事是在三年级。那天跟着外婆和舅舅一家人逛江苏省科技馆展厅里立着两面相对的镜子。外婆那时是物理老师她把我拉到两面镜子中间给我讲镜面反射讲镜面成像。我往前一看镜子里套着镜子我自己一层一层退下去越来越小越来越小朝着最深处退过去。所有的一切最后都消散在透视的原点缩成一个黑点。外婆在旁边讲她的原理我在那个黑点跟前看了很久。镜里的像无穷无尽人的视野却是有穷的。无穷的像走到有穷的视野尽头就只剩下那一个点。道理上镜子后面还有镜子像的后面还有像无限就站在那里站得端端正正。可我亲眼看见那无穷无尽的像最终消散在透视点处收成一个黑点。无穷是镜子的事有穷是看的人的事。后来我学递归才知道镜子其实很客气。上一夜那口井塌在第 22835 层不是运气差。镜子再深最深处的无穷最后收成安安静静一个黑点挂在透视的原点上。递归不这么客气。递归写坏了尽头不是黑点是黑洞什么掉进去当场爆炸。庙里的故事一层套一层镜子里的像一层退一层怎么套怎么退都有一个原点替它们收尾递归收不住的时候没有谁替它收尾。所以机器收下递归的那一刻同时递过来一把尺。写递归的人得先接住这把尺再去谈无限。好了。现在让老和尚开口。这一回他不再讲那座山了。他说从前恒河边上有一座庙。庙不稀奇稀奇的是庙里那桩差事。庙里立着三根柱子通体是宝石磨的。其中一根柱子上套着六十四片金盘最大的在底下越往上越小摞成一座塔。庙里的僧侣们领了差事要把这座塔从这根柱子搬到另一根柱子上去。规则只有两条。其一一次只许挪一片。其二无论什么时候大片不许压在小片上。僧侣们领了差事日复一日地搬。金盘一片一片换柱钟声一天一天响着塔还是那座塔模样没变。传说讲到这里露出了牙。它说等最后一片金盘落位的那一天这个世界就到了尽头。这个故事你多半听过。听过也不要紧编它的人就盼着你听。1883 年法国数学家吕卡斯做出了这个玩具又亲手写下这段传说一并印在说明书里。玩具卖遍了欧洲传说跟着走遍了世界一百多年后还住进了每一本编程教材。讲传说的书自己讲的传说也是编的。这一夜的庙两层都是编的。这一笔我不瞒你照实记在夜末的核对表里像第一夜把牛顿的名字还回去一样。预言归预言。现在把预言翻译成算术。搬一片算一步。想把最大的那片从甲柱挪到丙柱得先把压在它上面的六十三片整个搬到乙柱去等它落了位再把六十三片从乙柱请回来。搬六十三片是同样的麻烦得先搬六十二片。这样一层一层想下去每加深一片功夫翻一倍再加一。一片要一步两片要三步三片要七步十片要一千零二十三步。六十四片一共是 2⁶⁴ 减 1 步。18446744073709551615。每秒挪一片不吃饭不睡觉不过节这个数折合 5849 亿年。宇宙到今天 138 亿岁。僧侣们要连搬上四十二个宇宙的年纪才能听见最后一片金盘落位的那一声轻响。这个数的分量得拿人生去称。三片的小庙七步搬完每一步都画在下面这张图里。二十片要十二天一个下午变成了两个星期。三十片要三十四年动手的小伙子搬成了老汉。四十片要三万五千年长过全部文字的历史。五十片要三千五百多万年长过整个人类物种的年纪。六十四片5849 亿年。预言没有说谎它只是把日程表的最后一行写在了谁也等不到的年份里。图 3-1 三片金盘的七步搬法。灰色加粗的盘是这一步正在挪动的那片。从初始到第 7 步塔从甲柱完整落到丙柱任何时候都没有大片压住小片。第 6 步之后乙柱空了最省的搬法也不必用上每一根柱。预言翻完了。接下来这一位才是真正吓过数学家的。1872 年柏林。威尔斯特拉斯当着科学院摆出一条曲线处处连着却处处立不起切线。要知道那个年代的数学家默认连续的曲线总该有光滑的段落好比人人都默认山总有坡度缓的一段。这一条没有。它处处连着却寸步难滑。分析学界哗然埃尔米特在信里自陈怀着恐惧与惊骇避开这场可悲的瘟疫。三十二年之后科赫用一把直尺和初等几何把这群怪物里最驯顺的一只牵到了每个人眼前。就是下面这片雪花。从一片正三角形开始。把每条边三等分中间那一段向外顶成一片尖角尖角自己也是一个小三角形。第二层对着现有的每一条边再做一遍同样的事。第三层再来。图形越磨越碎越磨越像冬夜窗上的霜花。本夜的程序亲手把它磨了一遍从零层磨到三层画在下面。图 3-2 科赫雪花的头四层。从左到右打磨了零、一、二、三层。图是本夜的程序自己画出来的代码附在夜末。磨到无穷多层这片雪花的面积停在最初那片三角形的一又五分之三倍封了顶一步也不再走。它的周长却是另一副脾气。每磨一层周长变成上一层的 4/3 倍。乘一个比一大的数乘个不停周长通向无限。一片巴掌大的雪花镶着一条走不完的边。这一次是真的走不完。不是走很久是定义本身就到不了。这才是无限本来的脸色。可是没有人怕雪花。没有人怕因为没有人真的去走那条边。走不完写在定义里谁也不欠它一步。庙里那条路正相反。六十四片片片数得清步步都要人挪每一步都真实存在。让世界惦记了一百多年的从来不是无限是一个每一位都写得出来的大数。真无限反倒和善吓人的是数得出来的有限。老和尚的故事讲到这里本该收尾了。这一回插话的是小和尚。师父庙里为什么只有三根柱子老和尚不答。传说只发三根柱子不发为什么。小和尚又问那我能不能先把头顶的小塔整座寄存到别的柱子上腾出手来搬底下的大山等大山落了位再回来取小塔老和尚还是不答。庙里只有三根柱子第四根柱子传说没有发。可是山下的世界不归传说管。1941 年大西洋彼岸的一本数学杂志上Frame 和 Stewart 把第四根柱子插进了庙里。两人素不相识文章登在同一卷、相邻的两页交来的却是同一套搬法。先把头顶的小塔整座寄存到第四根柱上。寄存几片最省这个问题自己又是一道递归。腾出手来用老三柱的功夫把底下的大山搬完。最后回到第四根柱上把小塔请回来盖在大山的顶上。六十四片金盘四根柱子18433 步。一秒挪一片五个小时零七分。日头升起来的时候僧侣们动手日头还没偏西塔落成了世界好好的。压在世界头顶的末日被多出来的那根柱子改期到了当天晚饭前。可是 1941 年没有人敢把话说满。这套搬法是不是天下第一省Frame 和 Stewart 都没有证明。往后的七十三年里它一直顶着一个头衔叫据信最省。全世界最会算的一批人试了一辈子没能证明它是也没能找到更省的。直到 2014 年法国数学家布歇把它钉死了。第四根柱子上那套搬法就是最省的搬法。柱子 1941 年就插好了承认它的那句话在路上走了七十三年。北山愚公说过子子孙孙无穷匮也。河曲智叟笑他他就拿这句话作答。山不会再长高子孙却没有尽头一茬接一茬地挖总有一天挖平。这个道理在许多年后有了名字叫数学归纳法。只是愚公的两座山最后是天帝派夸娥氏二子背走的神替他收了尾。恒河边的庙没有神来。金盘要僧侣一片一片地搬第四根柱子要人一代一代地想从 1941 年一直想到 2014 年。有一句话我想原样放在这一夜里。人是不能打破规律的但是看透规律之后我们能做出更好的选择。大盘不压小盘一次只挪一片谁也改不了也不必改。多一根柱子多一层寄存多一步回头末日就改期了。规则没有被打破被看透了。庙里的僧侣不知道自己在倒数什么。他们不数日子只数手边这一片。世界没有在倒数僧侣们在慢慢搬再长的路也是一步一步走完的。这一夜我把庙写成了三段能跑的程序。第一段替僧侣数数小塔数到七步大塔数到钟声里。第二段插上第四根柱子。第三段磨雪花图就是它画的。你要是不信末日会改期、周长没有底自己跑一跑数一数。第一段 · 庙里的钟三柱import java.io.PrintStream; import java.math.BigInteger; /** * 《算法一千零一夜》第三夜 · 庙里的钟三柱 * 恒河边的庙三根柱六十四片金盘大盘在下小盘在上。 * 规则只有两条一次挪一片大片不压小片。 * 传说讲最后一片金盘落位之日世界终结。 * 这一版按最省的搬法替僧侣数数小塔一步步看得见大塔一声钟数得完。 */ public class TempleBells { static int moves 0; // 递是把塔交给更小的塔归是一片落位钟响一声。 static void move(int n, String from, String to, String via) { if (n 0) { return; // 零片可搬这一层到家。 } move(n - 1, from, via, to); // 先把上面的塔寄存到中途柱。 moves; if (n 3) { System.out.println(第 moves 步 n 号盘 from 柱到 to 柱。); } move(n - 1, via, to, from); // 再把寄存的塔请回来盖在大盘上。 } public static void main(String[] args) throws Exception { System.setOut(new PrintStream(System.out, true, UTF-8)); // 一、小庙演示。三片金盘七步与图 3-1 逐步核对。 System.out.println(三片金盘从甲柱搬到丙柱); move(3, 甲, 丙, 乙); System.out.println(三片共 moves 步。); System.out.println(); // 二、大庙钟声。每加深一片功夫翻倍再加一1、3、7、15、31…… BigInteger steps BigInteger.ONE; for (int n 2; n 64; n) { steps steps.shiftLeft(1).add(BigInteger.ONE); } System.out.println(六十四片金盘一共 steps 步。); BigInteger perYear BigInteger.valueOf(365L * 24 * 60 * 60); // 一年按 365 天不闰。 BigInteger years steps.divide(perYear); System.out.println(每秒搬一片约 years 年约合 5849 亿年。); BigInteger universe BigInteger.valueOf(13800000000L); // 宇宙现龄约 138 亿年。 System.out.println(这个年头约是宇宙现龄的 years.divide(universe) 倍。); } }第二段 · 第四根柱子四柱import java.io.PrintStream; import java.math.BigInteger; /** * 《算法一千零一夜》第三夜 · 第四根柱子四柱 * 1941 年Frame 与 Stewart 在同一本杂志的同一卷里 * 各自给庙里插上了第四根柱子先寄存小塔搬完大山再回来取塔。 * 寄存几片最省这个问题自己又是一道递归。本程序替小僧把它数完。 */ public class FourthPeg { public static void main(String[] args) throws Exception { System.setOut(new PrintStream(System.out, true, UTF-8)); // f(n) 是四根柱搬 n 片的最省步数。 // 搬法寄存 k 片到第四根柱三根柱搬完剩下的 n-k 片再取回小塔。 // f(n) min over 1 k n { 2*f(k) 2^(n-k) - 1 }。寄存几片最省问 n 自己。 BigInteger[] f new BigInteger[65]; f[1] BigInteger.ONE; // 一片一步。 for (int n 2; n 64; n) { BigInteger best null; for (int k 1; k n; k) { BigInteger plan f[k].shiftLeft(1) // 寄存一次取回一次。 .add(BigInteger.ONE.shiftLeft(n - k).subtract(BigInteger.ONE)); // 三柱搬大山。 if (best null || plan.compareTo(best) 0) { best plan; } } f[n] best; } StringBuilder head new StringBuilder(); for (int n 1; n 10; n) { head.append(f[n]); if (n 10) { head.append(、); } } System.out.println(四柱搬 n 片的最省步数前十项 head); System.out.println(六十四片四根柱子共 f[64] 步。); long secs f[64].longValue(); // 18433装得下。 System.out.println(每秒一片约合 secs / 3600 小时 secs % 3600 / 60 分 secs % 60 秒。); BigInteger three BigInteger.ONE.shiftLeft(64).subtract(BigInteger.ONE); System.out.println(同一座塔三根柱要 three 步四根柱只要 f[64] 步。); } }第三段 · 雪花的画笔科赫import java.awt.BasicStroke; import java.awt.Color; import java.awt.Graphics2D; import java.awt.RenderingHints; import java.awt.image.BufferedImage; import java.io.File; import java.io.PrintStream; import javax.imageio.ImageIO; /** * 《算法一千零一夜》第三夜 · 雪花的画笔科赫 * 从一片正三角形开始每条边的中间三分之一向外顶出尖角 * 层层打磨。面积封了顶周长没有底。 * 这一版一边打磨一边画图就是程序自己画的。 */ public class KochSnowflake { // 递是把一条边交给四条更短的边归是 depth 用尽落笔画直线。 static void koch(Graphics2D g, double x1, double y1, double x2, double y2, int depth) { if (depth 0) { g.drawLine((int) Math.round(x1), (int) Math.round(y1), (int) Math.round(x2), (int) Math.round(y2)); return; } double dx (x2 - x1) / 3, dy (y2 - y1) / 3; double ax x1 dx, ay y1 dy, bx x1 2 * dx, by y1 2 * dy; // 尖点底边中点向图形外侧顶起一个等边三角。屏幕坐标 y 朝下外侧法线取-dy3, dx3。 double mx (ax bx) / 2 - (by - ay) * Math.sqrt(3) / 2; double my (ay by) / 2 (bx - ax) * Math.sqrt(3) / 2; koch(g, x1, y1, ax, ay, depth - 1); koch(g, ax, ay, mx, my, depth - 1); koch(g, mx, my, bx, by, depth - 1); koch(g, bx, by, x2, y2, depth - 1); } public static void main(String[] args) throws Exception { System.setOut(new PrintStream(System.out, true, UTF-8)); // 一、画。四联图从左到右磨了零、一、二、三层。 int W 1600, H 400; BufferedImage img new BufferedImage(W, H, BufferedImage.TYPE_INT_RGB); Graphics2D g img.createGraphics(); g.setColor(Color.WHITE); g.fillRect(0, 0, W, H); g.setColor(new Color(0x22, 0x22, 0x22)); g.setStroke(new BasicStroke(1.6f)); g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON); double edge 200; for (int i 0; i 4; i) { double cx 200 i * 400; // 每格中心。 double h edge * Math.sqrt(3) / 2; double ax cx, ay 190 - h / 2; // 顶点朝上的正三角形。 double bx cx - edge / 2, by 190 h / 2; double cx2 cx edge / 2, cy2 190 h / 2; int depth i; koch(g, ax, ay, bx, by, depth); koch(g, bx, by, cx2, cy2, depth); koch(g, cx2, cy2, ax, ay, depth); } ImageIO.write(img, png, new File(fig3-2-koch.png)); System.out.println(四联图已画完落在 fig3-2-koch.png。); // 二、数一数。周长每层乘 4/3面积每层只添一点点。 double area0 Math.sqrt(3) / 4; // 边长 1 的正三角形。 double perimeter 3.0; double area area0; double newCorners 3; // 这一层新添的尖角个数。 double seg 1.0 / 3; // 尖角的边长。 System.out.println(层 0周长 3 倍面积 1 倍。); for (int n 1; n 9; n) { perimeter perimeter * 4 / 3; area newCorners * Math.sqrt(3) / 4 * seg * seg; newCorners * 4; seg / 3; System.out.printf(java.util.Locale.ROOT, 层 %d周长 %.3f 倍面积 %.4f 倍。%n, n, perimeter, area / area0); } } }---① 真伪核对逐条照实登记。Ⅰ 吕卡斯与传说 汉诺塔玩具由法国数学家吕卡斯于 1883 年推出上市时署名 N. Claus de Siam这个名字是他本名加家乡Lucas dAmiens亚眠的字母变形东方的皮是营销的包装神庙传说出自这套包装三根柱、六十四片金盘、搬完世界终结全是编的。Ⅱ 数字与换算 三柱六十四片共 2⁶⁴ 减 1 步即 18446744073709551615 步每秒一片、一年按 365 天折合 5849 亿年为本夜程序实跑输出宇宙现龄约 138 亿年倍数约 42。Ⅲ 四柱 1941 年 Frame 与 Stewart 在 American Mathematical Monthly 第 48 卷 216 至 219 页各自独立发表四柱搬法四柱六十四片最少 18433 步为本夜程序按 Frame-Stewart 递推实跑所得2014 年布歇Thierry Bousch证明这个递推给出的正是最少步数论文 La quatrième tour de Hanoï 载于 Bulletin of the Belgian Mathematical Society – Simon Stevin 第 21 卷第 5 期895 至 912 页。坊间另有此文载于法国数学会通报第 142 卷的引法系以讹传讹那是它 2013 年预印本旧题目惹的祸。Ⅳ 雪花 科赫 1904 年论文的题目直译过来是用初等几何构造的一条无切线的连续曲线雪花面积收敛于初始三角形面积的 8/5周长每层乘 4/3均经本夜程序实跑核对。威尔斯特拉斯于 1872 年 7 月 18 日在柏林科学院报告此曲线埃尔米特 1893 年致斯蒂尔杰斯的信里自陈怀着恐惧与惊骇避开这场可悲的瘟疫。Ⅴ 庙循环与愚公 从前有座山系民间口传作者与年代不可考如今是讲解无限递归时的常用例子。愚公引文出自《列子·汤问》原文为子子孙孙无穷匮也而山不加增结尾是帝感其诚命夸娥氏二子负二山。Ⅵ 实跑记录 三段程序均在本机 JDK 21 下编译运行三片七步与图 3-1 逐格一致四柱前十项为 1、3、5、9、13、17、25、33、41、49六十四片 18433 步折合 5 小时 7 分 13 秒雪花第九层周长约为初始三角形周长的 13.3 倍面积 1.5996 倍正向 8/5 收敛。Ⅶ 亲历登记 科技馆一节是亲历。三年级那年跟外婆和舅舅一家人逛江苏省科技馆外婆那时是物理老师镜面反射与成像的原理是她讲的两面镜与透视原点的黑点都是当年的实景。黑点的机理是每折一次光就折损一分深处渐暗最终收成一个点递归那边没有这份收敛栈溢出当场终止程序即正文所说的黑洞第二夜那口井实跑塌在第 22835 层照实登记。② 关于证明正文只留了七十三年一句话证明放在这里。Ⅰ 三柱的步数为什么省不掉 想让最大的那片动身压在它上面的 n 减 1 片必须全部让开而它要落的那根柱子必须腾空于是这 n 减 1 片只能全体挤进剩下那一根柱。让路的功夫一步都省不掉所以三柱的最少步数至少是搬 n 减 1 片的两倍再加一而搬法恰好做到这个数$T(n)2^n-1$ 就此锁死。Ⅱ 四柱为什么难了七十三年 让路的队伍一旦可以分成两批小塔去第四根柱大山直接走让路的成本就不再服从三柱的公式上面的下界证明当场断裂。算法 1941 年就有难的从来不是省是证明没有更省的。Ⅲ 布歇走的是图的路 把每一个合法局面画成一个点每挪一片画一条边全体局面连成一座巨大的图两座塔之间的最短距离就是最少步数。布歇量清了这座图的距离结构证明 Frame-Stewart 的数恰好就是那个距离。2014 年下界闭合七十三年的门开了。Ⅳ 两条式子留档 $T(n)2^n-1$。$S(n)\min_{1\le kn}\{2S(k)2^{n-k}-1\}$。③ 今夜习题三道评论区见。Ⅰ 小庙里的金盘只有一小摞。僧侣们按最省的搬法搬完了它一共 1023 步。这一摞有几片金盘Ⅱ 方丈给小庙添了第四根柱子。五片金盘从一根柱子搬到另一根柱子最少几步同样的五片三根柱子要多少步Ⅲ 从一片正三角形开始打磨雪花每打磨一层周长变成上一层的 4/3 倍。打磨几层之后周长第一次超过最初那片三角形周长的 10 倍你算出来了吗评论区见。答案与参考程序收在书后《参考解答》。版权声明本文为作者原创受著作权法保护。未经授权禁止转载、搬运、摘编、改编及任何形式的二次创作个人学习引用请注明作者与原文出处。转载授权请联系作者CSDN 私信。侵权必究。