實(shí)驗(yàn)6+漢諾塔游戲的迭代實(shí)現(xiàn)

1、軟件綜合項(xiàng)目開(kāi)發(fā)訓(xùn)練實(shí)驗(yàn)6 迭代漢諾塔游戲李偉鍵李偉鍵第2頁(yè)/共15頁(yè)遞歸遞歸：函數(shù)f()直接調(diào)用自己，或通過(guò)另一函數(shù)g()間接調(diào)用自己。f()|f()g() | f();| g(); f(); | |使用遞歸函數(shù)的兩個(gè)條件一個(gè)大的問(wèn)題可以逐步轉(zhuǎn)化為一個(gè)或多個(gè)小的類(lèi)似問(wèn)題，直到簡(jiǎn)化為一個(gè)簡(jiǎn)單問(wèn)題；遞歸有明確的終止條件。第3頁(yè)/共15頁(yè)遞歸的使用求解n的階乘n！n! = n(n-1)(n-2).21 = n(n-1)!int factorial ( int num )if ( num =1; i-)sum = i * sum;printf(n!等于%d, sum);第6頁(yè)/共15頁(yè)遞歸vs迭代遞

2、歸程序更直接，更好理解，編程更簡(jiǎn)單；遞歸程序的實(shí)現(xiàn)比迭代程序的實(shí)現(xiàn)需耗費(fèi)更多的時(shí)間和空間。因此，在具體實(shí)現(xiàn)的實(shí)現(xiàn)，盡可能把遞歸程序轉(zhuǎn)化為迭代程序。 并非所有的遞歸程序都有對(duì)應(yīng)的迭代程序；- 尾遞歸：遞歸作為最后一條語(yǔ)句，并且僅此一個(gè)遞歸調(diào)用?？梢灾苯愚D(zhuǎn)化為迭代（如求n！的遞歸）；- 非尾遞歸，無(wú)法直接轉(zhuǎn)化，需要通過(guò)使用堆棧，來(lái)實(shí)現(xiàn)遞歸。第7頁(yè)/共15頁(yè)遞歸轉(zhuǎn)化為迭代把遞歸算法轉(zhuǎn)化為非遞歸算法有如下三種基本方法： (1)通過(guò)分析，跳過(guò)分解過(guò)程，直接用循環(huán)結(jié)構(gòu)的算法實(shí)現(xiàn)求值過(guò)程； (2)遞歸為尾遞歸，直接轉(zhuǎn)化為迭代算法； (3)自己用棧模擬系統(tǒng)的運(yùn)行時(shí)棧,通過(guò)分析只保存必須保存的信息,從而用非遞歸

3、算法替代遞歸算法。第8頁(yè)/共15頁(yè)漢諾塔問(wèn)題有三根桿子（命名為A、B和C）。A桿上N（N1）個(gè)穿孔的圓盤(pán)，盤(pán)的尺寸由下到上依次變小。要求按照如下規(guī)則將A桿上的所有圓盤(pán)移至C桿上：每次只能移動(dòng)一個(gè)圓盤(pán)；1. 大盤(pán)不能疊在小盤(pán)下面。第9頁(yè)/共15頁(yè)漢諾塔游戲第10頁(yè)/共15頁(yè)基本思路移動(dòng)n個(gè)圓盤(pán)的基本思路將n-1個(gè)盤(pán)子從A桿移動(dòng)B桿，在此過(guò)程中可使用C桿作為臨時(shí)存放區(qū)；將最后一個(gè)盤(pán)子（最大）從A桿移動(dòng)C桿；將n-1個(gè)盤(pán)子從B桿移動(dòng)C桿，在此過(guò)程中可使用A桿作為臨時(shí)存放區(qū)。移動(dòng)n-1個(gè)圓盤(pán)的思路同移動(dòng)n個(gè)圓盤(pán)。當(dāng)n=1時(shí)，過(guò)程結(jié)束。第11頁(yè)/共15頁(yè)迭代思路(1/2)1.recursion_hano

4、(n-1,A,C,B); / 將 上 n-1 個(gè)圓盤(pán)移動(dòng)到 B上2.moveAC(n, A,C); /將最大的圓盤(pán)移動(dòng)到 C上 3.recursion_hano(n-1,B,A,C); /將B上的圓盤(pán)移動(dòng)到C上先把1移完，再移2，最后再移3。移1時(shí)，又是：先把1移完，再移2，最后再移3?？梢钥闯觯缟戏弦粋€(gè)堆棧的特點(diǎn)：后入先出。入棧順序：3，2，1。接著出棧，1。處理1：入棧3，2，1第12頁(yè)/共15頁(yè)迭代思路(2/2)使用一個(gè)堆棧來(lái)存放函數(shù)參數(shù)，對(duì)這些函數(shù)參數(shù)，依次調(diào)用函數(shù)recursion_hano或者moveAC來(lái)處理： 如果是recursion_hano函數(shù)，依次把3.recursi

5、on_hano(n-1,B,A,C) 、2.moveAC(n, A,C)和1.recursion_hano(n-1,A,C,B)入堆棧 如果是moveAC函數(shù)，直接移動(dòng)，也就是屏幕打印出移動(dòng)某圓盤(pán)，從x柱到y(tǒng)柱。函數(shù)參數(shù)要存放入堆棧，需要為ElemType聲明一個(gè)結(jié)構(gòu)體，結(jié)構(gòu)體內(nèi)放入所需的各種參數(shù)(n,num, A,B,C)： n:要移動(dòng)的盤(pán)子最大編號(hào) num:移動(dòng)盤(pán)子個(gè)數(shù)- 如果num為1，則為moveAC- 如果num=n，則為recursion_hano A，B，C:移動(dòng)的柱子編號(hào) AC，B為中轉(zhuǎn)第13頁(yè)/共15頁(yè)編碼思路初始化堆棧S依次把(n-1, n-1,B,A,C) 、 (n, 1,A,B,C) 、(n-1,n-1,A,C,B)入棧 /注意入棧順序是反過(guò)來(lái)的bool b = pop(S, p); / 一次出棧，存入pwhile(堆棧非空) if(p.num =1 ) moveAC; else / p.n = p.num 繼續(xù)壓棧； b = pop(S,