C語(yǔ)言初學(xué)者入門知識(shí)之函數(shù)03

　　本題算法分析如下，設(shè)A上有n個(gè)盤子。

　　如果n=1，則將圓盤從A直接移動(dòng)到C。

　　如果n=2，則：

　　1.將A上的n-1(等于1)個(gè)圓盤移到B上;

　　2.再將A上的一個(gè)圓盤移到C上;

　　3.最后將B上的n-1(等于1)個(gè)圓盤移到C上。

　　如果n=3，則：

　　A. 將A上的n-1(等于2，令其為n`)個(gè)圓盤移到B(借助于C)，

　　步驟如下：

　　(1)將A上的n`-1(等于1)個(gè)圓盤移到C上，見圖5.5(b)。

　　(2)將A上的一個(gè)圓盤移到B,見圖5.5(c)

　　(3)將C上的n`-1(等于1)個(gè)圓盤移到B,見圖5.5(d)

　　B. 將A上的一個(gè)圓盤移到C，見圖5.5(e)

　　C. 將B上的n-1(等于2，令其為n`)個(gè)圓盤移到C(借助A)，

　　步驟如下：

　　(1)將B上的n`-1(等于1)個(gè)圓盤移到A,見圖5.5(f)

　　(2)將B上的一個(gè)盤子移到C,見圖5.5(g)

　　(3)將A上的n`-1(等于1)個(gè)圓盤移到C，見圖5.5(h)。

　　到此，完成了三個(gè)圓盤的移動(dòng)過程。

　　從上面分析可以看出，當(dāng)n大于等于2時(shí)， 移動(dòng)的過程可分解為三個(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。顯然這是一個(gè)遞歸過

　　程，據(jù)此算法可編程如下：

　　move(int n,int x,int y,int z)

　　{

　　if(n==1)

　　printf("%c-->%c\n",x,z);

　　else

　　{

　　move(n-1,x,z,y);

　　printf("%c-->%c\n",x,z);

　　move(n-1,y,x,z);

　　}

　　}

　　main()

　　{

　　int h;

　　printf("\ninput number:\n");

　　scanf("%d",&h);

　　printf("the step to moving %2d diskes:\n",h);

　　move(h,'a','b','c');

　　}

　　move(int n,int x,int y,int z)

　　{

　　if(n==1)

　　printf("%-->%c\n",x,z);

　　else

　　{

　　move(n-1,x,z,y);

　　printf("%c-->%c\n",x,z);

　　move(n-1,y,x,z);

　　}

　　}

　　main()

　　{ ……

　　move(h,'a','b','c');

　　}

　　從程序中可以看出，move函數(shù)是一個(gè)遞歸函數(shù)，它有四個(gè)形參n，x，y，zn表示圓盤數(shù)，x，y，z分別表示三根針。move 函數(shù)的功能是把x上的n個(gè)圓盤移動(dòng)到z 上。當(dāng)n==1時(shí)，直接把x上的圓盤移至z上，輸出x→z。如n!=1則分為三步：遞歸調(diào)用move函數(shù)，把n-1個(gè)圓盤從x移到y(tǒng);輸出x→z;遞歸調(diào)用move函數(shù)，把n-1個(gè)圓盤從y移到z。在遞歸調(diào)用過程中n=n-1，故n的值逐次遞減，最后n=1時(shí)，終止遞歸，逐層返回。當(dāng)n=4 時(shí)程序運(yùn)行的結(jié)果為：

　　input number:

　　4

　　the step to moving 4 diskes:

　　a→b

　　a→c

　　b→c

　　a→b

　　c→a

　　c→b

　　a→b

　　a→c

　　b→c

　　b→a

　　c→a

　　b→c

　　a→b

　　a→c

　　b→c

　　相關(guān)推薦：

　　2012年軟考系統(tǒng)分析師考試60天完美復(fù)習(xí)計(jì)劃

　　2012年軟件水平考試網(wǎng)絡(luò)工程師章節(jié)筆記講義匯總

　　2012年上半年軟件水平考試成績(jī)查詢匯總