遞推算法是一種用若干步可重復(fù)運(yùn)算來(lái)描述復(fù)雜問(wèn)題的方法。遞推是序列計(jì)算中的一種常用算法。通常是通過(guò)計(jì)算前面的一些項(xiàng)來(lái)得出序列中的指定項(xiàng)的值。以下是整理的相關(guān)資料，希望對(duì)您有所幫助！
【篇一】
遞推方法的概述
在不少計(jì)數(shù)問(wèn)題中，要很快求出結(jié)果是比較困難的，有時(shí)可先從簡(jiǎn)單情況入手，然后從某一種特殊情況逐漸推出與以后比較復(fù)雜情況之間的關(guān)系，找出規(guī)律逐步解決問(wèn)題，這樣的方法叫遞推方法。
例1、線段AB上共有10個(gè)點(diǎn)(包括兩個(gè)端點(diǎn))，那么這條線段上一共有多少條不同的線段?
分析與解答：
從簡(jiǎn)單情況研究起：
AB上共有2個(gè)點(diǎn)，有線段：1條
AB上共有3個(gè)點(diǎn)，有線段：1+2=3(條)
AB上共有4個(gè)點(diǎn)，有線段：1+2+3=6(條)
AB上共有5個(gè)點(diǎn)，有線段：1+2+3+4=10(條)
……
AB上共有10個(gè)點(diǎn)，有線段：1+2+3+4+…+9=45(條)
一般地，AB上共有n個(gè)點(diǎn)，有線段：
1+2+3+4+…+(n-1)=n×(n-1)÷2
即：線段數(shù)=點(diǎn)數(shù)×(點(diǎn)數(shù)-1)÷2
【篇二】
2000個(gè)學(xué)生排成一行，依次從左到右編上1～2000號(hào)，然后從左到右按一、二報(bào)數(shù)，報(bào)一的離開(kāi)隊(duì)伍，剩下的人繼續(xù)按一、二報(bào)數(shù)，報(bào)一的離開(kāi)隊(duì)伍，……按這個(gè)規(guī)律此下去，直至當(dāng)隊(duì)伍只剩下一人為止。問(wèn)：這時(shí)一共報(bào)了多少次?最后留下的這個(gè)人原來(lái)的號(hào)碼是多少?
分析與解答：
難的不會(huì)想簡(jiǎn)單的，數(shù)大的不會(huì)想數(shù)小的。我們先從這2000名同學(xué)中選出20人代替2000人進(jìn)行分析，試著找出規(guī)律，然后再用這個(gè)規(guī)律來(lái)解題。
這20人第一次報(bào)數(shù)后共留下10人，因?yàn)?0÷2=10，這10人開(kāi)始時(shí)的編號(hào)依次是：2、4、6、8、10、12、14、16、18、20，都是2的倍數(shù)。
第二次報(bào)數(shù)后共留下5人，因?yàn)?0÷2=5，這5人開(kāi)始時(shí)的編號(hào)依次是：4、8、12、16、20，都是4的倍數(shù)，也就是2×2的倍數(shù)。
第三次報(bào)數(shù)后共留下2人，因?yàn)?÷2=2……1，這2人開(kāi)始時(shí)的編號(hào)依次是：8、16，都是8的倍數(shù)，也就是2×2×2的倍數(shù)。
第四次報(bào)數(shù)后共留下1人，因?yàn)?÷2=1，這1人開(kāi)始時(shí)的編號(hào)是：16，都是8的倍數(shù)，也就是2×2×2×2的倍數(shù)。
由此可以發(fā)現(xiàn)，第n次報(bào)數(shù)后，留下的人的編號(hào)就是n個(gè)2的連乘積，這是一個(gè)規(guī)律。
2000名同學(xué)，報(bào)幾次數(shù)后才能只留下一個(gè)同學(xué)呢?
第一次：2000÷2=1000第二次：1000÷2=500
第三次：500÷2=250第四次：250÷2=125
第五次：125÷2=62……1第六次：62÷2=31
第七次：31÷2=15……1第八次：15÷2=7……1
第九次：7÷2=3……1第十次：3÷2=1……1
所以共需報(bào)10次數(shù)。
那么，最后留下的同學(xué)在一開(kāi)始時(shí)的編號(hào)應(yīng)是：
2×2×2×…×2=1024(號(hào))
【篇三】
平面上有10個(gè)圓，最多能把平面分成幾部分?
分析與解答：
直接畫出10個(gè)圓不是好辦法，先考慮一些簡(jiǎn)單情況。
一個(gè)圓最多將平面分為2部分;
二個(gè)圓最多將平面分為4部分;
三個(gè)圓最多將平面分為8部分;
當(dāng)?shù)诙€(gè)圓在第一個(gè)圓的基礎(chǔ)上加上去時(shí)，第二個(gè)圓與第一個(gè)圓有2個(gè)交點(diǎn)，這兩個(gè)交點(diǎn)將新加的圓弧分為2段，其中每一段圓弧都將所在平面的一分為二，所以所分平面部分的數(shù)在原有的2部分的基礎(chǔ)上增添了2部分。因此，二個(gè)圓最多將平面分為2+2=4部分。
同樣道理，三個(gè)圓最多分平面的部分?jǐn)?shù)是二個(gè)圓分平面為4部分的基礎(chǔ)上增加4部分。因此，三個(gè)圓最多將平面分為2+2+4=8部分。
由此不難推出：畫第10個(gè)圓時(shí)，與前9個(gè)圓最多有9×2=18個(gè)交點(diǎn)，第10個(gè)圓的圓弧被分成18段，也就是增加了18個(gè)部分。因此，10個(gè)圓最多將平面分成的部分?jǐn)?shù)為：
2+2+4+6+…+18
=2+2×(1+2+3+…+9)
=2+2×9×(9+1)÷2
=92
類似的分析，我們可以得到，n個(gè)圓最多將平面分成的部分?jǐn)?shù)為：
2+2+4+6+…+2(n-1)
=2+2×[1+2+3+…+(n-1)]
=2+n(n-1)
=n2-n+2
【篇一】
遞推方法的概述
在不少計(jì)數(shù)問(wèn)題中，要很快求出結(jié)果是比較困難的，有時(shí)可先從簡(jiǎn)單情況入手，然后從某一種特殊情況逐漸推出與以后比較復(fù)雜情況之間的關(guān)系，找出規(guī)律逐步解決問(wèn)題，這樣的方法叫遞推方法。
例1、線段AB上共有10個(gè)點(diǎn)(包括兩個(gè)端點(diǎn))，那么這條線段上一共有多少條不同的線段?
分析與解答：
從簡(jiǎn)單情況研究起：
AB上共有2個(gè)點(diǎn)，有線段：1條
AB上共有3個(gè)點(diǎn)，有線段：1+2=3(條)
AB上共有4個(gè)點(diǎn)，有線段：1+2+3=6(條)
AB上共有5個(gè)點(diǎn)，有線段：1+2+3+4=10(條)
……
AB上共有10個(gè)點(diǎn)，有線段：1+2+3+4+…+9=45(條)
一般地，AB上共有n個(gè)點(diǎn)，有線段：
1+2+3+4+…+(n-1)=n×(n-1)÷2
即：線段數(shù)=點(diǎn)數(shù)×(點(diǎn)數(shù)-1)÷2
【篇二】
2000個(gè)學(xué)生排成一行，依次從左到右編上1～2000號(hào)，然后從左到右按一、二報(bào)數(shù)，報(bào)一的離開(kāi)隊(duì)伍，剩下的人繼續(xù)按一、二報(bào)數(shù)，報(bào)一的離開(kāi)隊(duì)伍，……按這個(gè)規(guī)律此下去，直至當(dāng)隊(duì)伍只剩下一人為止。問(wèn)：這時(shí)一共報(bào)了多少次?最后留下的這個(gè)人原來(lái)的號(hào)碼是多少?
分析與解答：
難的不會(huì)想簡(jiǎn)單的，數(shù)大的不會(huì)想數(shù)小的。我們先從這2000名同學(xué)中選出20人代替2000人進(jìn)行分析，試著找出規(guī)律，然后再用這個(gè)規(guī)律來(lái)解題。
這20人第一次報(bào)數(shù)后共留下10人，因?yàn)?0÷2=10，這10人開(kāi)始時(shí)的編號(hào)依次是：2、4、6、8、10、12、14、16、18、20，都是2的倍數(shù)。
第二次報(bào)數(shù)后共留下5人，因?yàn)?0÷2=5，這5人開(kāi)始時(shí)的編號(hào)依次是：4、8、12、16、20，都是4的倍數(shù)，也就是2×2的倍數(shù)。
第三次報(bào)數(shù)后共留下2人，因?yàn)?÷2=2……1，這2人開(kāi)始時(shí)的編號(hào)依次是：8、16，都是8的倍數(shù)，也就是2×2×2的倍數(shù)。
第四次報(bào)數(shù)后共留下1人，因?yàn)?÷2=1，這1人開(kāi)始時(shí)的編號(hào)是：16，都是8的倍數(shù)，也就是2×2×2×2的倍數(shù)。
由此可以發(fā)現(xiàn)，第n次報(bào)數(shù)后，留下的人的編號(hào)就是n個(gè)2的連乘積，這是一個(gè)規(guī)律。
2000名同學(xué)，報(bào)幾次數(shù)后才能只留下一個(gè)同學(xué)呢?
第一次：2000÷2=1000第二次：1000÷2=500
第三次：500÷2=250第四次：250÷2=125
第五次：125÷2=62……1第六次：62÷2=31
第七次：31÷2=15……1第八次：15÷2=7……1
第九次：7÷2=3……1第十次：3÷2=1……1
所以共需報(bào)10次數(shù)。
那么，最后留下的同學(xué)在一開(kāi)始時(shí)的編號(hào)應(yīng)是：
2×2×2×…×2=1024(號(hào))
【篇三】
平面上有10個(gè)圓，最多能把平面分成幾部分?
分析與解答：
直接畫出10個(gè)圓不是好辦法，先考慮一些簡(jiǎn)單情況。
一個(gè)圓最多將平面分為2部分;
二個(gè)圓最多將平面分為4部分;
三個(gè)圓最多將平面分為8部分;
當(dāng)?shù)诙€(gè)圓在第一個(gè)圓的基礎(chǔ)上加上去時(shí)，第二個(gè)圓與第一個(gè)圓有2個(gè)交點(diǎn)，這兩個(gè)交點(diǎn)將新加的圓弧分為2段，其中每一段圓弧都將所在平面的一分為二，所以所分平面部分的數(shù)在原有的2部分的基礎(chǔ)上增添了2部分。因此，二個(gè)圓最多將平面分為2+2=4部分。
同樣道理，三個(gè)圓最多分平面的部分?jǐn)?shù)是二個(gè)圓分平面為4部分的基礎(chǔ)上增加4部分。因此，三個(gè)圓最多將平面分為2+2+4=8部分。
由此不難推出：畫第10個(gè)圓時(shí)，與前9個(gè)圓最多有9×2=18個(gè)交點(diǎn)，第10個(gè)圓的圓弧被分成18段，也就是增加了18個(gè)部分。因此，10個(gè)圓最多將平面分成的部分?jǐn)?shù)為：
2+2+4+6+…+18
=2+2×(1+2+3+…+9)
=2+2×9×(9+1)÷2
=92
類似的分析，我們可以得到，n個(gè)圓最多將平面分成的部分?jǐn)?shù)為：
2+2+4+6+…+2(n-1)
=2+2×[1+2+3+…+(n-1)]
=2+n(n-1)
=n2-n+2