漢諾塔問題，是心理學(xué)實(shí)驗(yàn)研究常用的任務(wù)之一。該問題的主要材料包括三根高度相同的柱子和一些大小及顏色不同的圓盤，三根柱子分別為起始柱A、輔助柱B及目標(biāo)柱C。

相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上，有三根桿(編號(hào)A、B、C)，在A桿自下而上、由大到小按順序放置64個(gè)金盤(如圖1)。游戲的目標(biāo)：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好。操作規(guī)則：每次只能移動(dòng)一個(gè)盤子，并且在移動(dòng)過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于A、B、C任一桿上。

分析：對(duì)于這樣一個(gè)問題，任何人都不可能直接寫出移動(dòng)盤子的每一步，但我們可以利用下面的方法來(lái)解決。設(shè)移動(dòng)盤子數(shù)為n，為了將這n個(gè)盤子從A桿移動(dòng)到C桿，可以做以下三步：

(1)以C盤為中介，從A桿將1至n-1號(hào)盤移至B桿；

(2)將A桿中剩下的第n號(hào)盤移至C桿；

(3)以A桿為中介；從B桿將1至n-1號(hào)盤移至C桿。

這樣問題解決了，但實(shí)際操作中，只有第二步可直接完成，而第一、三步又成為移動(dòng)的新問題。以上操作的實(shí)質(zhì)是把移動(dòng)n個(gè)盤子的問題轉(zhuǎn)化為移動(dòng)n-1個(gè)盤，那一、三步如何解決？事實(shí)上，上述方法設(shè)盤子數(shù)為n, n可為任意數(shù)，該法同樣適用于移動(dòng)n-1個(gè)盤。因此，依據(jù)上法，可解決n -1個(gè)盤子從A桿移到B桿(第一步)或從B桿移到C桿(第三步)問題?，F(xiàn)在，問題由移動(dòng)n個(gè)盤子的操作轉(zhuǎn)化為移動(dòng)n-2個(gè)盤子的操作。依據(jù)該原理，層層遞推，即可將原問題轉(zhuǎn)化為解決移動(dòng)n -2、n -3… … 3、2，直到移動(dòng)1個(gè)盤的操作，而移動(dòng)一個(gè)盤的操作是可以直接完成的。至此，我們的任務(wù)算作是真正完成了。而這種由繁化簡(jiǎn)，用簡(jiǎn)單的問題和已知的操作運(yùn)算來(lái)解決復(fù)雜問題的方法，就是遞歸法。在計(jì)算機(jī)設(shè)計(jì)語(yǔ)言中，用遞歸法編寫的程序就是遞歸程序。

漢諾塔問題是用遞歸方法求解的一個(gè)典型問題，在實(shí)際教學(xué)中，可以在傳統(tǒng)教學(xué)方式的基礎(chǔ)上，利用計(jì)算機(jī)輔助教學(xué)進(jìn)行算法的模擬演示教學(xué)，使學(xué)生更容易接受和理解遞歸算法的思想，不但能提高學(xué)生的學(xué)習(xí)興趣，而且還能取得較好的教學(xué)效果。

程序如下：

#include<bits/stdc++.h>

using namespace std;

int s=0,x=0;

void hanoti(int n,char one,char two,char three)

{

if (n==1)

{

cout<<one<<"→"<<three<<"? ? ? ? ?";

s++;

x++;

if (s==5)

{

cout<<endl<<endl;

s=0;

cout<<"? ? ? ? ? ";

}

}

else

{

hanoti (n-1,one,three,two);

cout<<one<<"→"<<three<<"? ? ? ? ?";

s++;

x++;

if (s==5)

{

cout<<endl<<endl;

s=0;

cout<<"? ? ? ? ? ";

}

hanoti (n-1,two,one,three);

}

}

int main()

{

int j;

cin>>j;

cout<<"? ? ? ? ? ";

hanoti (j,'A','B','C');

cout<<endl<<endl<<"? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? "<<x<<endl;

cout<<endl<<"? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? "<<pow(2,j)-1<<endl;

return 0;

}