四柱汉诺塔之初步探究

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

四柱汉诺塔之初步探究

杨楷, 徐川

北京大学计算机科学与技术系，北京，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.

[1]	白璐, 关平, 呼其图, 宋丹丹. 五台地区高凡群沉积年代、物源性质与构造环境[J]. 北京大学学报自然科学版, 2024, 60(2): 210-226.
[2]	张志亮, 曾琪明, 杨立功. 利用结合土地覆盖类型的自适应DS-InSAR方法监测矿区地表形变[J]. 北京大学学报自然科学版, 2024, 60(2): 265-276.
[3]	向岚麟, 张君楚, 闫禹涵, 马贝贝. 社会感知数据表征下的历史文化街区地方感变迁——以南锣鼓巷(2008—2022年)为例[J]. 北京大学学报自然科学版, 2024, 60(2): 289-305.
[4]	王江月, 田佳, 周正暘, 马晓昀, 龙玉, 王戎疆, 李晟. 利用生物声学指标评估暗针叶林鸣禽围攻事件中的鸣声特征[J]. 北京大学学报自然科学版, 2024, 60(1): 118-126.
[5]	韩西丽, 张心悦. 城市公园正式及非正式运动场地体力活动特征研究——以深圳市为例[J]. 北京大学学报自然科学版, 2023, 59(6): 981-990.
[6]	王楠, 郝晋珉, 星野敏, 田玉福. 黄淮海平原农村产业结构与用地结构关系研究——以曲周县为例[J]. 北京大学学报自然科学版, 2023, 59(5): 801-812.
[7]	陈文华, 徐娟. 中国西南鸟类物种丰富度及其维持因素研究[J]. 北京大学学报自然科学版, 2023, 59(4): 629-638.
[8]	郑毅权, 雷军. 腾冲地区中小震群横波分裂到时差变化研究[J]. 北京大学学报自然科学版, 2023, 59(3): 375-387.
[9]	张豪, 冯长春, 郭永沛. 城市边缘区“三生”空间格局演变与驱动因素分析——以北京市朝阳区为例[J]. 北京大学学报自然科学版, 2023, 59(3): 478-488.
[10]	桂智明, 孙忠祥, 黄舟. 区块链与数据库混合架构下的空间查询优化方法[J]. 北京大学学报自然科学版, 2023, 59(2): 261-270.
[11]	蒲金芳, 刘沙沙, 温良友, 高阳, 王数. 江南丘陵区农村居民点多功能空间特征与分区优化[J]. 北京大学学报自然科学版, 2023, 59(2): 271-280.
[12]	张峰, 陆思华, 李丛益, 邵敏, 李悦, 吕大器, 李歆, 刘莹. 石化工业区中等挥发性有机物排放特征[J]. 北京大学学报自然科学版, 2023, 59(2): 281-289.
[13]	高山松, 李秋根, 胡鹏月, Yasin Rahim, 李泓莹. 华北克拉通恒山地区晚太古代变质火山岩的地球化学特征及构造意义[J]. 北京大学学报自然科学版, 2023, 59(1): 143-160.
[14]	戴林琳, 余璇, 吕晋美. 面向空间管控的村庄分类方法与实践——以天津市武清区为例[J]. 北京大学学报自然科学版, 2022, 58(6): 1121-1129.
[15]	任磊, 杨凡, 杨凌娜, 陈晓帆, 潘广维, 韦骏. 基于高频地波雷达观测的粤港澳大湾区春季海表流特征研究[J]. 北京大学学报自然科学版, 2022, 58(5): 839-849.