ACM培訓(xùn)第四講-遞歸

1、ACM程序設(shè)計(jì)程序設(shè)計(jì)第四講第四講-遞歸遞歸湖南工學(xué)院 張新玉 將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題，分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。分而治之。凡治眾如治寡，分?jǐn)?shù)

2、是也。凡治眾如治寡，分?jǐn)?shù)是也。-孫子兵法孫子兵法 直接或間接地調(diào)用自身的算法稱為遞歸算法遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)遞歸函數(shù)。 由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。 分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。下面來看幾個(gè)實(shí)例。例例1 1 階乘函數(shù)階乘函數(shù)階乘函數(shù)可遞歸地定義為：00)!1(1!nnnnn邊界條件邊界條件遞歸方程遞歸方程邊界條件與遞歸方程是遞歸函數(shù)

3、的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。例例2 Fibonacci2 Fibonacci數(shù)列數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，被稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件邊界條件遞歸方程遞歸方程110)2() 1(11)(nnnnFnFnF第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：public static int fibonacci(int n) if (n 1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。 例例5 5 整數(shù)劃分問題整數(shù)劃分問題將正整數(shù)n表示成一系列

4、正整數(shù)之和：n=n1+n2+nk，其中n1n2nk1，k1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個(gè)數(shù)。 例如正整數(shù)6有如下11種不同的劃分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。(2) q(n,m)=q(n,n),mn;最大加數(shù)n1實(shí)際上不能大于n。因此，q(1,m)=1。(1) q(n,1)=1,n1;當(dāng)最大加數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式，即nn111 (4) q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整數(shù)n的最大加數(shù)n1

5、不大于m的劃分由n1=m的劃分和n1n-1 的劃分組成。(3) q(n,n)=1+q(n,n-1);正整數(shù)n的劃分由n1=n的劃分和n1n-1的劃分組成。例例5 5 整數(shù)劃分問題整數(shù)劃分問題前面的幾個(gè)例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)。可以建立q(n,m)的如下遞歸關(guān)系。11, 1),() 1,() 1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqmnq例例5 5 整數(shù)劃分問題整數(shù)劃分問題前面的幾個(gè)例子中，問

6、題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。 例例6 Hanoi6 Hanoi塔問題塔問題設(shè)a,b,c是3個(gè)塔座。開始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1,2,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則1：每次只能移動(dòng)1個(gè)圓盤；規(guī)則2：任何時(shí)刻都不允許將

7、較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。在問題規(guī)模較大時(shí)，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來解決這個(gè)問題。當(dāng)n=1時(shí)，問題比較簡(jiǎn)單。此時(shí)，只要將編號(hào)為1的圓盤從塔座a直接移至塔座b上即可。當(dāng)n1時(shí)，需要利用塔座c作為輔助塔座。此時(shí)若能設(shè)法將n-1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個(gè)較小的圓盤依照移動(dòng)規(guī)則從塔座c移至塔座b。由此可見，n個(gè)圓盤的移動(dòng)問題可分為2次n-1個(gè)圓盤的移動(dòng)問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計(jì)出解Hanoi塔問題的遞歸

8、算法如下。例例6 Hanoi6 Hanoi塔問題塔問題 public static void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 課堂練習(xí)課堂練習(xí)-基礎(chǔ)基礎(chǔ)： 轉(zhuǎn)轉(zhuǎn)相除法求最大公約數(shù)課堂練習(xí)課堂練習(xí)-題目題目1： 問題描述：大于1的正整數(shù)n可以分解成為n=x1*x2*x3*xn 例如，當(dāng)n=12時(shí)，共有8種不同的分解式 12=12*1 12=6*2 12=4*3 12=3*4 12=3*2*2 12= 2*6 12=2*3*2 12=2*2

9、*3 輸入n，求n的整數(shù)因子分解 2022-2-319 甲、乙兩人同時(shí)從 A地出發(fā)要盡快同時(shí)趕到 B地。出發(fā)時(shí) A 地有一輛小車，可是這輛小車除了駕駛員外只能帶一人。已知甲、乙兩人的步行速度一樣，且小于車的速度。問：怎樣利用小車才能使兩人盡快同時(shí)到達(dá) 【輸入】 僅一行，三個(gè)數(shù)據(jù)分別表示 AB兩地的距離 s，人的步行速度 a，車的速度 b。 【輸出】 兩人同時(shí)到達(dá) B地需要的最短時(shí)間。 【樣例】 輸入：120 5 25 輸出9.6000000000E+00 課堂練習(xí)課堂練習(xí)-題目題目2：今盒子里有n個(gè)小球，A、B兩人輪流從盒中取球，每個(gè)人都可以看到另一個(gè)人取了多少個(gè)，也可以看到盒中還剩下多少個(gè)，并且兩人都很聰明，不會(huì)做出錯(cuò)誤的判斷。我們約定： 每個(gè)人從盒子中取出的球的數(shù)目必須是：1，3，7或者8個(gè)。輪到某一方取球時(shí)不能棄權(quán)！A先取球，然后雙方交替取球，直到取完。被迫拿到最后一個(gè)球的一方為負(fù)方（輸方） 請(qǐng)編程確定出在雙方都不判斷失誤的情況下，對(duì)于特定的初