C語(yǔ)言遞歸算法ppt課件

1、第四章第四章 遞歸算法遞歸算法1;. 前面曾經(jīng)引見(jiàn)了關(guān)于遞歸調(diào)用這樣一種操作，而遞歸程序設(shè)計(jì)是C+言語(yǔ)程序設(shè)計(jì)中的一種重要的方法，它使許多復(fù)雜的問(wèn)題變得簡(jiǎn)單，容易處置了。遞歸特點(diǎn)是：函數(shù)或過(guò)程調(diào)用它本人本身。其中直接調(diào)用本人稱為直接遞歸，而將A調(diào)用B，B以調(diào)用A的遞歸叫做間接遞歸。 2【例【例1】 給定給定nn=1,用遞歸的方法計(jì)算用遞歸的方法計(jì)算1+2+3+4+.+(n-1)+n。 【算法分析】【算法分析】 此題可以用遞歸方法求解，其緣由在于它符合遞歸的三個(gè)條件：此題可以用遞歸方法求解，其緣由在于它符合遞歸的三個(gè)條件： (1)此題是累加問(wèn)題：當(dāng)前和此題是累加問(wèn)題：當(dāng)前和=前一次和前一次和+當(dāng)

2、前項(xiàng)，而前一次和的計(jì)算方法與其一樣，只是數(shù)據(jù)不當(dāng)前項(xiàng)，而前一次和的計(jì)算方法與其一樣，只是數(shù)據(jù)不同同s(n)=s(n-1)+n; (2)給定給定n,所以是有限次的遞歸調(diào)用；所以是有限次的遞歸調(diào)用； (3)終了條件是當(dāng)終了條件是當(dāng)n=1，那么，那么s=1。 【參考程序】【參考程序】#includeusing namespace std;int fac(int); /遞歸函數(shù)遞歸函數(shù)int main()int t;cint; /輸入輸入t的值的值couts=fac(t)endl; /計(jì)算計(jì)算1到到t的累加和，輸出結(jié)果的累加和，輸出結(jié)果int fac(int n)if (n=1) return 1;r

3、eturn(fac(n-1)+n); /調(diào)用下一層遞歸調(diào)用下一層遞歸 3 運(yùn)轉(zhuǎn)程序，當(dāng)T=5時(shí)，輸出結(jié)果：S=15，其遞歸調(diào)用執(zhí)行過(guò)程是：設(shè)T=3 遞歸調(diào)用過(guò)程，本質(zhì)上是不斷調(diào)用過(guò)程或函數(shù)的過(guò)程，由于遞歸調(diào)用一次，一切子程序的變量部分變量、變參等、地址在計(jì)算機(jī)內(nèi)部都有用特殊的管理方法棧先進(jìn)后出來(lái)管理，一旦遞歸調(diào)用終了，計(jì)算機(jī)便開場(chǎng)根據(jù)棧中存儲(chǔ)的地址前往各子程序變量的值，并進(jìn)展相應(yīng)操作。 4【例【例2】 設(shè)有設(shè)有N個(gè)數(shù)曾經(jīng)按從大到小的順序陳列，如今輸入個(gè)數(shù)曾經(jīng)按從大到小的順序陳列，如今輸入X，判別它能否在這，判別它能否在這N個(gè)數(shù)中，個(gè)數(shù)中，假設(shè)存在那么輸出：假設(shè)存在那么輸出：“YES 否那么輸出

4、否那么輸出“NO。 【算法分析】【算法分析】 該問(wèn)題屬于數(shù)據(jù)的查找問(wèn)題，數(shù)據(jù)查找有多種方法，通常方法是：順序查找和二分查該問(wèn)題屬于數(shù)據(jù)的查找問(wèn)題，數(shù)據(jù)查找有多種方法，通常方法是：順序查找和二分查找，當(dāng)找，當(dāng)N個(gè)數(shù)排好序時(shí)，用二分查找方法速度大大加快。二分查找算法：個(gè)數(shù)排好序時(shí)，用二分查找方法速度大大加快。二分查找算法： 1 設(shè)有設(shè)有N個(gè)數(shù)，存放在個(gè)數(shù)，存放在A數(shù)組中，待查找數(shù)為數(shù)組中，待查找數(shù)為X，用，用L指向數(shù)據(jù)的高端，用指向數(shù)據(jù)的高端，用R指向數(shù)據(jù)指向數(shù)據(jù)的低端，的低端，MID指向中間：指向中間： 2 假設(shè)假設(shè)X=AMID 輸出輸出 “YES； 3假設(shè)假設(shè)XAMID那么到數(shù)據(jù)前半段查找：那

5、么到數(shù)據(jù)前半段查找：L不變，不變，R=MID-1，計(jì)算新的，計(jì)算新的MID值，并進(jìn)值，并進(jìn)展新的一段查找；展新的一段查找； 5假設(shè)假設(shè)LR都沒(méi)有查找到，那么輸出都沒(méi)有查找到，那么輸出“NO。 該算法符合遞歸程序設(shè)計(jì)的根本規(guī)律，可以用遞歸方法設(shè)計(jì)。該算法符合遞歸程序設(shè)計(jì)的根本規(guī)律，可以用遞歸方法設(shè)計(jì)。 5【參考程序】【參考程序】 #include#includeusing namespace std;int a11;void search(int,int,int);int main() /主程序主程序int k,x,L=1,R=10;cout輸入輸入10個(gè)從大到小順序的數(shù)：個(gè)從大到小順序的數(shù)：e

6、ndl;for (k=1;kak;cinx;search(x,L,R); system(pause); void search(int x,int top,int bot) /二分查找遞歸過(guò)程二分查找遞歸過(guò)程int mid; if (top=bot) mid=(top+bot)/2; /求中間數(shù)的位置求中間數(shù)的位置 6 if (x=amid) coutYESendl; /找到就輸出找到就輸出 else if (xamid) search(x,mid+1,bot); /判別在前半段還是后半段查找判別在前半段還是后半段查找 else search(x,top,mid-1); else coutNO

7、C; (2)當(dāng)當(dāng)N=2時(shí)，那么需求挪動(dòng)三次：時(shí)，那么需求挪動(dòng)三次： A- 1 - B, A - 2 - C, B - 1- C. (3)假設(shè)假設(shè)N=3，那么詳細(xì)挪動(dòng)步驟為：，那么詳細(xì)挪動(dòng)步驟為：89 假設(shè)把第3步，第4步，第7步抽出來(lái)就相當(dāng)于N=2的情況把上面2片捆在一同，視為一片：10 所以可按“N=2的挪動(dòng)步驟設(shè)計(jì)： 假設(shè)N=0，那么退出，即終了程序;否那么繼續(xù)往下執(zhí)行; 用C柱作為協(xié)助過(guò)渡，將A柱上的N-1片移到B柱上，調(diào)用過(guò)程mov(n-1, a,b,c); 將A柱上剩下的一片直接移到C柱上; 用A柱作為協(xié)助過(guò)渡，將B柱上的N-1移到C柱上，調(diào)用過(guò)程mov (n-1,b,c,a)?！緟?/p>

8、考程序】 #includeusing namespace std;int k=0,n;void mov(int n,char a,char c,char b) /用b柱作為協(xié)助過(guò)渡，將a柱上的n移到c柱上if (n=0) return; /假設(shè)n=0，那么退出，即終了程序mov(n-1,a,b,c ); /用c柱作為協(xié)助過(guò)渡，將a柱上的n-1片移到b柱上k+;cout k :from a cendl;mov(n-1,b,c,a ); /用a柱作為協(xié)助過(guò)渡，將b柱上的n-1移到c柱上11int main() coutn;mov(n,a,c,b); 12 程序定義了把n片從A柱移到C柱的過(guò)程mov

9、 (n,a,c,b)，這個(gè)過(guò)程把挪動(dòng)分為以下三步來(lái)進(jìn)展： 先調(diào)用過(guò)程mov (n-1, a, b, c)，把(n-1)片從A柱移到B柱, C柱作為過(guò)渡柱; 直接執(zhí)行 writeln(a, -, c)，把A柱上剩下的一片直接移到C柱上，; 調(diào)用mov (n-1,b,c,a)，把B柱上的(n-1)片從B移到C柱上，A柱是過(guò)渡柱。 對(duì)于B柱上的(n-1)片如何移到C柱，依然調(diào)用上述的三步。只是把(n-1)當(dāng)成了n，每調(diào)用一次，要移到目的柱上的片數(shù)N就減少了一片，直至減少到n=0時(shí)就退出，不再調(diào)用。exit是退出指令，執(zhí)行該指令能在循環(huán)或遞歸調(diào)用過(guò)程中一下子全部退出來(lái)。 mov過(guò)程中出現(xiàn)了本人調(diào)用本人

10、的情況，在Pascal中稱為遞歸調(diào)用，這是Pascal言語(yǔ)的一個(gè)特征。對(duì)于沒(méi)有遞歸調(diào)用功能的程序設(shè)計(jì)言語(yǔ)，那么需求將遞歸過(guò)程重新設(shè)計(jì)為非遞歸過(guò)程的程序。 13【例【例4】用遞歸的方法求斐波那契數(shù)列中的第】用遞歸的方法求斐波那契數(shù)列中的第N個(gè)數(shù)個(gè)數(shù) 【參考程序】【參考程序】#includeusing namespace std;int a11;int fib(int);int main() int m; cinm; coutfib(m)=k，k0)。w 下面，我們來(lái)確定S(n，k)的邊境條件,首先不能把n個(gè)元素不放進(jìn)任何一個(gè)集合中去，即k=0時(shí)，S(n，k)0；也不可以在不允許空盒的情況下把n個(gè)

11、元素放進(jìn)多于n的k個(gè)集合中去，即kn時(shí),S(n，k)0；再者，把n個(gè)元素放進(jìn)一個(gè)集合或把n個(gè)元素放進(jìn)n個(gè)集合，方案數(shù)顯然都是1，即k=1或k=n時(shí)，S(n,k)=1。w 因此，我們可以得出劃分?jǐn)?shù)S(n，k)的遞歸關(guān)系式為：w S(n，k)S(n1，k1) + k * S(n1，k) (nk，k0)w S(n，k)0 (nk)或(k0)w S(n，k)1 (k=1)或(kn)18w【參考程序】【參考程序】w #includewusing namespace std;wwint s(int n, int k) /數(shù)據(jù)還有可以越界，請(qǐng)用高精度計(jì)算數(shù)據(jù)還有可以越界，請(qǐng)用高精度計(jì)算ww if (n n

12、k;w cout s(n,k);w return 0;w19w【例【例6 6】數(shù)的計(jì)數(shù)】數(shù)的計(jì)數(shù)(Noip2001)(Noip2001)w【問(wèn)題描畫】【問(wèn)題描畫】w我們要求找出具有以下性質(zhì)數(shù)的個(gè)數(shù)包括輸入的自然數(shù)我們要求找出具有以下性質(zhì)數(shù)的個(gè)數(shù)包括輸入的自然數(shù)n n。先輸入一個(gè)自然數(shù)。先輸入一個(gè)自然數(shù)n nn1000n1000，然后對(duì)此自然數(shù)按照如下方法進(jìn)展處置：，然后對(duì)此自然數(shù)按照如下方法進(jìn)展處置：w不作任何處置；不作任何處置；w在它的左邊加上一個(gè)自然數(shù)，但該自然數(shù)不能超越原數(shù)的一半；在它的左邊加上一個(gè)自然數(shù)，但該自然數(shù)不能超越原數(shù)的一半；w加上數(shù)后，繼續(xù)按此規(guī)那么進(jìn)展處置，直到不能再加自然

13、數(shù)為止。加上數(shù)后，繼續(xù)按此規(guī)那么進(jìn)展處置，直到不能再加自然數(shù)為止。w輸入：自然數(shù)輸入：自然數(shù)n nn1000n1000w輸出：滿足條件的數(shù)輸出：滿足條件的數(shù)w【輸入樣例】【輸入樣例】w 6 6 滿足條件的數(shù)為滿足條件的數(shù)為 6 ( 6 (此部分不用輸出此部分不用輸出) )w 16 16w 26 26w 126 126w 36 36w w【輸出樣例】【輸出樣例】w 6 620【方法一】【方法一】用遞歸，用遞歸，f(n)=1+f(1)+f(2)+f(div/2)，當(dāng)，當(dāng)n較大時(shí)會(huì)超時(shí)，時(shí)間應(yīng)該為指數(shù)級(jí)。較大時(shí)會(huì)超時(shí)，時(shí)間應(yīng)該為指數(shù)級(jí)?！緟⒖汲绦颉俊緟⒖汲绦颉?includeusing namesp

14、ace std;int ans;void dfs(int m) /統(tǒng)計(jì)統(tǒng)計(jì)m所擴(kuò)展出的數(shù)據(jù)個(gè)數(shù)所擴(kuò)展出的數(shù)據(jù)個(gè)數(shù) int i; ans+; /每出現(xiàn)一個(gè)原數(shù)，累加器加每出現(xiàn)一個(gè)原數(shù)，累加器加1； for (i = 1; i n; dfs(n); cout ans; return 0; 21w【方法二】：用記憶化搜索，實(shí)踐上是對(duì)方法一的改良。設(shè)【方法二】：用記憶化搜索，實(shí)踐上是對(duì)方法一的改良。設(shè)hi表示自然數(shù)表示自然數(shù)i滿足題意三個(gè)條滿足題意三個(gè)條件的數(shù)的個(gè)數(shù)。假設(shè)用遞歸求解，會(huì)反復(fù)來(lái)求一些子問(wèn)題。例如在求件的數(shù)的個(gè)數(shù)。假設(shè)用遞歸求解，會(huì)反復(fù)來(lái)求一些子問(wèn)題。例如在求h4時(shí)，需求再求時(shí)，需求再求h

15、1和和h2的值。如今我們用的值。如今我們用h數(shù)組記錄在記憶求解過(guò)程中得出的一切子問(wèn)題的解，當(dāng)遇到重疊數(shù)組記錄在記憶求解過(guò)程中得出的一切子問(wèn)題的解，當(dāng)遇到重疊子問(wèn)題時(shí)，直接運(yùn)用前面記憶的結(jié)果。子問(wèn)題時(shí)，直接運(yùn)用前面記憶的結(jié)果。w【參考程序】【參考程序】w#includewusing namespace std;wint h1001;wvoid dfs(int m)ww int i;w if (hm != -1) return; /闡明前面曾經(jīng)求得闡明前面曾經(jīng)求得hm的值，直接援用即可，不需求再遞歸的值，直接援用即可，不需求再遞歸w hm = 1; /將將hm置為置為1，表示，表示m本身為一種情況

16、本身為一種情況w for (i = 1; i n;w for (int i = 1; i = n; i+)w hi = -1; /h數(shù)組初始化為數(shù)組初始化為-1w dfs(n); /由頂?shù)较掠洃浕f歸求解由頂?shù)较掠洃浕f歸求解w cout hn; w return 0;w22【方法三】【方法三】 用遞推，用用遞推，用h(n)表示自然數(shù)表示自然數(shù)n所能擴(kuò)展的數(shù)據(jù)個(gè)數(shù)，那么所能擴(kuò)展的數(shù)據(jù)個(gè)數(shù)，那么h(1)=1, h(2)=2, h(3)=2, h(4)=4, h(5)=4, h(6)=6, h(7)=6, h(8)=10, h(9)=10.分析以上數(shù)據(jù)，可得遞推公式：分析以上數(shù)據(jù)，可得遞推公式：h

17、(i)=1+h(1)+h(2)+h(i/2)。此算法的時(shí)間度為。此算法的時(shí)間度為O(n*n)。設(shè)設(shè)hi-i按照規(guī)那么擴(kuò)展出的自然數(shù)個(gè)數(shù)按照規(guī)那么擴(kuò)展出的自然數(shù)個(gè)數(shù)(1in)。下表列出了。下表列出了hi值及其方案：值及其方案：23w【參考程序】【參考程序】w#includewusing namespace std;wint h10001;wint main()ww int n;w cin n;w for (int i = 1; i = n; i+) /按照遞增順序計(jì)算擴(kuò)展出的自然數(shù)的個(gè)數(shù)按照遞增順序計(jì)算擴(kuò)展出的自然數(shù)的個(gè)數(shù)w w hi = 1; /擴(kuò)展出的自然數(shù)包括擴(kuò)展出的自然數(shù)包括i本身本身w

18、 for (int j = 1; j = i/2; j+) w /i左邊分別加上左邊分別加上1自然數(shù)自然數(shù) 按規(guī)那么擴(kuò)展出的自然數(shù)按規(guī)那么擴(kuò)展出的自然數(shù)w hi += hj; w w cout hn;w return 0;w24【方法四】【方法四】是對(duì)方法三的改良，我們定義數(shù)組是對(duì)方法三的改良，我們定義數(shù)組s，s(x)=h(1)+h(2)+h(x),h(x)=s(x)-s(x-1)，此算法的時(shí)間，此算法的時(shí)間復(fù)雜度可降到復(fù)雜度可降到O(n)?！緟⒖汲绦颉俊緟⒖汲绦颉?includeusing namespace std;int h1001,s1001;int main() int n; cin

19、 n; for (int i = 1; i = n; i+) hi = 1 + si/2; si = si-1 + hi; /s是是h的前綴累加和的前綴累加和 cout hn; return 0;25【方法五】【方法五】 還是用遞推，只需作仔細(xì)分析，其實(shí)我們還可以得到以下的遞推公式還是用遞推，只需作仔細(xì)分析，其實(shí)我們還可以得到以下的遞推公式: (1)當(dāng)當(dāng)i為奇數(shù)時(shí)，為奇數(shù)時(shí)，h(i)=h(i-1); (2)當(dāng)當(dāng)i為偶數(shù)時(shí)為偶數(shù)時(shí),h(i)=h(i-1)+h(i/2).【參考程序】【參考程序】#includeusing namespace std;int h1001;int main() int

20、 n; cin n; h1 = 1; for (int i = 2; i = n; i+) hi = hi-1; if (i % 2 = 0) hi = hi-1 + hi/2; cout 0，n0) 【輸入格式】【輸入格式】 輸入二個(gè)數(shù)，即輸入二個(gè)數(shù)，即m和和n的值。的值?！据敵龈袷健俊据敵龈袷健?輸出最大公約數(shù)。輸出最大公約數(shù)。【輸入樣例】【輸入樣例】 8 6【輸出樣例】【輸出樣例】 gcd=2316、雙色、雙色Hanoi塔問(wèn)題塔問(wèn)題【問(wèn)題描畫】【問(wèn)題描畫】 設(shè)設(shè)A、B、C是是3 個(gè)塔座。開場(chǎng)時(shí)，在塔座個(gè)塔座。開場(chǎng)時(shí)，在塔座A 上有一疊共上有一疊共n 個(gè)圓盤，這些圓盤自下而上，由大個(gè)圓盤，

21、這些圓盤自下而上，由大到小地疊在一同。各圓盤從小到大編號(hào)為到小地疊在一同。各圓盤從小到大編號(hào)為1，2，n，奇數(shù)號(hào)圓盤著藍(lán)色，偶數(shù)號(hào)圓盤著紅，奇數(shù)號(hào)圓盤著藍(lán)色，偶數(shù)號(hào)圓盤著紅色，如以以下圖?，F(xiàn)要求將塔座色，如以以下圖?，F(xiàn)要求將塔座A 上的這一疊圓盤移到塔座上的這一疊圓盤移到塔座B 上，并仍按同樣順序疊置。在挪動(dòng)上，并仍按同樣順序疊置。在挪動(dòng)圓盤時(shí)應(yīng)遵守以下挪動(dòng)規(guī)那么：圓盤時(shí)應(yīng)遵守以下挪動(dòng)規(guī)那么： 規(guī)那么規(guī)那么(1)：每次只能挪動(dòng)：每次只能挪動(dòng)1 個(gè)圓盤；個(gè)圓盤； 規(guī)那么規(guī)那么(2)：任何時(shí)辰都不允許將較大的圓盤壓在較小的圓盤之上；：任何時(shí)辰都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)那么規(guī)那么(

22、3)：任何時(shí)辰都不允許將同色圓盤疊在一同；：任何時(shí)辰都不允許將同色圓盤疊在一同； 規(guī)那么規(guī)那么(4)：在滿足挪動(dòng)規(guī)那么：在滿足挪動(dòng)規(guī)那么(1)-(3)的前提下，可將圓盤移至的前提下，可將圓盤移至A，B，C 中任一塔座上。中任一塔座上。 試設(shè)計(jì)一個(gè)算法，用最少的挪動(dòng)次數(shù)將塔座A 上的n個(gè)圓盤移到塔座B 上，并仍按同樣順序疊置。32【編程義務(wù)】【編程義務(wù)】 對(duì)于給定的正整數(shù)對(duì)于給定的正整數(shù)n，編程計(jì)算最優(yōu)挪動(dòng)方案。，編程計(jì)算最優(yōu)挪動(dòng)方案。【輸入格式】【輸入格式】 由文件由文件hanoi.in給出輸入數(shù)據(jù)。第給出輸入數(shù)據(jù)。第1 行是給定的正整數(shù)行是給定的正整數(shù)n?！据敵龈袷健俊据敵龈袷健?將計(jì)算出的

23、最優(yōu)挪動(dòng)方案輸出到文件將計(jì)算出的最優(yōu)挪動(dòng)方案輸出到文件hanoi.out。文件的每一行由一個(gè)正整數(shù)。文件的每一行由一個(gè)正整數(shù)k和和2個(gè)字個(gè)字符符c1和和c2組成，表示將第組成，表示將第k個(gè)圓盤從塔座個(gè)圓盤從塔座c1移到塔座移到塔座c2上。上。【輸入樣例】【輸入樣例】3 【輸出樣例】【輸出樣例】1 A B2 A C1 B C3 A B1 C A2 C B1 A B337、背包問(wèn)題、背包問(wèn)題【問(wèn)題描畫】【問(wèn)題描畫】 簡(jiǎn)單的背包問(wèn)題。設(shè)有一個(gè)背包，可以放入的分量為簡(jiǎn)單的背包問(wèn)題。設(shè)有一個(gè)背包，可以放入的分量為s?，F(xiàn)有?，F(xiàn)有n件物品，分量分別為件物品，分量分別為w1,w2，wn，1in均為正整數(shù)，從均

24、為正整數(shù)，從n件物品中挑選假設(shè)干件，使得放入背包的分量之件物品中挑選假設(shè)干件，使得放入背包的分量之和正好為和正好為s。找到一組解即可。找到一組解即可?！据斎敫袷健俊据斎敫袷健?第一行是物品總件數(shù)和背包的載分量，第二行為各物品的分量。第一行是物品總件數(shù)和背包的載分量，第二行為各物品的分量?！据敵龈袷健俊据敵龈袷健?各所選物品分量。各所選物品分量?！据斎霕永俊据斎霕永? 101 2 3 4 5【輸出樣例】【輸出樣例】number:1 weight:1number:4 weight:4number:5 weight:5348、2的冪次方的冪次方Noip1998【問(wèn)題描畫】【問(wèn)題描畫】 任何一個(gè)正

25、整數(shù)都可以用任何一個(gè)正整數(shù)都可以用2的冪次方表示。例如：的冪次方表示。例如： =27+23+20 同時(shí)商定方次用括號(hào)來(lái)表示，即同時(shí)商定方次用括號(hào)來(lái)表示，即ab 可表示為可表示為ab。 由此可知，可表示為：由此可知，可表示為： 27+23+20 進(jìn)一步：進(jìn)一步：7= 22+2+20 21用用2表示表示 3=2+20 所以最后可表示為：所以最后可表示為： 222+2+20+22+20+20 又如：又如： 1315=210 +28 +25 +2+1 所以所以1315最后可表示為：最后可表示為： 222+20+2+222+20+222+20+2+20【輸入格式】【輸入格式】 正整數(shù)正整數(shù)n20000【

26、輸出格式】【輸出格式】 符合商定的符合商定的n的的0，2表示在表示中不能有空格表示在表示中不能有空格【輸入樣例】【輸入樣例】 【輸出樣例】【輸出樣例】2(2(2)+2+2(0)+2(2+2(0)+2(0)359、數(shù)的計(jì)數(shù)、數(shù)的計(jì)數(shù)Noip2001【問(wèn)題描畫】【問(wèn)題描畫】 我們要求找出具有以下性質(zhì)數(shù)的個(gè)數(shù)我們要求找出具有以下性質(zhì)數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)包含輸入的自然數(shù)n): 先輸入一個(gè)自然數(shù)先輸入一個(gè)自然數(shù)nn1000, 然后對(duì)此自然數(shù)按照如下方法進(jìn)展處置：然后對(duì)此自然數(shù)按照如下方法進(jìn)展處置： 1不作任何處置；不作任何處置； 2在它的左邊加上一個(gè)自然數(shù)，但該自然數(shù)不能超越原數(shù)在它的左邊加上一個(gè)自然數(shù)，但該自然數(shù)不能超越原數(shù)(輸入的輸入的n)的一半；的一半； 3加上數(shù)后，繼續(xù)按此規(guī)那么進(jìn)展處置，直到不能再加自然數(shù)為止。加上數(shù)后，繼續(xù)按此規(guī)那么進(jìn)展處置，直到不能再加自然數(shù)為止。【輸入樣例】【輸入樣例】 6 滿足條件的數(shù)為滿足條件的數(shù)為 6 (此部分不用輸出此部分不用輸出) 16 26 126 36 【輸出樣例】【輸出樣例】636【編程義務(wù)】【編程義務(wù)】 給