请问如何写出这题河内塔

题目:

    初始状态下有三根柱子 ,分别为 ABC 三支 ,当中 A 柱摆上将要搬移的碟子 ,碟子由上到下依小到大叠好 ,分别编上号码 1,2,3,4.... ,需将所有碟子全部搬移到 C 柱 ,规则为大碟不得摆在小碟上 ,也就是数字小者必须在前方
要求:

Input : 有几个环,由上而下为 1,2,.....,N
Output: 每一步的动作的结果(输出的要求是列出每一步骤后 ,各个柱子的情形 ,例:第一步由 A 搬 1 号碟到 C ,输出便是: A(2,3)B()C(1))
三根柱子由左至右为 A,B,C
example:

    Input : 2 (<-- 此数字为测试资料笔数)
              3 (<-- 第一组测试数 ..

访客只能看到部份内容，免费 加入会员

x0

参考一下，这是我觉得最简单可以理解的

http://tw.knowledge.yahoo.com/question/question?qid=1608110103848


试试看 高度(设为 h) h = 3, h = 4, h = 5..... 的河内塔你会发现一个规律

就是 h 为奇数时，第一个盘子都一定会先放到最右边 (假设一开始全部在左边)

h 是偶数时，第一个盘子一定会先放到中间


那么，你就可以发现其中的规律，你试着想想看，h = 3 的河内塔将 "最小的盘子" 移到最右边时

和 h = 4 河内塔将 "最上面的两个小盘子" 依照规律移动到 最右边时，把这两个小盘子 "群组化" 当成是一个小盘子






就会发现，h = 4 移动第三次与 h = 3 移动一次 的感觉是非常像的，这就是上面知识+提到 的想法

当河内塔其中一个杆子是空的时候，要移动比较小的那堆时，可以想像成，整个河内塔要移动的只有 那几个小盘子 (因为不管怎么移动这几个小盘子，都不会违反 小的要在大的上面)

例如，h = 4 时候，如上图下面的情况，要把最右边两个小盘子准备移动到 第二大的盘子(下一步骤 : 移动到中间杆子)


知道这个规律后，就能用 递回 (recursive) 或是一般的 回圈 来跑程式了

x0