汉诺塔问题的深入探讨

A PROFOUND INQUIRY INTO THE HANOI PROBLEM

汉诺塔问题古老而有趣,是经常用作程序设计递归算法的典型例题。澳大利亚M·C·Er论证了单向移动的若干性质,并给出了相应迭代算法。但他在论述对称性时,隐含删去无效移动;而计算移动次数时又默认无效移动的存在,两者互相矛盾。本文以删除无效移动为出发点,严格论证了单向汉诺塔移动的对称性与唯一性,同时证明了各种移动序列可以相互变换。

Hnaoi Problem is an old-aged yet interesting one,which is often used as an typical example for recursive algorithm in program design. M. C. Er of Australia has made some arguments on the characteristics of one-way movement and put forward the corresponding iterative computation. However,while he has implicitly deleted the invalid movement in expounding symmetry,he gives tacit consent to the existence of such movement in calculating the number of movement occurred, which presents a contradiction. This paper,taking the deletion of invalid movement as a starting point,strictly proves the symmetry and unicity of one-way Hanoi movement as well as the exchangeability between various moving sequences.