在處理遞推問題時，我們有時遇到的遞推關系是十分明顯的，簡單地寫出遞推關系式，就可以逐項遞推，即由第i項推出第i+1項，我們稱其為顯示遞推關系。但有的遞推關系，要經過仔細觀察，甚至要借助壹些技巧，才能看出它們之間的關系，我們稱其為隱式的遞推關系。
遞推算法的關鍵是認真分析題意，發現遞推關系，正確寫出遞推公式，求得邊界條件，然後用循環實現即可。
總結
1.遞推算法的基本形式，是指編程者讓計算機循環求得壹序列數值，而後壹項的計算結果是由上壹項或多項推導出來的。有時，我們為求得壹個數列的某壹項，我們不得不從第壹項開始，逐個計算前面每壹項的值。雖然這樣做的效率不很高，但它能幫助我們解決許多實際問題。
2.無論是順著還是逆著遞推，其關鍵是遞推公式是否正確，邊界條件是否正確。二者有壹個出錯。則所有遞推結果將都是錯誤的。
例1：已知數列1，2，5，10，17，26，37...求數列的第n項。
通過分析，我們可以發現，數列後面的數在前壹項的基礎上以1，3，5，7，9，11的規律增長，則可以得出增長規律的表達式為2*n-3,也就是a(1)=1,a(n)=a(n-1)+2*n-3;
還有壹個規律，我們可以發現每壹項依次為從0開始的自然數的平方再加1，即
(n-1)2+1,第壹項（1-1）2+1，第二項（2-1）2+1，第三項（3-1）2+1...
例2:階梯問題：題目的意思是：有N級階梯，可以壹步走上壹級，也可以壹步走兩級，求從階梯底走到頂端可以有多少種不同的走法。
這是壹個隱式的遞推關系，如果編程者不能找出這個遞推關系，可能就無法做出這題來。我們來分析壹下：走上第壹級的方法只有壹種，走上第二級的方法卻有兩種（兩次走壹級或壹次走兩級），走上第三級的走法，應該是走上第壹級的方法和走上第二級的走法之和（因從第壹級和第二級，都可以經壹步走至第三級,也就是說增加的第三級有兩種處理方法，第壹種就是直接作為壹級走壹步，那麽就和兩級的走法壹致，另壹種就是與第二級合並作壹步走，那麽就和壹級的走法壹致，加起來就是壹級的方法和二級的走法之和），推廣到走上第i級，是走上第i-1級的走法與走上第i-2級的走法之和。很明顯，這是壹個菲波拉契數列。到這裏，讀者應能很熟練地寫出這個程序。在以後的程序習題中，我們可能還會遇到菲波拉契數列變形以後的結果：如f(i)=f(i-1)+2f(i-2)，或f(i)=f(i-1)+f(i-2)+f(i-3)等。
例3：猴子吃桃問題：山中住有五只猴。壹天，老大看見壹堆桃子，想把桃子據為已有，卻擔心讓老二老三知道了說自己太貪心。於是將桃分成相等的兩份，卻發現剩余壹個，於是，老大吃掉這壹個以後，再帶走這堆桃的二分之壹。第二天，老二也看到了這堆桃，其想法和做法與老大壹樣，老三老四老五也和他們的兄長想到壹塊去了。結果等老五吃完壹個，帶走壹半以後，這堆桃還剩余11個。請編程計算當初這堆桃***有多少個。
這個下題目明眼人壹看便知，我們如果按兄弟吃桃把桃的相反順序倒推過去，就能知道當初桃子的總數。其遞推的公式是a[n-1]=a[n]*2+1。遞推的初始值是a[5]=11（又稱邊界條件），待求a[0]的值。相信現在大家能很容易就能寫出正確的程序。在這裏不過是想說明壹下，遞推算法不僅可以順著推、也可逆著推的道理。
回溯算法也叫試探法，它是壹種系統地搜索問題的解的方法。回溯算法的基本思想是：從壹條路往前走，能進則進，不能進則退回來，換壹條路再試。
用回溯算法解決問題的壹般步驟為：
壹、定義壹個解空間，它包含問題的解。
二、利用適於搜索的方法組織解空間。
三、利用深度優先法搜索解空間。
四、利用限界函數避免移動到不可能產生解的子空間。
問題的解空間通常是在搜索問題的解的過程中動態產生的，這是回溯算法的壹個重要特性。
回溯法是壹個既帶有系統性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任壹結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任壹解時，只要搜索到問題的壹個解就可以結束。這種以深度優先的方式系統地搜索問題的解的算法稱為回溯法，它適用於解壹些組合數較大的問題.
[遞推是學習材料，回溯是百度百科]
江靜
遊客 回答於：2010-8-29 15:05:18
遞歸
遞歸是計算機科學的壹個重要概念,遞歸的方法是程序設計中有效的方法,采用遞歸編寫
程序能是程序變得簡潔和清晰.
2.1 遞歸的概念
1.概念
壹個過程(或函數)直接或間接調用自己本身,這種過程(或函數)叫遞歸過程(或函數).
如:
procedure a;
begin
.
.
.
a;
.
.
.
end;
這種方式是直接調用.
又如:
procedure b; procedure c;
begin begin
. .
. .
. .
c; b;
. .
. .
. .
end; end;
這種方式是間接調用.
例1計算n!可用遞歸公式如下:
1 當 n=0 時
fac(n)={n*fac(n-1) 當n>0時
可編寫程序如下:
program fac2;
var
n:integer;
function fac(n:integer):real;
begin
if n=0 then fac:=1 else fac:=n*fac(n-1)
end;
begin
write('n=');readln(n);
writeln('fac(',n,')=',fac(n):6:0);
end.
例2 樓梯有n階臺階,上樓可以壹步上1階,也可以壹步上2階,編壹程序計算***有多少種不同的走法.
設n階臺階的走法數為f(n)
顯然有
1 n=1
f(n)={2 n=2
f(n-1)+f(n-2) n>2
可編程序如下：
program louti;
var n:integer;
function f(x:integer):integer;
begin
if x=1 then f:=1 else
if x=2 then f:=2 else f:=f(x-1)+f(x-2);
end;
begin
write('n=');read(n);
writeln('f(',n,')=',f(n))
end.
2.2 如何設計遞歸算法
1.確定遞歸公式
2.確定邊界(終了)條件
練習:
用遞歸的方法完成下列問題
1.求數組中的最大數
2.1+2+3+...+n
3.求n個整數的積
4.求n個整數的平均值
5.求n個自然數的最大公約數與最小公倍數
6.有壹對雌雄兔,每兩個月就繁殖雌雄各壹對兔子.問n個月後***有多少對兔子?7.已知:數列1,1,2,4,7,13,24,44,...求數列的第 n項.
2.3典型例題
例3 梵塔問題
如圖:已知有三根針分別用1,2,3表示,在壹號針中從小放n個盤子,現要求把所有的盤子
從1針全部移到3針,移動規則是:使用2針作為過度針,每次只移動壹塊盤子,且每根針上
不能出現大盤壓小盤.找出移動次數最小的方案.
程序如下:
program fanta;
var
n:integer;
procedure move(n,a,b,c:integer);
begin
if n=1 then writeln(a,'--->',c)
else begin
move(n-1,a,c,b);
writeln(a,'--->',c);
move(n-1,b,a,c);
end;
end;
begin
write('Enter n=');
read(n);
move(n,1,2,3);
end.
例4 快速排序
快速排序的思想是:先從數據序列中選壹個元素,並將序列中所有比該元素小的元素都放到它的右邊或左邊,再對左右兩邊分別用同樣的方法處之直到每壹個待處理的序列的長度為1, 處理結束.
程序如下:
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procedure quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
練習:
1.計算ackerman函數值:
n+1 m=0
ack(m,n)={ ack(m-1,1) m<>0 ,n=0
ack(m-1,ack(m,n-1)) m<>0,n<>0
求ack(5,4)
回溯
回溯是按照某種條件往前試探搜索,若前進中遭到失敗,則回過頭來另擇通路繼續搜索.
3.1 回溯的設計
1.用棧保存好前進中的某些狀態.
2.制定好約束條件
例1由鍵盤上輸入任意n個符號;輸出它的全排列.
program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procedure input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;
end;
begin
input;
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.
例2.n個皇後問題:
program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
begin
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.
回溯算法的公式如下:
3.2 回溯算法的遞歸實現
由於回溯算法用壹棧數組實現的,用到棧壹般可用遞歸實現。
上述例1的遞歸方法實現如下：
program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procedure input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;readln;
end;
procedure try(k:integer);
var i :integer;
begin
if k=n+1 then begin print;exit end;
for i:=1 to n do
begin
x[k]:=i;
if place(k) then try(k+1)
end
end;
begin
input;
try(1);
end.
例2：n皇後問題的遞歸算法如下：
程序1：
program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procedure try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end.
程序2：
說明:當n=8 時有30條對角線分別用了l和r數組控制，
用c數組控制列.當(i,j)點放好皇後後相應的對角線和列都為false.遞歸程序如下:
program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procedure output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procedure try(i:integer);
var j:integer;
begin
for j:=1 to n do
begin
if c[j] and l[i-j] and r[i+j] then
begin
a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
if i<n then try(i+1) else output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
end;
end;
end;
begin
for i:=1 to n do c[i]:=true;
for i:=1-n to n-1 do l[i]:=true;
for i:=2 to 2*n do r[i]:=true;
s:=0;try(1);
writeln;
end.
練習：
1.找出所有從m個元素中選取n(n<=m)元素的組合。
2.設有A,B,C,D,E 5人從事j1,j2,j3,j4,j5 5項工作每人只能從事壹項,它們的
效益表如下:
j1j2j3j4j5A13111047B13101085C59774D151210115E1011884
求最佳安排,使效益最高.
3.N個數中找出M個數(從鍵盤上輸入正整數N,M後再輸入N個正數),要求從N個數中
找出若幹個數,使它們的和為M,把滿足條件的數組找出來,並統計組數.
4.地圖著色。如下圖12個區域用4種顏色著色要求相鄰的區域著不同的顏色
5.將任意壹正整數(1<n<100)分解成若幹正整數的和.
如:4=1+1+1+1
=2+1+1
=2+2
=3+1.