[理學(xué)]第08章遞歸與搜索上-文庫吧資料
2024-10-22 21:20本頁面
【正文】 disks:\n, m )。 scanf( %d, amp。 int m。 include iostream using namespace std。 ? 設(shè)計(jì)程序 ? 分別用 2 個(gè)函數(shù)實(shí)現(xiàn)以上 2 類操作： ? 設(shè)計(jì) hanoi 函數(shù)實(shí)現(xiàn)第 1 類操作； ? 函數(shù) hanoi( n, one, two, three ) 將實(shí)現(xiàn)把 n 個(gè)盤子從 one 座借助 two 座移到 three 座的過程； ? 設(shè)計(jì) move 函數(shù)實(shí)現(xiàn)第 2 類操作； ? 函數(shù) move( x, y ) 將實(shí)現(xiàn)把 1 個(gè)盤子從 x 座移到 y 座的過程。 ? 對第 3 步，對應(yīng)關(guān)系是： one— B， two— C， three— A 。 ? 只是在第 1 步和第 3 步中， one、 two、 three 和 A、 B、 C 的對應(yīng)關(guān)系不同。 ? 上面第 1 步和第 3 步，都是把 n1 個(gè)盤子從 1 個(gè)座移到另 1 個(gè)座上， 采用的辦法是相同的，只是座的名字不同而已。 ? 注意： ? 第 1 個(gè)人完成任務(wù)的前提是：第 2 個(gè)人完成了任務(wù) ? 第 2 個(gè)人完成任務(wù)的前提是：第 3 個(gè)人完成了任務(wù) ? …… ? 第 63 個(gè)人完成任務(wù)的前提是：第 64 個(gè)人完成了任務(wù) ? 所以： ? 只有當(dāng)?shù)? 64 個(gè)人完成任務(wù)后，第 63 個(gè)人才能完成任務(wù)；只有第 2~64 個(gè)人完成任務(wù)后，第 1 個(gè)人才能完成任務(wù)！ ? 典型的遞歸問題！ 思考： 遞歸的結(jié)束條件是什么？ 21 3 2 1 A B C 1 2 1 31 2 1 ? 進(jìn)一步分析： ? 欲將 A 上 3 個(gè)盤子移到 C 上，用遞歸思想可以分解為以下 3 步： 1) 將 A 上 2 個(gè)盤子移到 B 上（借助 C ） 2) 將 A 上 1 個(gè)盤子移到 C 上 3) 將 B 上 2 個(gè)盤子移到 C 上（借助 A ） （ 其中，第 2 步可以直接實(shí)現(xiàn)。 63 62 1 2 63 62 1 2 18 思考： n個(gè)盤子至少需要移動(dòng)多少步？比如 n=64。 ?比如：只有 2 個(gè)盤子的情況，此問題就變得相當(dāng)?shù)暮唵?，只需? 3 步就可以完成整個(gè)移動(dòng)操作。要求編程輸出移動(dòng)的步驟。 16 A B C ？ 例 經(jīng)典的 Hanoi(漢諾塔 )問題 問題描述：古代有一個(gè)梵塔，塔內(nèi)有 A， B， C三個(gè)柱子。 else return gcd(v, u%v)。其遞歸思想是：在求最大公約數(shù)過程中，如果 u對 v取余的結(jié)果為 0，則最大公約數(shù)就是 v； 否則 遞歸 求 v和 u%v的最大公約數(shù)。 return 0。 }。 m = n。n )。 scanf( %d%d, amp。 } int main( ) { int m, n, t。 v=r。 r=u%v=15 u=v=18 v=r=15 r=u%v=3 u=v=15 v=r=3 u=m=33 v=n=18 因此 18和 33的最大公約數(shù)是 v=3 r=u%v=0 14 輾轉(zhuǎn)相除法可以采用 非遞歸 的方法，即 循環(huán)方法 實(shí)現(xiàn)，如下面的代碼： include int gcd( int u, int v ) //求 u和 v的最大公約數(shù) { int r。 思考： 在初等數(shù)學(xué)里是如何求兩個(gè)數(shù)的最大公約數(shù)？ 13 分析 (continue)： 例如，假設(shè)輸入的兩個(gè)正整數(shù)為 18和 33，則 m = 33， n = 18。其基本思想及執(zhí)行過程為 (設(shè) m為兩正整數(shù)中較大者， n為較小者 )： (1) 令 u = m， v = n； (2) 取 u對 v的余數(shù) ，即 r = u%v， 如果r的值為 0，則此時(shí) v的值就是 m和 n的最大公約數(shù) ，否則執(zhí)行第 (3)步； (3) u = v， v = r， 即 u的值為 v的值，而 v的值為余數(shù) r。 //每個(gè)數(shù)據(jù)占 6個(gè)字符的寬度 } printf( \n )。 i++ ) { if( i%10==0 ) printf( \n )。 for( i=0。 i20。 int f[20] = { 0 }。 else return ( Fibonacci(n1) + Fibonacci(n2) )。 分析： Fibonacci數(shù)列各項(xiàng)的遞推關(guān)系是： F(n) = F(n1) + F(n2)， 這種遞推關(guān)系式很 適合 用 遞歸函數(shù) 實(shí)現(xiàn)。 return 0。 else return(2*(A(n+1)+1))。假設(shè)第 n天吃完后剩下的桃子數(shù)為 A(n)， 第 n+1天吃完后剩下的桃子數(shù)為A(n+1)， 則存在的推關(guān)系： A(n) = ( A(n+1) + 1 ) * 2。 return 0。 day。 while( day0 ) { x1 = (x2+1)*2。 day = 9。 從第 9天剩下 1個(gè)桃子，反復(fù)遞推 9次，則可求第 1天共摘下的桃子數(shù)。 有以下遞推式子： A0 = 2 (A1+1) A1： 第 1天吃完后剩下的桃子數(shù) A1 = 2 (A2+1) A2： 第 2天吃完后剩下的桃子數(shù) …… A8 = 2 (A9+1) A9： 第 9天吃完后剩下的桃子數(shù) A9 = 1 以上遞推過程可分別用 循環(huán)結(jié)構(gòu) 和 遞歸函數(shù) 實(shí)現(xiàn)。求第 1天共摘了多少個(gè)桃子。以后每天早上都吃了前一天剩下的一半另加一個(gè)。猴子第 1天摘下若干個(gè)桃子，當(dāng)即吃了一半，還不過癮，又多吃了一個(gè)。 6 假設(shè)要求 3!，其完整的執(zhí)行過程如圖 ，具體過程為： ①執(zhí)行 main函數(shù)的開頭部分； ②當(dāng)執(zhí)行到 Factorial函數(shù)調(diào)用“ Factorial(3)”時(shí)，流程轉(zhuǎn)而去執(zhí)行Factorial(3)函數(shù)，并將實(shí)參 3傳遞給形參 n； ③ 執(zhí)行 Factorial(3)函數(shù)的開頭部分； ④當(dāng)執(zhí)行到遞歸調(diào)用 Factorial(n1)函數(shù)時(shí)，此時(shí) n1=2， 所以要轉(zhuǎn)而去執(zhí)行 Factorial(2)函數(shù)； ⑤執(zhí)行 Factorial(2)函數(shù)的開頭部分； ⑥當(dāng)執(zhí)行到遞歸調(diào)用 Factorial(n1)函數(shù)時(shí)，此時(shí) n1=1， 所以要轉(zhuǎn)而去執(zhí)行 Factorial(1)函數(shù)； 7 ⑦執(zhí)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1