THUẬT TOÁN ĐỆ QUY MINH HỌA BẰNG FREE PASCAL - Tài Liệu Text

Tải bản đầy đủ (.pdf) (15 trang)

1. Trang chủ
>>
2. Công Nghệ Thông Tin
>>
3. Kỹ thuật lập trình

THUẬT TOÁN ĐỆ QUY MINH HỌA BẰNG FREE PASCAL

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 (542.25 KB, 15 trang )

THUẬT TOÁN ĐỆ QUYMINH HỌA BẰNG FREE PASCALTrong thế giới lập trình, có rất nhiều thuật toán như: các thuật toán tìm kiếm, sắp xếp, quy hoạchđộng, đồ thị,... Trong đó có một thuật toán rất nổi tiếng, đó là Đệ quy.Nếu bạn là một người đã và đang học lập trình, chắc hẳn bạn đã tìm hiểu hoặc ít nhất cũng nghe nóivề thuật toán kinh điển này. Thuật toán này được ứng dụng cũng khá rộng rãi trong tin học và cảtoán học. Có rất nhiều bài toán được giải quyết bằng thuật toán Đệ quy rất hiệu quả. Thậm chí cónhững bài toán chỉ có thể suy nghĩ theo cách Đệ quy mới giải quyết được.Edited by: Nguyễn Khắc NhoPage 11. Vấn đề Đệ quy1.1. Các ví dụ:Ví dụ 1: Hãy tính S(n) = 1+2+3+…+n (tính tổng của n số nguyên dương đầu tiên).Nếu n = 10, chúng ta có thể giải bằng cách cộng 10 số nguyên dương đầu tiên, kết quả là 55:S(10) = 1+2+3+…+10 = 55Nếu tính tiếp n = 11 chúng ta cũng có thể giải bài toán với như trên, nghĩa là cộng 11 số nguyêndương đầu tiên và kết quả là 66. Tuy nhiên trong thực tế để tính S(11) khi đã biết S(10) người ta lấykết quả của S(10) cộng thêm cho 11:S(11) = S(10) + 11 = 66Bài toán tính S(n) được giải tổng quát qua hai bước phân tích và thế ngược như sau:(1) Bước phân tích: Để tích S(n) trước tiên chúng ta phải tính S(n-1), sau đó tính S(n) = S(n-1) + n. Để tích S(n-1) trước tiên chúng ta phải tính S(n-2), sau đó tính S(n-1) = S(n-2) + n-1. … Để tích S(2) trước tiên chúng ta phải tính S(1), sau đó tính S(2) = S(1) + 1. Và cuối cùng S(1) có ngay kết quả là 1.Bước phân tích của bài toán tính S(n)S(n) = S(n-1) + nS(n-1) = S(n-2) + n-1……S(2) = S(1) + 1S(1) = 1(2) Bước thế ngược:Có kết quả của S(1) chúng ta thay nó vào biểu thức tính S(2) và tính được S(2), có S(2) chúng ta sẽtính được S(3),…, có S(n-1) chúng ta sẽ tính được S(n), và bài toán đã được giải quyết.Bước thế ngược của bài toán tính S(n)S(1)= 1S(2) = S(1) + 2 = 3S(3) = S(2) +3 = 6…S(n) = S(n-1) + nVí dụ 2: Tính P(n) = xn với x là số thực và n là số nguyên ≥ 0.Tương tự như bài toán trên, bài toán tính P(n) được giải tổng quát qua hai bước là bước phân tích vàbước thế ngược như sau:(1). Bước phân tích:Để tính P(n) trước tiên chúng ta phải tính P(n-1), sau đó tính P(n) = P(n-1) * x.Để tính P(n-1) trước tiên chúng ta phải tính P(n-2), sau đó tính P(n-1) = P(n-2) * x.…Để tính P(1) trước tiên chúng ta phải tính P(0), sau đó tính P(1) = P(0) * x.Và cuối cùng P(0) có ngay kết quả là 1.Bước phân tích của bài toán tính P(n)Edited by: Nguyễn Khắc NhoPage 2P(n) = P(n-1) * xP(n-1) = P(n-2) + x……P(1) = P(0) * 1P(0) = 1(2). Bước thế ngược:Có kết quả của P(0) chúng ta thay nó vào biếu thức tính P(1) và tính được P(1), có P(1) chúng ta sẽtính được P(2),…, có P(n-1) chúng ta sẽ tính được P(n), và bài toán đã được giải quyết.Bước thế ngược của bài toán tính S(n)P(0)= 1P(1) = P(0) * x = xP(2) = P(1) * x = x*x…P(n) = P(n-1) * xLưu ý:Trong quá trình giải hai bài toán trên giống nhau ở chỗ đều tiến hành giải qua hai bước làbước phân tích và bước thế ngược.Ở bước phân tích, bài toán lớn được phân tích thành bài toán đồng dạng (nhưng đơn giảnhơn). Bước phân tích sẽ dừng lại khi chúng ta phân tích đến bài toán đồng dạng đơn giảnnhất mà ở đó chúng ta có thể xách định kết quả một cách trực tiếp.Ở bước thế ngược giúp chúng ta tuần tự xác định kết quả các bài toán đồng dạng (từ đơngiản đến phức tạp hơn), và cuối cùng chúng ta sẽ xác định được kết quả của bài toán.1.2. Vấn đề Đệ quy là gì?Vấn đề Đệ quy là vấn đề được định nghĩa bằng chính nó, ví dụ:Tính tổng S(n) (tính tổng n số nguyên dương đầu tiên) được định nghĩa thông qua S(n-1)(tính tổng n-1 số nguyên dương đầu tiên).Tính P(n) ( tính xn) được định nghĩa thông qua P(n-1) (tính (xn-1).Vấn đề Đệ quy thường được giải qua hai bước là bước phân tích và bước thế ngược. Bài toán (hayvấn đề) giải quyết theo phương pháp Đệ quy cần hai điều kiện sau để hiện hữu (tồn tại) tính Đệ quyvà không bị gọi Đệ quy bất tận (bị loop):(1). Để hiện hữu (tồn tại) tính Đệ quy – nghĩa là để giải một bài toán chúng ta phải giải các bàitoán đồng dạng, để giải bài toán đồng dạng này chúng ta phải giải bài toán đồng dạng khác – phảitồn tại bước Đệ quy. Bài toán 1 có bước Đệ quy là S(n) = S(n-1) + n, bài toán 2 có bước Đệ quy làxn=xn-1*x(2). Để không bị gọi Đệ quy bất tận (bị loop) thì phải có điều kiện dừng. Bài toán 1 có điều kiệndừng là S(1) = 1, bài toán 2 có điều kiện dừng là x0 =1.=> Bài toán Đệ quy là những bài toán này có thể được phân rã thành các bài toán nhỏ hơn, đơn giảnhơn nhưng có cùng dạng với bài toán ban đầu. Những bài toán nhỏ lại được phân rã thành các bàitoán nhỏ hơn. Cứ như vậy, việc phân rã chỉ dừng lại khi bài toán con đơn giản đến mức có thể suyra ngay kết quả mà không cần phải phân rã nữa. Ta phải giải tất cả các bài toán con rồi kết hợp cáckết quả đó lại để có được lời giải cho bài toán lớn ban đầu. Cách phân rã bài toán như vậy gọi là"chia để trị" (devide and conquer), là một dạng của Đệ quy.2. Chương trình con Đệ quyEdited by: Nguyễn Khắc NhoPage 3Một chương trình con (hàm hoặc thủ tục) được gọi là Đệ quy nếu trong quá trình thực hiện nó cóphần phải gọi đến chính nó.Ví dụ 1: Hàm tính lũy thừa nguyên của một số thực x (tính xn).Function LT(x: real, n: integer): real;BeginIf n=0 then LT:=1 elseLT:=LT(x,n-1)*x;End;Khi có lệnh gọi hàm, chẳng hạn: a:=LT(3,4);Thì máy sẽ nhớ là: LT(3,4):=3*LT(3,3) và đi tính LT(3,3);Kế tiếp máy lại phải ghi nhớ: LT(3,3):=3*LT(3,2) và đi tính LT(3,2);Kế tiếp máy lại phải ghi nhớ: LT(3,2):=3*LT(3,1) và đi tính LT(3,1);Kế tiếp máy lại phải ghi nhớ: LT(3,1):=3*LT(3,0) và đi tính LT(3,0);Theo định nghĩa của hàm LT: LT(3,0):=1;Máy sẽ quay ngược lại: LT(3,1):=3*1=3;Rồi tiếp tục quy ngược lại: LT(3,2):=3*3=9; LT(3,3):=9*3=27; LT(3,4):=27*3:=81;Ví dụ 2: Hàm tính giai thừa của n (tính n!).Function GT(n: word): longint;BeginIf n=1 then GT:=1 elseGT:=GT(n-1)*n;End;3. Cấu trúc chính của một chương trình con Đệ quyMột chương trình con Đệ quy vè căn bản gồm 2 phần:(1). Phần cố định (điều kiện dừng):Trong đó chứa các tác động của hàm hoặc thủ tục với với một số giá trị của thể ban đầu của thamsố.Trong ví dụ 1: If n=0 then LT:=1;Trong ví dụ 2: If n=1 then GT:=1;(2). Phần hạ bậcTrong đó tác động cần được thực hiện cho giá trị hiện thời của các tham số được định nghĩa bằngcác tác động đã được định nghĩa trước đây với kích thước nhỏ hơn của tham số:Trong ví dụ 1: If n > 0 then LT:=LT(x,n-1)*x;Trong ví dụ 2: If n > 1 then GT:=GT(n-1)*n;4. Các loại Đệ quy4.1. Đệ quy đuôiĐệ quy đuôi là dạng Đệ quy mà trong một cấp Đệ quy, chỉ có lời gọi Đệ quy duy nhất xuống cấpthấpVí dụ 1: Hàm tính giai thừa của n (tính n!).Funtion GT(n: word): longint;Edited by: Nguyễn Khắc NhoPage 4BeginIf n:=1 then GT:=1 elseGT:=GT(n-1)*n;End;Ví dụ 2: Tìm vị trí xuất hiện của số x trong dãy a gồm n số được sắp tăng dần. Ta giải bài toán nàybằng tìm kiếm nhị phân.Tư tưởng thuật toán: Xét số ở chính giữa dãy số gội là phần tử giữa, nếu x lớn hơn số này, nghĩalà x phải nằm ở dãy số phía bên phải phần tử giữa, nếu x nhỏ hơn thi x phải nằm ở dãy số bên tráiphần tử giữa, nếu x bằng giữa thì đã tìm được x.Type DaySo=Array[1..100] of integer;Function Tim(a:Dayso;left, right:integer): integer;BeginIf (left>right) then Tim:= -1ElseBeginMid:=(right+left) div 2;If (a[mid]=x) then Tim:=midElseIf x>a[mid] then Tim(mid+1,right)Else Tim:=Tim(left, mid -1);End;End;Nhận xét: Chúng ta thấy lời gọi Đệ quy xuất hiện hai lần trong hàm (Tim(mid+1,right) và Tim(left,mid -1), nhưng trong một lần thi hành hàm chỉ một trong hai được thi hành.4.2. Đệ quy nhánhĐệ quy nhánh là dạng Đệ quy mà trong suốt quá trình thực hiện hàm Đệ quy, lời gọi hàm Đệ quyđược thực hiện nhiều hơn một lần.Ví dụ 1: Bài toán tháp Hà NộiCho n dĩa tròn có kích thước khác nhau và được đặt xuyên qua một cọc sao cho dĩa nhỏ ở trên dĩato. Hãy chuyển toàn bộ số dĩa này sang một cọc khác với điều kiện: Khi chuyển, khi chuyển, có thểchuyển dĩa sang một cọc trung gian khác và trên mỗi cọc, dĩa nhỏ luôn nằm trên dĩa lớn.Để đơn giản, gọi cọc nguồn là cọc A, cọc đích là B và cọc trung gian là cọc C. Các dĩa được đánhsố theo thứ tự từ 1 đến n. Dĩa có số lớn hơn thì đường kính lớn hơn.Thuật giải Đệ quyĐể chuyển n dĩa từ cọc A sang cọc B thì cần:1. chuyển n-1 dĩa từ A sang C. Chỉ còn lại dĩa n trên cọc A2. chuyển dĩa n từ A sang B3. chuyển n-1 dĩa từ C sang B cho chúng nằm trên dĩa nEdited by: Nguyễn Khắc NhoPage 5Phương pháp trên được gọi là thuật giải Đệ quy: Để tiến hành bước 1 và 3, áp dụng lại thuật giảicho n-1. Toàn bộ quá trình là một số hữu hạn các bước, vì đến một lúc nào đó thuật giải sẽ áp dụngcho n = 1. Bước này chỉ đơn giản là chuyển một dĩa duy nhất từ cọc A sang cọc C.Giải thích thuật giải với n=3:1. chuyển đĩa 1 sang cọc C2. chuyển đĩa 2 sang cọc B3. chuyển đĩa 1 từ C sang B sao cho nó nằm lên 2Vậy ta hiện có 2 đĩa đã nằm trên cọc B, cọc C hiện thời trống1. chuyển đĩa 3 sang cọc C2. lặp lại 3 bước trên để chuyển 1 & 2 cho nằm lên 3Mỗi lần dựng xong tháp từ đĩa i đến 1, chuyển đĩa i+1 từ cọc A là cọc xuất phát, rồi lại di chuyểntháp đã dựng lên đĩa i+1.Program ThapHaNoi;Var n:integer;Procedure ChuyenDia(n:integer; nguon,dich:char);Beginwriteln('chuyen dia: ',n,' tu coc ',nguon,' sang coc ',dich);End;Procedure ChuyenChongDia(n:integer; nguon,dich:char);Var trunggian:char;Beginif(nguon'A') and (Dich'A') then trunggian:='A';if(nguon'B') and (Dich'B') then trunggian:='B';if(nguon'C') and (Dich'C') then trunggian:='C';if n=1 then ChuyenDia(n,nguon,dich)else BeginChuyenChongDia(n-1,nguon,trunggian);ChuyenDia(n,nguon,dich);ChuyenChongDia(n-1,trunggian,dich);End;End;BeginWrite('Nhap vao so dia: '); readln(n);ChuyenChongDia(n,'A','B');readlnEnd.Nhận xét: Trong một lần thi hành, có hai lời gọi Đệ quy – Đệ quy rẽ nhánh.Ví dụ 2: Liệt kê tất cả hoán vị của một dãy n phần tử khác nhau (tổng số hoán vị của dãy n phần tửlà n!). Chẳng hạn với dãy có 3 phần tử là ABC thì tất cả hoán vị là ABC, ACB, BAC, BCA, CAB,CBA.Tư tưởng của thuật toán này như sau:Xét các phần tử ai từ 1 đến n (n là chiều dài dãy số - DaySo):+ Bỏ phần tử ai ra khỏi dãy số.+ Ghi nhận đã lấy ra phần tử ai.+ Hoán vị (dãy số).Edited by: Nguyễn Khắc NhoPage 6+ Đưa phần tử ai vào lại dãy sốNếu dãy số rỗng thì thứ thự các phần tử được lấy ra chính là một hoán vị.Ví dụ: Dãy số ABCBỏ A (còn BC)Bỏ B (còn C)Bỏ C -> 1 hoán vị ABCBỏ C (còn B)Bỏ B -> 1 hoán vị ACBBỏ B (còn AC)Bỏ A (còn C)Bỏ C -> 1 hoán vị BACBỏ C (còn A)Bỏ A -> 1 hoán vị BCABỏ C (còn AB)Bỏ A (còn B)Bỏ B -> 1 hoán vị CABBỏ B (còn A)Bỏ A -> 1 hoán vị CBAProgram HoanViDaySo;Var Day: Array[1..10] of char; // mảng lưu các phần tửSoKyTu,i: Integer;// Số phần tửDuocChon: Array[1..10] of boolean;//ghi nhận phần tử nào đã lấy ra khỏi dãyProcedure HoanVi(kytu:string);Var i:integer;Chon: Boolean;// =false, không còn ký tự nào để lấy ra nữa, dãy rỗng.Beginchon:=false;for i:=1 to SoKyTu do Beginif (DuocChon[i]=false) then BeginDuocChon[i]:=True;HoanVi(KyTu+Day[i]); // Lời gọi Đệ quy được gọi nhiều lần trong vòng lặpDuocChon[i]:=false;Chon:=true;End;End;if chon=false then writeln(KyTu);// dãy rỗng các phần tử đã chọn theo thứ tự là 1 HV.End;BeginWrite('Nhap vao so phan tu cua day: '); readln(SoKyTu);For i:=1 to SoKyTu do BeginWrite('Nhap vao phan tu thu ',i,': ');readln(Day[i]);End;For i:=1 to SoKyTu Do DuocChon[i]:=false;Edited by: Nguyễn Khắc NhoPage 7hoanvi('');readlnEnd.4.3. Đệ quy tương hỗ tươngĐệ quy hỗ tương là dạng Đệ quy mà trong đó có sự gọi quay vòng như A gọi B, B gọi C rồi C lạigọi A. Đây là trường hợp rất phức tạp nhưng cũng có nhiều ví dụ rất hấp dẫn.Ví dụ: Viết chương trình tính X(n) và Y(n). X(n) và Y(n) được xác định bởi công thức sau:( ) = ( − 1) + ( − 1)A(0) và B(0) =1( ) = ( − 1) ∗ ( − 1)Cây nhị phân biểu diễn tính A(3) và B(3) như sau:Chương trình:Program TinhXnVaYn;Var n:byte;Function TinhYn(n:byte): longint; forward;// Từ khóa dùng để khai báo trước tên hàm.Function TinhXn(n:byte): longint; forward;// Nếu không có thì không thể sự dụng Đệ quyFunction TinhXn(n:byte): longint;// tương hỗEdited by: Nguyễn Khắc NhoPage 8Beginif n=0 then TinhXn:=1else TinhXn:=TinhXn(n-1)+TinhYn(n-1);End;Function TinhYn(n:byte): longint;Beginif n=0 then TinhYn:=1else TinhYn:=TinhXn(n-1)*TinhYn(n-1);End;BeginWrite('Nhap vao n: '); readln(n);Writeln('Gia tri cuar X(',n,') la: ',TinhXn(n));Write('Gia tri cuar Y(',n,') la: ',TinhYn(n));readlnEnd.5. Ưu và nhược điểm của Đệ quy5.1. Ưu điểmĐệ quy mạnh ở chỗ có thể định nghĩa một tập hợp rất lớn các tác động chỉ bởi một số ít mệnh đề.Một chương trình viết theo giải thuật Đệ quy sẽ tự nhiên hơn đó là:+ Sáng sủa+ Dễ hiểu+ Nêu bật được bản chất của vấn đề.Có nhiều bài toán cho đến nay vẫn chưa có cách giải không Đệ quy.5.2. Nhược điểmTrong giải thuật Đệ quy các bài toán con có thể được gọi lại rất nhiều lần, dù trước đó kết quả củabài toán con đã được tính rồi. Nên thực hiện giải thuật Đệ quy sẽ:+ Tốn nhiều dung lượng+ Cực kỳ chậm6. Khử Đệ quyCó một số giải thuật Đệ quy thuộc loại tính toán đơn giản có thể được thay thế bởi một giải thuậtkhác không tự gọi nó, sự thay thế đó được gọi là khử Đệ quy.Tuy nhiên, như vậy không có nghĩa là phải khử Đệ quy bằng mọi giá và cũng không e ngại cũngnhư ác cảm với việc dùng Đệ quy.6.1. Khử Đệ quy bằng vòng lặpQuy tắc: Chuyển tham số Đệ quy thành biến đếm của vòng lặpPhương pháp vòng lặp thường được áp dụng với kiểu Đệ quy đuôi. Nếu quan sát thấy hình ảnh “cáiđuôi” trong Đệ quy đuôi, ta nhận thấy đó là là một dãy thao tác được lặp đi lặp lại với quy mô“nhỏ” dần cho đến lúc đạt được trạng thái dừng. Đặc tính này cũng tương tự ý niệm của vòng lặp:Lặp lại dãy thao tác cho đến lúc gặp điều kiện dừng. Nếu ta có thể chuyển đổi từ quy mô bài toánsang điều kiện thi hành (hoặc điều kiện dừng) của vòng lặp thì ta có thể khử được lời gọi Đệ quybằng vòng lặp.Ví dụ 1: Tính giai n!Điều kiện dừng của thật toán Đệ quy là n=2, và đó cũng là điều kiện dừng của vòng lặpEdited by: Nguyễn Khắc NhoPage 9Cách 1: Đệ quyvar n:integer;Function GT(n:integer): integer;Beginif n right). Ta sẽ dùng biểu thức này làm điều kiện dừng của vòng lặp.Program Timkiemnhiphan;Type Dayso=Array[1..1000] of integer;Var a:DaySo; n,x,i:integer;Function Tim(a:dayso): integer;Var TimThay: Boolean;left, right, mid: integer;BeginTim:=-1; TimThay:=False; //Ban đầu xem như không tim thấyleft:=1;right:=n; // tìm trên toàn bộ mảngWhile(lefta[mid] then left:=mid+1 //Thu hẹp dãy số chỉ còn nửa bên phảielse right:=mid-1; //Thu hẹp dãy số chỉ còn nửa bên tráiEnd;write('Vi tri gia tri can tim trong day la: ',tim);Edited by: Nguyễn Khắc NhoPage 10End;BeginWrite('Nhap vao so can tim: '); readln(x);Write('nhap vao so phan tu cua day: '); readln(n);For i:=1 to n do BeginWrite('nhap vao phan tu thu ',i,' cua day: ');readln(a[i]); // Chú ý nhập dãy số là dãy tăngEnd;Tim(a);readlnEnd.So sách Đệ quy và vòng lặp:Đệ QuyVòng LặpCẤU TRÚC LẶPXây dựng cấu trúc tùy ý, thường là Sử dụng vòng lặp của NNLT: Cóchương trình con. Tự gọi lại chính hai loại là lặp với số lần biết trướcnó để sinh ra vòng lặp.và lặp với số lần chưa biết trước.ĐIỂM DỪNGKhi gặp trường hợp cơ sở của quá Khi điều kiện duy trì vòng lặptrình Đệ quy.không còn thỏa mãn.QUÁLẶPĐi từ trường hợp ban đầu đến Là vòng lặp đơn thuần. Sau mỗiTRÌNH trường hợp cơ sở. Tại mỗi bước bước giá trị “biến đếm” thay đổ đểlặp độ phức tạp của bài toán giảm đi đến điểm dừng.dần.LẶP VÔ HẠNSO SÁCHƯU NHƯỢCĐIỂMCác bước Đệ quy không thể làm Nếu điều kiện duy trì vòng lặpđơn giản bài toán. Chương trình không bao giờ sai thì sẽ lặp vô hạnkhông thể hội tụ về trường hợp cơsở.Ưu: Đệ quy có thể giải quyết tốtmột số bài toán dạng vòng lặp mộtcách dễ dàng hơn. Chương trìnhthiết kế đơn giản. Dễ đưa raphương án tối ưu, giải quyết đượcmột số vấn đề vòng lặp thôngthường không giải quyết được.Ưu: Ít tốn bộ nhớ, dễ dàng trongviệc quản lý các vòng lặp. Quátrình thiết kế vòng lặp cũng đơngiản hơn rất nhiều so với Đệ quy.Nhược: Do có nhiều bài toán con Nhược: Nhiều bài toán vòng lặpđược gọi lại khi đã được gọi trước thông thường không giải quyếtđó rồi, nên Đệ quy rất tốn bộ nhớ, được phải nhờ đến Đệ quy.quản lý không tốt sẽ bị tràn bộnhớ.6.2. Khử Đệ quy bằng stack tự tạoQuy tắc: Chỉ đưa vào stack những tham số có ý nghĩa trong quá trình Đệ quyPhương pháp này thường được dùng trong đệ quy nhánh. Khi có lời gọi Đệ quy, chương trình tựđộng Push vào stack toàn bộ biến cục bộ và tham số của hàm đệ quy. Dù ta có tiết kiệm bộ nhớ tốiđa, nhưng chương trình vẫn phải sử dụng lượng biến cục bộ nhất định nào đó. Tuy nhiên, nhữngbiến cục bộ này đôi lúc lại không cần thiết trong quá trình Đệ quy. Trong những trường hợp đó,Edited by: Nguyễn Khắc NhoPage 11người ta tạo ra stack riêng và chỉ push vào stack những biến có ý nghĩa trong quá trình Đệ quy.Ngoài ra, việc tự tạo một stack riêng còn có một lợi điểm nữa là có thể tạo ra được một stack cókích thước lớn từ đó có thể tăng độ sâu đệ quy; trong khi đó stack do chương trình tự tạo ra thườngcó kích thước rất hạn chế và như vậy sẽ hạn chế độ sâu của đệ quy. Xét cho cùng phương phápstack tự tạo không phải phương pháp khử đệ quy (tuy rằng nó làm mất đi các lời gọi đệ quy) mà chỉlà phương án tối ưu sử dụng bộ nhớ để làm tăng độ sâu của đệ quy mà thôi.Nhìn chung, khử đệ quy bằng stack là một kỹ thuật khó. Cấu trúc của stack và của một thành phầnsẽ biến động tùy theo chương trình đệ quy. Thông thường, khử đệ quy bằng stack tự tạo đòi hỏi taphải tiến hành phân tích thật tỉ mỉ chương trình đệ quy.Các bước thực hiện:Khởi tạo stack với số phần tử phù hợp.Đưa bộ tham số đầu vào stack.Khi Stack không trống:+ Lấy bộ tham số ra khỏi stack;+ Xử lý các tác vụ cơ bản ứng với tham số này. Nếu gặp 1 tác vụ đệ quy thì lại đưa bộtham số của tác vụ đệ quy tương ứng vào stackVí dụ: Cho một hình kín bất kỳ và một điểm (x0, y0) nằm bên trong hình đó, hãy tô màu phần bêntrong hình đó.Ta giải bài toán này bằng phương pháp tô loang. Nghĩa là từ điểm (x0, y0) ban đầu, ta tô loang ra 4điểm kế điểm đó là (x0+1, y0), (x0-1, y0), (x0, y0+1), (x0, y0-1). Và từ 4 điểm này ta lại tiếp tục tô 4điểm kế tiếp nếu điểm đó chưa được tô màu hoặc có màu trùng với màu biên. Quá trình này cứ tiếptục cho đến lúc không còn điểm nào để tô. Người ta gọi thuật toán này là thuật toán FloodFill.Cách 1: Sử dụng thuật toán đệ quyEdited by: Nguyễn Khắc NhoPage 12Program FloodFill;Var Matran: Array[0..9,0..9] of Byte;maubien,i,j: byte;Procedure Inmatran;BeginFor i:=0 to 9 doBeginFor j:=0 to 9 dowrite(matran[i,j]:3);writeln;End;End;Procedure Fill(x,y:integer; Mau:integer);BeginIf (Matran[x,y]MauBien) and (Matran[x,y]mau) thenBeginMatran[x,y]:=mau;if x0 then Fill(x-1,y,mau);if y0 then Fill(x,y-1,mau);End;End;Beginmaubien:=1; // màu đường biênWriteln('Ma tran truoc khi FloodFill');inmatran;fill(4,3,2);Writeln('Ma tran sau khi FloodFill');inmatran;readlnEnd.Cách 2: Sử dụng stack tự tạo:Giả sử đã có các chương trình con sau: {chúng ta sẽ tham khảo cách tạo và sử dụng ngăn xếp và vàhàng đợi ở chuyên đề “CẤU TRÚC DỮ LIÊU NÂNG CAO”.+ Thủ tục Push (x,y:integer) cho phép push vào ngăn xếp tọa độ một điểm+ Thủ tục Pop (var x,y:integer) cho phép lấy ra tọa độ của một điểm ở đầu ngăn xếp.+ Hàm IsStackEmpty cho biết stack có rỗng hay không.Thủ tục tô màu như sau:Procedure Fill(x0,y0:integer; Mau:Byte);Var x,y:integer;BeginTop:=-1;Push(x0,y0);While IsStackEmpty=False Do BeginPop(x,y);Edited by: Nguyễn Khắc NhoPage 13If (Matran[x,y]MauBien) and (Matran[x,y]mau) thenBeginMatran[x,y]:=mau;if x0 then Fill(x-1,y,mau);if y0 then Fill(x,y-1,mau);End;End;End;7. Một số bài toán.Bài toán 1: Bài toán tính phần tử thứ n của dãy Fibonacci:Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1, các phần tử sau đóđược thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Công thức truy hồicủa dãy Fibonacci là:Sơ đồ gọi đệ quy với bài toán tính F(6):Phần cố định: n=0 hoặc n= 1 thì F(n)=nPhần hạ bậc: F(n)=F(n-1)+F(n-2)Code:Program Fibonacci;Var n:byte;Function Fi(n:byte):longint;Beginif n0Phần cố định: n=1 thì S(n) = 1.Phần hạ bậc: S(n)=S(n-1)+1/n.Code:Var n:integer;Function TinhS(n:integer): real;Beginif n=1 then TinhS:=1else TinhS:=TinhS(n-1)+1/nEnd;BeginWrite('Nhap vao so n: '); readln(n);Write('Gia tri cua day so la: ',TinhS(n):4:1);readlnEnd.Bài toán 3: Tính S(n)=1+1.2+1.2.3+…+1.2.3…n với n>0Phần cố định: n≤ 1 thì S(n)=n;Phần hạ bậc: S(n)=S(n-1)+ n!Code:Var n:byte;Function Gt(n:byte): longint;Beginif n