一.算法背景 最早发明这个问题的人是法国数学家爱德华·卢卡斯.传说越南河内某间寺院有三根银棒(A, B, C),上串 64 个金盘. 寺院里的僧侣依照一个古老的预言,以上述规则移动这些盘子:预言说当这些盘子移动完毕,世界就会灭亡. 这个传说叫做梵天寺之塔问题(Tower of Brahma puzzle).但不知道是卢卡斯自创的这个传说,还是他受他人启发. A C B 二.汉诺塔算法 有三根杆子A,B,C.A 杆上有 N 个 (N>1) 穿孔圆盘,盘的尺寸由下到上依次变小.要求按下列规则将所有圆
题目链接:https://www.lintcode.com/problem/tower-of-hanoi/description 题目大意 经典递归问题. 分析 由于是经典问题了,这里不讨论用递归实现,也不讨论用栈模拟实现,只讨论纯迭代实现. 首先用 L, M, R 来标记左柱子,中柱子,右柱子. 我们知道汉诺塔问题与二进制是密不可分的,“n-圆盘汉诺塔问题”最少只需要$2^n - 1$步,而且如果 n 为奇数,第一步必然是 L->R:如果 n 为偶数,第一步必然是 L->M. 现在我们定义三
using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace MyExample_Hanoi_{ class Program { static void Main(string[] args) { HanoiCalculator c = new HanoiCalculator(); Cons