說明
河內(nèi)之塔(Towersof Hanoi)是法國人M.Claus(Lucas)于1883年從泰國帶至法國的，河內(nèi)為越戰(zhàn)時(shí) 北越的首都，即現(xiàn)在的胡志明市;1883年法國數(shù)學(xué)家 EdouardLucas曾提及這個(gè)故事，據(jù)說創(chuàng)世 紀(jì)時(shí)Benares有一座波羅教塔，是由三支鉆石棒(Pag)所支撐，開始時(shí)神在第一根棒上放置64 個(gè)由上至下依由小至大排列的金盤(Disc) ，并命令僧侶將所有的金盤從第一根石棒移至第根三 石棒，且搬運(yùn)過程中遵守大盤子在小盤子之下的原則，若每日僅搬一個(gè)盤子，則當(dāng)盤子全數(shù)搬 運(yùn)完畢之時(shí)，此塔將毀損，而也就是世界末日來臨之時(shí)。
解法
A上有n個(gè)盤子。
一、如果n=1，則將圓盤從A直接移動到C。
二、如果n=2，則：
1）將A上的n-1（等于1）個(gè)圓盤移到B上；
2）再將A上的一個(gè)圓盤移到C上；
3）最后將B上的n-1（等于1）個(gè)圓盤移到C上。
如果n=3，則：
將A上的n-1（等于2，令其為n'）個(gè)圓盤移到B（借助于C），步驟如下：
1）將A上的n'-1（等于1）個(gè)圓盤移到C上。
2）將A上的一個(gè)圓盤移到B。
3）將C上的n'-1（等于1）個(gè)圓盤移到B。
B將A上的一個(gè)圓盤移到C。
C將B上的n-1（等于2，令其為n'）個(gè)圓盤移到C（借助A），步驟如下：
1）將B上的n'-1（等于1）個(gè)圓盤移到A。
2）將B上的一個(gè)盤子移到C。
3）將A上的n'-1（等于1）個(gè)圓盤移到C。到此，完成了三個(gè)圓盤的移動過程。
從上面分析可以看出
1、當(dāng)n=1時(shí)，將A移到C上
2、當(dāng)n大于等于2時(shí)， 移動的過程可分解為三個(gè)步驟：
第一步：把A上的n-1個(gè)圓盤移到B上；
第二步：把A上的一個(gè)圓盤移到C上；
第三步：把B上的n-1個(gè)圓盤移到C上；其中第一步和第三步是類同的。 當(dāng)n=3時(shí)，第一步和第三步又分解為類同的三步，即把n'-1個(gè)圓盤從一個(gè)針移到另一個(gè)針上，這里的n'=n-1。
