四柱汉诺塔之初步探究

北京大学学报（自然科学版）

四柱汉诺塔之初步探究

杨楷, 徐川

北京大学计算机科学与技术系，北京，100871

收稿日期:2003-02-27 出版日期:2004-01-20 发布日期:2004-01-20

The Preliminary Probe of 4-Peg Hanoi Tower

YANG Kai, XU Chuan

Department of Computer Science and Technology, Peking University, Beijing, 100871

Received:2003-02-27 Online:2004-01-20 Published:2004-01-20

摘要/Abstract

摘要： 1941年，J.S.Frame在《美国数学月刊》上提出了一种解决四柱汉诺塔问题的算法，但未给出最终公式的证明。本文按照这种算法总结出完成四柱汉诺塔游戏之最少步数的公式，并用数学归纳法证明了它。

关键词: 四柱汉诺塔, 区, 剩余盘数R(n)

Abstract: In 1941,J.S.Frame gave out an algorithm in American Mathematical Monthly to solve the problem of 4-peg Hanoi Tower, but he did not provide the proof for the final formulae. According to that algorithm, this article puts forward a formula to calculate the number of movements necessary for the 4-peg Hanoi Tower problem, and proves it using mathematical induction.

Key words: 4-peg Hanoi Tower, zone, the number of remaining disks R(n)

中图分类号:

O224

杨楷, 徐川. 四柱汉诺塔之初步探究[J]. 北京大学学报（自然科学版）.

YANG Kai,XU Chuan. The Preliminary Probe of 4-Peg Hanoi Tower[J]. Acta Scientiarum Naturalium Universitatis Pekinensis.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: https://xbna.pku.edu.cn/CN/

https://xbna.pku.edu.cn/CN/Y2004/V40/I1/99

[1]	王彩红, 宋国富, 尼玛卓玛, 王永鹏, 赵矿. 西藏地区环境空气中PM₁₀和PM_2.5时空分布特征[J]. 北京大学学报自然科学版, 2025, 61(2): 195-205.
[2]	邓婉月, 范宾倩, 任重远, 李睿, 刘盈盈, 李丽明, 李媛, 耿春梅, 杨文. 伊犁河谷核心区工业园区挥发性有机物污染特征及环境影响[J]. 北京大学学报自然科学版, 2025, 61(2): 253-264.
[3]	闫纪元, 冯军, 张雪华, 李宁. 2024年1月23日新疆阿克苏地区乌什Ms 7.1级地震地表变形特征初步调查[J]. 北京大学学报自然科学版, 2025, 61(2): 388-402.
[4]	刘书同, 曹之炯, 蔡旭晖, 胡洵, 宋宇, 康凌. 太原地区近地面风场和大气输送特征分析[J]. 北京大学学报自然科学版, 2025, 61(1): 65-76.
[5]	张豪, 蒙吉军. 面向SDGs的喀斯特地区水土资源可持续性评估——以贵州省为例[J]. 北京大学学报自然科学版, 2025, 61(1): 139-152.
[6]	张朝鲲, 田伟, 何衍鑫, 朱伟鹏, 李舜. 1.32 Ga基性岩床侵位的环境效应探究[J]. 北京大学学报自然科学版, 2024, 60(6): 1067-1078.
[7]	张合, 蒋一然, 王虹宇, 温景充, 宁杰远. 雄安新区壳幔结构揭示的大陆岩石圈改造模式[J]. 北京大学学报自然科学版, 2024, 60(6): 1079-1093.
[8]	郑强, 杨彬云, 相云, 郑成洋. 雄安新区千年秀林土壤水分变化规律的研究[J]. 北京大学学报自然科学版, 2024, 60(6): 1123-1130.
[9]	张豪, 习皓, 龙嘉骞, 郑秋月, 冯长春. 北京市绿隔地区生态环境质量变化与驱动因素分析——以“基于自然的解决方案”为视角[J]. 北京大学学报自然科学版, 2024, 60(5): 935-944.
[10]	刘炜, 刘梦姿, 龚岳, 阙槿楠, 郭传民. 西方城市规划对居住分异的影响及其启示[J]. 北京大学学报自然科学版, 2024, 60(5): 945-956.
[11]	梁丽娜, 王洪佳, 冯慧懿, 唐秀美. 基于多源数据的北京生态涵养区生态产品供给与经济发展耦合协调度研究[J]. 北京大学学报自然科学版, 2024, 60(4): 713-722.
[12]	朱国营, 赵昕奕. 1981—2020年中国风速变化及其与大气环流的关系[J]. 北京大学学报自然科学版, 2024, 60(3): 431-441.
[13]	李能韬, 周庭红, 黄宝春. 中国新疆地区考古陶片的古地球磁场强度研究[J]. 北京大学学报自然科学版, 2024, 60(3): 503-512.
[14]	白璐, 关平, 呼其图, 宋丹丹. 五台地区高凡群沉积年代、物源性质与构造环境[J]. 北京大学学报自然科学版, 2024, 60(2): 210-226.
[15]	张志亮, 曾琪明, 杨立功. 利用结合土地覆盖类型的自适应DS-InSAR方法监测矿区地表形变[J]. 北京大学学报自然科学版, 2024, 60(2): 265-276.