四柱汉诺塔之初步探究.docx

Acta Scientiarum NaturaliumUniversitatis Pekinensis , Vol . 40 , No . 1 (J an ,2004)四柱汉诺塔之初步探究杨楷徐川(北京大学计算机科学与技术系 ,北京 ,100871)摘 要 1941 年 ,J . S. Frame 在《美国数学月刊》上提出了一种解决四柱汉诺塔问题的算法 ,但未给出最终公式的证明 。本文按照这种算法总结出完成四柱汉诺塔游戏之最少步数的公式 ,并用数学 归纳法证明了它 。关键词 四柱汉诺塔 ; 区 ; 剩余盘数 R ( n)中图分类号 O 2240引言汉诺塔问题是一个古老的数学问题 。经典汉诺塔问题是三柱的 。它起源于印度 。意思是 :第一个柱 (A 柱) 上有 n 个碟子 ,从底向上碟子大小依次减小 ,目标是通过第二个柱 (B 柱) 把所有碟子移到第三个柱 ( C 柱) 上 ,但不能把大的碟子放到小的碟子上面 。三柱汉诺塔经典 算法是这样的 :首先用三柱汉诺塔经典算法把 A 柱上面的 n - 1 个碟子通过 C 柱移到 B 柱上 ,然后把 A 柱剩下的一个碟子移到 C 柱上 ,最后用三柱汉诺塔经典算法把 B 柱上所有的碟子通 过 A 柱移到 C 柱上1 。设完成 n 个碟子的三柱汉诺塔游戏需要移动的步数为 T ( n) ,则T ( n) = 2 × T ( n - 1) + 1 ,T (1)(1)= 1 。因此 ,T ( n) = 2 n - 1 。如果 n = 64 ,则 T (64) = 264 - 1≈11845 ×1019 步 。 四柱汉诺塔问题和三柱汉诺塔问题的惟一区别就是增加了一个柱 (D 柱) ,如图 1 所示 ,目标是把 A 柱上的 n 个碟子通过 B 柱和 C 柱移到 D 柱上 。虽然四柱汉诺塔只比三柱汉诺塔多 一个柱 ,但是解决它的难度远大于三柱汉诺塔 。四柱汉诺塔的 Frame 算法是这样的 :对于碟数为 n 的四柱汉诺塔 ,假定碟数 i 小于 n 时的算法已经确定 , i 个碟子的四柱汉诺 塔需要移动的步数为 F ( i) 。可把 A 柱上的碟子分成上 、下两部分2 。下部分共有 r 个碟子 , 上部分 n - r 个碟子 ,1 ≤r ≤n 。操作步骤如下 :① 用四柱汉诺塔 Frame 算法把 A 柱上部分的 n - r 个碟子通过 C 柱和 D 柱移到 B 柱上 ,需要 F ( n - r) 步 ;(2)收稿日期 : 2003202227 ; 修回日期 : 200320621099北 京 大 学 学 报 (自 然 科 学 版)第 40 卷② 用三柱汉诺塔经典算法把 A 柱上剩余的 r 个 碟 子 通 过 C 柱 移 到 D 柱 上 , 需 要T ( r) = 2 r - 1 步 ;③用四柱汉诺 塔 Frame 算 法 把 B 柱 上 的 n - r 个 碟 子 通 过 A 柱 和 C 柱 移 到 D 柱上 ,需要 F ( n - r) 步 ;据此 ,计算出总步数为 f ( n , r) ,随后对 所有的 r (1 ≤r ≤n) 逐一进行尝试 。选择一个 r 使得 f ( n , r) 取最小值 ,并定义此时的 r为R ( n) 。这样 ,就可以确定完成 n 个碟子的 四柱汉诺塔游戏需要的最少步数2 :图 1 四柱汉诺塔的图示Fig. 1 The illustrastion of 42peg Hanoi TowerF ( n) = min f ( n , r) = min[ 2 F ( n - r) + T ( r) ] = min[ 2 F ( n - r) + 2 r - 1 ] 。(3)rrr有关数据及公式根据上述算法 ,不难得到如下的数据 (见表 1) :表 1 R( n) 与 F( n)1根据表 1 的数据 ,作者猜想 : Table 1 R ( n) and F ( n) ·2 R ( n)F ( n)=n -+ 1 ,R ( n)F ( n)n(4)111 2 1 3 8 n + 1 - 1R ( n) = 1」其中。(5)34522259132本文的目的就是要证明 (3) , (5) ] (4) 。67893333172533412公式的证明从上面的表格不难看出 ,虚线按照公式 (5)将所有自然数 n 划分成区 ,每区中所有的 n 对应同一个 R ( n ) , 该区简称为 R 区 。如 n = 3 ,n = 4 和 n = 5 在同一个区 , R ( n) 都等于 2 。10111213444449658197证明 (3) , (5) ](4) 之前 ,先给出一个引理 。 14 4 113 1