Đệ quy cỡ nhỏ
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (123.23 KB, 8 trang )
Đệ quy có nhớ
Đỗ Đức Đông
Bài toán 1: Số Fibonacci
Xét dãy số Fibonacci: 1, 1,2, 3, 5, 8, 11,...; trong đó số đứng sau bằng tổng hai số đứng
trước nó. Hãytìm số Fibonacci thứ n.
Fib(1)= 1
Fib(2)= 1
Fib(n)= Fib(n-1)+Fib(n-2) với n>2
Phân tích bài toán:Việc giải bài toán lớn Fib(n) tương đương với việc giải hai bài toán con
Fib(n-1)và Fib(n-2). Bài toán Fib(n-1) lại được chia ra làm hai bài toán con Fib(n-2)và
Fib(n-3). Như vậy, bài toán Fib(n-2) được gặp lại. Và tiếp tục như vậy, tacó:
Fib[n] = Fib[n-1] + Fib[n-2] =(Fib[n-2]+Fib[n-3])+Fib[n-2] =...
Lời giải: Ta sẽdùng một mảng một chiều F[1..N] phần tử thứ k sẽ là số Fib thứ k. Ban đầu
tagán các phần tử của mảng F đều bằng -1 (đánh dấu để phân biệt bài toán đượcgiải hay
chưa). Giải hai bài toán con nhỏ nhất F[1]:=1 và F[2]:=1. Khi giải bàitoán Fib(k) ta kiểm
tra xem bài toán này đã được giải chưa (thể hiện bằngF[k]=-1, hay khác -1). Nếu bài toán
chưa được giải (F[k]=-1) thì ta sẽ tínhFib(k) nếu không ta sẽ sử dụng kết quả bài toán
Fib(k) là F[k].
Chương trình dưới đây khá gọn,dễ hiểu và rất hiệu quả.
Uses crt;
Const max = 20;
Var F : array[1..max]oflongint;
N : integer;
Procedure Nhap;
Var k :integer;
Begin
Write(?Nhap N:?); readln(n);
For k:=1 to n do F[k]:=-1; {tất cả các bài toán đều chưa được giải}
F[1]:=1;F[2]:=1; {giải hai bài toán con nhỏ nhất}
End;
FunctionFib(k:integer):longint;
Begin
If F[k]=-1 then { Nếu bài toán con này chưa được giải}
F[k]:=Fib(k-1)+Fib(k-2); {chia ra làm 2 bài toán con}
Fib:=F[k]; {lấy kết quả}
End;
BEGIN
Nhap;
Writeln('Fibonacci(', n ,')='), Fib(n));
Readln;
END.
Bài toán 2: Tính tổ hợp chập k của N phần tử C(k,n)
Phân tích bài toán:
C[k,n] = C[k,n-1] + C[k-1,n-1]= (C[k,n-2] + C[k-1,n-2]) +(C[k-1,n-2] + C[k-2,n-2]) =..
Như vậy C[k-1,n-2] được tínhlại. Cứ tiếp tục khai triển ta sẽ thấy các bài toán con khác
cũng sẽ lặp lạinhiều lần.
Gợi ý: Dùng mảng2 chiều C[1..k,1..N]. Phần tử thứ C[k,n] sẽ là kết quả của tổ hợp chập k
của Nphần tử.
Các bạn có thể tự giải bài này.
Bài 3: Phân trang (Đề thi chọn đội tuyển quốc gia 99 )
Văn bản là một dãy gồm N từđánh số từ 1 đến N. Từ thứ i có độ dài là w
i
(i=1, 2,... N).
Phântrang là một cách xếp lần lượt các từ của văn bản vào dãy các dòng, mỗi dòng cóđộ
dài L, sao cho tổng độ dài của các từ trên cùng một dòng không vượt quá L.Ta gọi hệ số
phạt của mỗi dòng trong cách phân trang là hiệu số (L-S), trong đóS là tổng độ dài của
các từ xếp trên dòng đó. Hệ số phạt của cách phân trang làgiá trị lớn nhất trong số các hệ
số phạt của các dòng.
Yêu cầu: Tìmcách phân trang với hệ số phạt nhỏ nhất.
Dữ liệu vào từ tệp văn bảnPTRANG.INP
- Dòng 1chứa 2 số nguyên dương N, L (N<=4000, L<=70)
- Dòng thứi trong số N dòng tiếp theo chứa số nguyên dương w
i
(w
i
<=L),i=1, 2,.., N
Kết qủa ghi ra file văn bảnPTRANG.OUT
- Dòng 1ghi 2 số P,Q theo thứ tự là hệ số phạt và số dòng theo cách phân trang tìm được
- Dòng thứi trong số Q dòng tiếp theo ghi chỉ số của các từ trong dòng thứ i của cáchphân
trang.
Ví dụ:
Lời giải:
Xét bài toán với i từ đầu tiên(các từ có số thứ tự từ 1 tới i). Ta gọi cách phân trang pt
j
là
cáchphân trang tối ưu từ thứ 1 đến từ thứ j vào mộtsố dòng và phân trang từ thứ j+1 đến từ
thứ i vào một dòng tiếp theo (với điều kiện tổng chiều dài các từ từ j+1 tớii không lớn hơn
L hay S = W
j+1
+ W
j+2
+... + W
i
<=L).
Như vậy hệ số phạt nhỏ nhất củacách phân trang i từ này là:
MAX {hệ số phạt của cách phân trang tối ưu từ thứ 1 đến từ thứ jvào một số dòng,
hệ số phạt củacác từ thứ j+1 đến từ thứ i vào một dòng(=L-S)}
Vậy cách phân trang tối ưu i từđầu chính là cách phân trang tốt nhất củacác cách phân
trang pt
j
vớij=1, 2,..., i. Ta thấy các bài toán con chính là tìm hệ số phạt (nhỏ nhất)của cách
phân trang tối ưu i từ đầu với i = 1, 2,..., N. Hệ số phạt nhỏ nhấtcủa cách phân trang N từ
chính là kết quả của cách phân trang tối ưu N từ đầu.
Ta sẽ dùng một mảng h[0..n],h[i] - là hệ số phạt (nhỏ nhất) của cách phân trang tối ưu nhất
các từ có sốthứ tự từ 1 đến i.
Chương trình sau thể hiện thuậttoán trên.
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+}
{$M 65000,0,655360} {mở rộngStack}
Uses crt;
Const maxn = 4000;
fi = 'ptrang.inp';
fo = 'ptrang.out';
Var h, tr, w : array[0..maxn] of integer;
n, L, kq :integer;
Procedure docf;
var f : text;
k : integer;
Begin
assign(f,fi);
reset(f);
readln(f,n,L);
for k:=1 to n do read(f,w[k]);
close(f);
for k:=1 to n do h[k]:=-1; {tất cả các bài toán đều chưa giải}
h[0]:=0; {giải bài toán con nhất là không có từ nào}
End;
Function maxso(u,v:integer):integer;
Begin
if u>v then maxso:=u else maxso:=v;
End;
Function hsp(i:integer):integer;{hệsố phạt tối ưu nhất của cách phân trang các từ 1 đến i}
var j,s,min : integer;
Begin
if h[i]=-1 then {chưa được làm}
begin
s:=w[i];
j:=i;
h[i]:=maxint;
while (s<=L)and(j>0) do
begin
min:=maxso(hsp(j-1),L-s);{từ 1 đến j-1 làm 1 nhómdòng,j đến i làm 1 dòng}
if min<>
begin
h[i]:=min;
tr[i]:=j;
end;
dec(j);
