[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Để hiểu được giải thuật đệ quy quay lui, trước hết ta nhắc lại khái niệm về đệ qui.
1. Đệ quy
1.1 Khái niệm về đệ qui.
Ta nói một khái niệm là đệ qui nếu nó gao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó.
Ví dụ:
1. Số tự nhiên:
a./ 1 là số tự nhiên
b./ X là số tự nhiên nếu X – 1 là số tự nhiên..
2. Hàm n giai thừa ( n!)
a./ o! =1
b./ n!=n(n-1)! nếu n > 0
1.2 Giải thuật đệ quy và thủ tục đệ qui
Nếu lời giải của một bài toán T được thực hiện bằng lời giải của bài toán T’ có dạng giống như T, thì đó là lời giải đệ qui.Giải thuật tương ứng với lời giải như vậy gọi là giải thuật đệ qui.( T’ ở đây hiểu theo nghĩa nó phải nhỏ hơn T)
Thủ tục đệ qui( chương trình con đệ qui) là thủ tục mà trong thủ tục đó có lời gọi tới chính thủ tục đó.
Đặc điểm của thủ tục đệ qui:
a./ Trong thủ tục đệ qui có lời gọi đến chính thủ tục đó.
b./ Mỗi lần gọi lại thủ tục đó thì kích thước bài toán đã thu nhỏ hơn trước.
c./ Có một trường hợp đặc biệt: đó là trường hợp suy biến.
Ví dụ:
1. Tính n!
n! =1.2.3…n
2. Số FIBONACCI.
Dãy số a1, a2, a3 , …, an… được gọi là dáy số fibonacci nếu a1=a2=1, còn từ số thứ 3 trở đi bằng tổng của 2 số đứng ngay trước nó.
Ta có thủ tục đệ quy sau:
Cả hai thủ tục trên ta thấy rất rõ 3 đặc điểm trên của thủ tục đệ quy.
– Thủ tục có lời gọi đến chính thủ tục đó.
– Lần gọi sau kích thước bài toán nhỏ hơn( lần trước tính n!, nhưng lần sau chỉ tính (n-1)!)
– Có trường hợp suy biến( Nếu n=1; gt=1; nếu n ≤ 2 fibo =1).
1.3 Hiệu lực của đệ quy:
Ưu điểm: Sáng sủa, dễ hiểu, thủ tục rất gọn, đơn giản
Nhược điểm: Tính toán nhiều, thời gian thực hiện rất lâu.
1.4 Ví dụ về giải thuật đệ qui trên lưới ô vuông.
Xét bài toán sau:
Cho lưới ô vuông cấp NxM. Trên mỗi ô [i,j] của lưới ghi một số nguyên a[i,j]. Hai ô được gọi là liên thông trực tiếp nếu nó chung cạnh và giá trị tuyệt đối của tổng 2 số ghi trên 2 ô đó là số chẵn. Hãy lập trình giải quyết các công việc sau:
a) Cho biết lưới ô vuông đó có bao nhiêu vùng liên thông( vùng liên thông gồm các ô liên thông trực tiếp hoặc liên thông qua một số trung gian nào đó)
b) Vùng liên thông lớn nhất (có nhiều ô nhất)
Dự liệu vào: Cho trong tệp văn bản LUOI.txt có cấu trúc như sau:
– Dòng đầu tiên ghi hai số nguyên dương n, m là kích thước của lưới
– Dòng thứ i trong N dòng tiếp theo ghi M số nguyên dương là các số ghi trên dòng thứ i của lưới theo thứ tự từ trái qua phải.
Kết quả: Đưa ra tệp văn bản LUOI.out, có cấu trúc như sau:
– Dòng đầu tiên ghi số S là số vùng liên thông của lưới.
– Dòng thứ i trong S dòng tiếp theo là ghi toạ độ của các ô của vùng liên thông thứ i
– Dòng thứ s+2 ghi toạ độ các ô của vùng liên thông lớn nhất.
Cả hai File dự liệu các số trên một dòng ghi cách nhau một dấu cách.
Ví dụ
LUOI.inp
LUOI.out
4 5
0 1 3 1 5
1 1 5 7 8
2 2 4 1 5
0 5 9 10 2
6
(1 1)
(1 2) (1 3) (1 4) (1 5) (2 1) (2 2) (2 3) (2 4) (2 5) (3 4) (3 5)
(2,5)
(3 1) (3 2) (3 3) ( 4 1)
( 4 2) (4 3)
(4 4) (4 5)
(1 2) (1 3) (1 4) (1 5) (2 1) (2 2) (2 3) (2 4) (2 5) (3 4) (3 5)
Nếu chỉ giải quyết câu a thì chương trình là:
Ta chú ý thủ tục procedure lt(x,y : integer); trong thủ tục này gọi tới chính thủ tục này
Để giải quyết trọn vẹn bài toán này( tức là cả câu b, ta đưa thêm biến DEM để đếm số ô của từng vùng, biến MAX để lưu vùng có số ô lớn nhất và bién VMAX để lưu thứ tự vùng có số ô lớn nhất. Khi được một vùng ta được số ô lưu trong biến DEM, ta so sánh DEM với MAX để lưu vùng có ô lớn nhất và thứ tự của vùng này.
Chương trình sau giải quyết trọn ven bài toán trên.
1. Đệ quy
1.1 Khái niệm về đệ qui.
Ta nói một khái niệm là đệ qui nếu nó gao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó.
Ví dụ:
1. Số tự nhiên:
a./ 1 là số tự nhiên
b./ X là số tự nhiên nếu X – 1 là số tự nhiên..
2. Hàm n giai thừa ( n!)
a./ o! =1
b./ n!=n(n-1)! nếu n > 0
1.2 Giải thuật đệ quy và thủ tục đệ qui
Nếu lời giải của một bài toán T được thực hiện bằng lời giải của bài toán T’ có dạng giống như T, thì đó là lời giải đệ qui.Giải thuật tương ứng với lời giải như vậy gọi là giải thuật đệ qui.( T’ ở đây hiểu theo nghĩa nó phải nhỏ hơn T)
Thủ tục đệ qui( chương trình con đệ qui) là thủ tục mà trong thủ tục đó có lời gọi tới chính thủ tục đó.
Đặc điểm của thủ tục đệ qui:
a./ Trong thủ tục đệ qui có lời gọi đến chính thủ tục đó.
b./ Mỗi lần gọi lại thủ tục đó thì kích thước bài toán đã thu nhỏ hơn trước.
c./ Có một trường hợp đặc biệt: đó là trường hợp suy biến.
Ví dụ:
1. Tính n!
n! =1.2.3…n
Mã:
function gt(x:integer):longint;
begin
if x = 0 then
gt:=1;
else
gt:=x*gt(x-1);
end;2. Số FIBONACCI.
Dãy số a1, a2, a3 , …, an… được gọi là dáy số fibonacci nếu a1=a2=1, còn từ số thứ 3 trở đi bằng tổng của 2 số đứng ngay trước nó.
Ta có thủ tục đệ quy sau:
Mã:
[B]function fibo(x: integer): longint;
var
f1,f2 : integer;
Begin
if x<=2 then
fibo:=1
else
fibo:=f(x-2)+ f(x-1);
end;Cả hai thủ tục trên ta thấy rất rõ 3 đặc điểm trên của thủ tục đệ quy.
– Thủ tục có lời gọi đến chính thủ tục đó.
– Lần gọi sau kích thước bài toán nhỏ hơn( lần trước tính n!, nhưng lần sau chỉ tính (n-1)!)
– Có trường hợp suy biến( Nếu n=1; gt=1; nếu n ≤ 2 fibo =1).
1.3 Hiệu lực của đệ quy:
Ưu điểm: Sáng sủa, dễ hiểu, thủ tục rất gọn, đơn giản
Nhược điểm: Tính toán nhiều, thời gian thực hiện rất lâu.
1.4 Ví dụ về giải thuật đệ qui trên lưới ô vuông.
Xét bài toán sau:
Cho lưới ô vuông cấp NxM. Trên mỗi ô [i,j] của lưới ghi một số nguyên a[i,j]. Hai ô được gọi là liên thông trực tiếp nếu nó chung cạnh và giá trị tuyệt đối của tổng 2 số ghi trên 2 ô đó là số chẵn. Hãy lập trình giải quyết các công việc sau:
a) Cho biết lưới ô vuông đó có bao nhiêu vùng liên thông( vùng liên thông gồm các ô liên thông trực tiếp hoặc liên thông qua một số trung gian nào đó)
b) Vùng liên thông lớn nhất (có nhiều ô nhất)
Dự liệu vào: Cho trong tệp văn bản LUOI.txt có cấu trúc như sau:
– Dòng đầu tiên ghi hai số nguyên dương n, m là kích thước của lưới
– Dòng thứ i trong N dòng tiếp theo ghi M số nguyên dương là các số ghi trên dòng thứ i của lưới theo thứ tự từ trái qua phải.
Kết quả: Đưa ra tệp văn bản LUOI.out, có cấu trúc như sau:
– Dòng đầu tiên ghi số S là số vùng liên thông của lưới.
– Dòng thứ i trong S dòng tiếp theo là ghi toạ độ của các ô của vùng liên thông thứ i
– Dòng thứ s+2 ghi toạ độ các ô của vùng liên thông lớn nhất.
Cả hai File dự liệu các số trên một dòng ghi cách nhau một dấu cách.
Ví dụ
LUOI.inp
LUOI.out
4 5
0 1 3 1 5
1 1 5 7 8
2 2 4 1 5
0 5 9 10 2
6
(1 1)
(1 2) (1 3) (1 4) (1 5) (2 1) (2 2) (2 3) (2 4) (2 5) (3 4) (3 5)
(2,5)
(3 1) (3 2) (3 3) ( 4 1)
( 4 2) (4 3)
(4 4) (4 5)
(1 2) (1 3) (1 4) (1 5) (2 1) (2 2) (2 3) (2 4) (2 5) (3 4) (3 5)
Nếu chỉ giải quyết câu a thì chương trình là:
Mã:
Uses crt;
Const
fi = ‘luoi.txt’;
fo = ‘luoi.out’;
d : array[1..4] of integer=(-1,0,1,0);
c : array[1..4] of integer=(0,1,0,-1);
Var
a : array[0..101,0..101] of integer;
b : array[0..101,0..101] of integer;
f : text;
n,m,sh,r,s : integer;
procedure nhap;
var i,j : integer;
begin
assign(f,fi); reset(f);
readln(f,n,m);
for i:=1 to n do
begin
for j:=1 to m do
read(f,a[i,j]);
readln(f);
end;
for i := 0 to n+1 do
for j := 0 to m+1 do
if (i = 0) or (i = n+1)or(j = 0)or( j = m+1) then
b[i,j] :=-1
else
b[i,j] := 0;
sh := 0;
close(f);
end;
function kiemtra(p,q : integer) : boolean;
var t : integer;
begin
t :=abs(p+q);
if t mod 2 = 0 then
kiemtra := true
else
kiemtra :=false;
end;
procedure lt(x,y : integer);
var k : integer;
begin
b[x,y] := sh;
for k := 1 to 4 do
if (kiemtra(a[x,y],a[x+d[k],y+c[k]]))and(b[x+d[k],y+c[k]] = 0) then
lt(x + d[k], y + c[k]);
end;
[B]procedure thong_bao[/B];
var t,i,j : integer;
begin
assign(f,fo);rewrite(f);
writeln(f,’ so vung lien thong la: ‘,sh);
for t := 1 to sh do
begin
write(f, ‘vung lien thong thu ‘, t,’ : ‘);
for i := 1 to n do
for j := 1 to m do
if b[i,j] = t then
write(f,'(‘,i,’,’,j,’)’,’ ‘);
writeln(f);
end;
end;
{============= Chuong trinh chinh ====================}
BEGIN
nhap;
for r:=1 to n do
for s:=1 to m do
if b[r,s] = 0 then
begin
inc(sh);
lt(r,s);
end;
thong_bao;
close(f);
END.Ta chú ý thủ tục procedure lt(x,y : integer); trong thủ tục này gọi tới chính thủ tục này
Để giải quyết trọn vẹn bài toán này( tức là cả câu b, ta đưa thêm biến DEM để đếm số ô của từng vùng, biến MAX để lưu vùng có số ô lớn nhất và bién VMAX để lưu thứ tự vùng có số ô lớn nhất. Khi được một vùng ta được số ô lưu trong biến DEM, ta so sánh DEM với MAX để lưu vùng có ô lớn nhất và thứ tự của vùng này.
Chương trình sau giải quyết trọn ven bài toán trên.
Mã:
Uses crt;
Const
fi = ‘luoi.txt’;
fo = ‘luoi.out’;
d : array[1..4] of integer=(-1,0,1,0);
c : array[1..4] of integer=(0,1,0,-1);
Var
a : array[1..100,1..100] of integer;
b : array[0..101,0..101] of integer;
f : text;
n,m,sh,max : integer;
vmax,dem,r,s : integer;
[B]procedure nhap;[/B]
var i,j : integer;
begin
assign(f,fi);reset(f);
readln(f,n,m);
for i:=1 to n do
begin
for j:=1 to m do
read(f,a[i,j]);
readln(f);
end;
for i := 0 to n+1 do
for j := 0 to m+1 do
if (i = 0) or (i = n+1)or(j = 0)or( j = m+1) then
b[i,j] :=-1
else
b[i,j] := 0;
max := – maxint;
sh := 0;
close(f);
end;
function kiemtra(p,q : integer) : boolean;
var t,i : integer;
begin
t :=abs(p+q);
if t mod 2 = 0 then
lienthong := true
else
kiemtra :=false;
end;
procedure lt(x,y : integer);
var k : integer;
begin
b[x,y] := sh;
for k := 1 to 4 do
if (kiemtra(a[x,y], a[x+d[k],y+c[k]]))and(b[x+d[k],y+c[k]]= 0) then
begin
inc(dem);
lt(x + d[k], y + c[k]);
end;
if dem > max then
begin
max : = dem;
vmax : =sh;
end;
end;
procedure thong_bao
var t,i,j : integer;
begin
assign(f,fo);rewrite(f);
writeln(f,’ so vung lien thong la: ‘,sh);
for t := 1 to sh do
begin
write(f, ‘vung lien thong thu ‘, t,’ : ‘);
for i := 1 to n do
for j := 1 to m do
if b[i,j] = t then
write(f,'(‘,i,’,’,j,’)’,’ ‘);
writeln(f);
end;
writeln(f,’ so vung lien thong lon nhat la: ‘);
for i:=1 to n do
for j:=1 to m do
if b[i,j] = vmax then
write(f,'(‘,i,’,’,j,’)’,’ ‘);
end;
{============= Chuong trinh chinh ====================}
BEGIN
nhap;
for r:=1 to n do
for s:=1 to m do
if b[r,s] = 0 then
begin
dem:=1;
inc(sh);
lt(r,s);
end;
thong_bao;
close(f);
END.
Last edited:
