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

1、軟件綜合項(xiàng)目開發(fā)訓(xùn)練實(shí)驗(yàn)6 迭代漢諾塔游戲李偉鍵李偉鍵第2頁/共15頁遞歸遞歸：函數(shù)f()直接調(diào)用自己，或通過另一函數(shù)g()間接調(diào)用自己。f()|f()g() | f();| g(); f(); | |使用遞歸函數(shù)的兩個(gè)條件一個(gè)大的問題可以逐步轉(zhuǎn)化為一個(gè)或多個(gè)小的類似問題，直到簡化為一個(gè)簡單問題；遞歸有明確的終止條件。第3頁/共15頁遞歸的使用求解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頁/共15頁遞歸vs迭代遞

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

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

4、(n-1,A,C,B); / 將 上 n-1 個(gè)圓盤移動(dòng)到 B上2.moveAC(n, A,C); /將最大的圓盤移動(dòng)到 C上 3.recursion_hano(n-1,B,A,C); /將B上的圓盤移動(dòng)到C上先把1移完，再移2，最后再移3。移1時(shí)，又是：先把1移完，再移2，最后再移3。可以看出，如上符合一個(gè)堆棧的特點(diǎn)：后入先出。入棧順序：3，2，1。接著出棧，1。處理1：入棧3，2，1第12頁/共15頁迭代思路(2/2)使用一個(gè)堆棧來存放函數(shù)參數(shù)，對(duì)這些函數(shù)參數(shù)，依次調(diào)用函數(shù)recursion_hano或者moveAC來處理： 如果是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)某圓盤，從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)的盤子最大編號(hào) num:移動(dòng)盤子個(gè)數(shù)- 如果num為1，則為moveAC- 如果num=n，則為recursion_hano A，B，C:移動(dòng)的柱子編號(hào) AC，B為中轉(zhuǎn)第13頁/共15頁編碼思路初始化堆棧S依次把(n-1, n-1,B,A,C) 、 (n, 1,A,B,C) 、(n-1,n-1,A,C,B)入棧 /注意入棧順序是反過來的bool b = pop(S, p); / 一次出棧，存入pwhile(堆棧非空) if(p.num =1 ) moveAC; else / p.n = p.num 繼續(xù)壓棧； b = pop(S,