Tài liệu Bài giảng chuyên đề về giải thuật đệ quy quay lui

Mô tả:

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 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: 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à: 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; 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; end;