遞推

遞推

遞推演演算法是一種用若干步可重複運算來描述複雜問題的方法。遞推是序列計算中的一種常用演演算法。通常是通過計算前面的一些項來得出序列中的指定項的值。

基本介紹


遞推是按照一定的規律來計算序列中的每個項,通常是通過計算前面的一些項來得出序列中的指定項的值。其思想是把一個複雜的龐大的計算過程轉化為簡單過程的多次重複,該演演算法利用了計算機速度快和不知疲倦的機器特點。

遞推演演算法


【例1】
植樹節那天,有五位同學參加了植樹活動,他們完成植樹的棵樹都不相同。問第一位同學植了多少棵時,他指著旁邊的第二位同學說比他多植了兩棵;追問第二位同學,他又說比第三位同學多植了兩棵;... 如此,都說比另一位同學多植兩棵。最後問到第五位同學時,他說自己植了10棵。到底第一位同學植了多少棵樹?
分析:設第一位同學植樹的棵樹為a1,欲求a1,需從第五位同學植樹的棵數a5入手,根據“多兩棵”這個規律,按照一定順序逐步進行推算:
(1) a5=10;
(2) a4=a5+2=12;
(3) a3=a4+2=14;
(4) a2=a3+2=16;
(5) a1=a2+2=18;
Pascal程序:
Program Examl;
Var i,a:byte;
begin
a:=10;
for i:= 1 to 4 do
a:=a+2;
writeln('The Num is' ,a);
readln;
end.
本程序的遞推運算可用下圖示表示:
初始值a:=10 ----- i=1,a=a+2(12) ----- i=2,a=a+2(14) ------ i=3,a=a+2(16) ----- i=4,a=a+2(18) ---- 輸出a值
例2:
十本不同的書放在書架上。現重新擺放,使每本書都不在原來放的位置。有幾種擺法?
當n個編號元素放在n個編號位置,元素編號與位置編號各不對應的方法數用M(n)表示,那麼M(n-1)就表示n-1個編號元素放在n-1個編號位置,各不對應的方法數,其它類推.
第一步,把第n個元素放在一個位置,比如位置k,一共有n-1種方法;
第二步,放編號為k的元素,這時有兩種情況.1,把它放到位置n,那麼,對於剩下的n-2個元素,就有M(n-2)種方法;2,不把它放到位置n,這時,對於這n-1個元素,有M(n-1)種方法;
綜上得到
M(n)=(n-1)[M(n-2)+M(n-1)]
遞推演演算法以初始(起點)值為基礎,用相同的運算規律,逐次重複運算,直至運算結束。這種從“起點”重複相同的方法直至到達一定“邊界”,猶如單向運動,用循環可以實現。遞推的本質是按規律逐次推出(計算)先一步的結果。