Chuyên đề Bd Hsg: đệ Quy Và đệ Quy Quay Lui - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.docx) (8 trang)

Trang chủ

Công Nghệ Thông Tin

Kỹ thuật lập trình

chuyên đề bd hsg: đệ quy và đệ quy quay lui

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 (244.4 KB, 8 trang )

Tài liệu bồi dưỡng học sinh giỏi THPT – Môn Tin họcPhần II: Chuyên đề nâng caoCHUYÊN ĐỀ NÂNG CAO 4CHUYÊN ĐỀ 4: ĐỆ QUY VÀ ĐỆ QUY QUAY LUIA. ĐỆ QUYI. LÝ THUYẾT ĐỆ QUY1. 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 n1 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(hay vấ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ài toá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ải tồntạ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*x2) Để 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ện dừnglà 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ản hơnnhư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ài toá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ể suy ra 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ác kế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 andconquer), là một dạng của Đệ quy.2. Chương trình con Đệ quyMộ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ầnphả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 else LT:=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!).Giáo viên: Lê Thanh Phú1|Tra n gTài liệu bồi dưỡng học sinh giỏi THPT – Môn Tin họcFunction GT(n: word): longint;BeginIf n=1 then GT:=1Else GT:=GT(n-1)*n;End;Phần II: Chuyên đề nâng cao3. 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 – Phần Neo (đ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 đầucủa tham số để dừng đệ quy.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ậc đệ quyTrong đó tác động cần được thực hiện cho giá trị hiện thời của các tham số được địnhnghĩa bằng các tác động đã được định nghĩa trước đây với kích thước nhỏ hơn của thamsố: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. Nguyên tắc hoạt động của giải thuật đệ quyKhái niệm stack:Stack là một cấu trúc lưu trữ, hoạt động theo nguyên tắc sau: Mỗi lần nộp vào hoặc lấy ra chỉ thực hiện với một phần tử. Phần tử nộp vào sau sẽ được lấy ra trước.Nguyên tắc hoạt động:• Khi thực hiện một giải thuật đệ quy thì các bước của giải thuật đệ quy sẽ lần lượt được thực hiệntuần tự.• Khi gặp lời gọi đệ quy thì trước khi thực hiện lời gọi đệ quy, đoạn mã lệnh chưa được thực hiệnxong cùng với các đối tượng dữ liệu liên quan tại thời điểm này sẽ được lưu vào stack.• Đến lúc nào đó không thể thực hiện lời gọi đệ quy nữa thì các đối tượng được lưu trong stack sẽlần lượt được lấy ra để xử lý. Ví dụ: Trong ví dụ trên, qui trình thực hiện như sau:• Khi có lệnh gọi hàm, chẳng hạn: x := gt(3); thì máy sẽ ghi nhớ là: gt(3) := 3 * gt(2); và đi tính gt(2)• Kế tiếp máy lại ghi nhớ: gt(2):= 2*gt(1); và đi tính gt(1) • Theo định nghĩa của hàm thì khi gt(1):= 1; máy sẽ quay ngược lại: gt(2):= 2 * 1; và cho kết quả là 2• Tiếp tục: gt(3) := 3 * 2; cho kết quả là 6• Như vậy kết quả cuối cùng trả về là 6. Ta có: 3! = 6.5. Ưu điểm và hạn chế của đệ quyƯu điểm: Mô tả được một số thao tác tính toán thông qua một đoạn lệnh ngắn, làm cho chương trình ngắngọn, dễ hiểu, lộ rõ bản chất đệ quy. Rất thuận tiện để giải quyết các bài toán có bản chất đệ quy. Hiện nay vẫn có nhiều thuật toán chưa có lời giải đệ quy. Nhiều giải thuật rất dễ mô tả dạng đệ quy nhưng lại rất khó mô tả với giải thuật không-đệ-quy. Một chương trình viết theo giải thuật có tính đệ qui sẽ mang tính "người" hơn, do đó sẽ sángsủa, dễ hiểu, nêu bật được bản chất của vấn đề.Hạn chế: Vừa tốn bộ nhớ, chương trình chạy chậmGiáo viên: Lê Thanh Phú2|Tra n gTài liệu bồi dưỡng học sinh giỏi THPT – Môn Tin họcPhần II: Chuyên đề nâng cao Do đệ quy lưu trữ các dữ liệu trung gian vào Stack nên nếu Lưu nhiều bộ dữ liệu lớn trên stacknên có thể gây ra hiện tượng tràn StackII. MỘT SỐ BÀI TẬP:Yêu cầu: Các bài tập sau cần xây dựng chương trình con đệ quy.1. Viết chương trình tính N! (Có sử dụng chương trình con dạng đệ quy)Hướng dẫn:Trường hợp không sử dụng đệ quy, theo cách bình thường ta có chương trình con tính n! như sau:Function GT(n:longint):longint;Var i:longintBeginGT:=1;For i:=1 to N do GT:=GT*i;End;Trường hợp sử dụng đệ quy ta viết như sauFunction GT(n:longint):longint;BeginIf n=0 then GT:=1 else GT:= n * GT(n-1);End;Chương trình: Tự viết2. Viết chương trình tìm số Fibonaci thứ n.HD: Sử dụng đ/n của dãy Fibonaci ta có• F1 = F2 = 1• Fn = Fn-1 + Fn-23. Viết chương trình tính S:1 11s = 1 + + + ... +1 2n4. Viết chương trình tínhS = 1 + 1.2 + 1.2.3 + 1.2.3.4 + … + 1.2.3…n5. Viết chương trình tìm ước chung lớn nhất của hai số a và b.6. Hãy tính tổng các chữ số của số nguyên dương N.7. Tính S(n) = 1/2 + 1/4 + ... + 1/2n8. Tính S(n) = 1 + 1/3 + 1/5 + ... + 1/(2n+1)9. Tìm số đảo ngược.Ví dụ: Số 2345 thì in kết quả đảo ngược là 543210. Tính S(n) = 1/2 + 2/3 + 3/4 + ... + n/(n+1)11. Tính S(n) = 1/2 + 3/4 + 5/6 + ... + (2n+1)/(2n+2)12. Tính lũy thừa của một số: S(x,n) = x^n13. Độ bền của một số nguyên không âm n được định nghĩa như sau:- Nếu N có một chữ số thì độ bền của n bằng 0.- Nếu N có từ 2 chữ số trở lên thì độ bền của n bằng độ bền của số nguyên là tích các chữ số của n cộng1.Viết chương trình nhập số n (0 ≤ n ≤ 1000) từ bàn phím, tìm số bé hơn n có độ bền lớn nhất.Ví dụ: Với n = 100 thì in ra kết quả: So be hon 100 co do ben lon nhat la: 77• Giải thích:Doben(77)=Doben(49)+1=Doben(36)+1+1=Doben(18)+1+1+1= Doben(8)+1+1+1+1=0+1+1+1+1=4Giáo viên: Lê Thanh Phú3|Tra n gTài liệu bồi dưỡng học sinh giỏi THPT – Môn Tin họcPhần II: Chuyên đề nâng caoViết chương trình nhập vào một số n và thông báo ra độ bền của nó.Giáo viên: Lê Thanh Phú4|Tra n gTài liệu bồi dưỡng học sinh giỏi THPT – Môn Tin họcPhần II: Chuyên đề nâng caoB. ĐỆ QUY QUAY LUI (BACK TRACKING)I. LÝ THUYẾT1. Sơ lược về đệ quy quay luiTrong lập trình, phương pháp giải một bài toán tổng quát rất được chú ý. Đó là việc xác định cácgiải thuật để tìm lời giải cho một số bài toán nào đó không theo một luật tính toán cố định bằng phươngpháp "Try and Error" (Thử và sai).Nét đặc trưng của phương pháp này là ở chỗ các bước đi đến lời giải hoàn toàn bằng cách làmthử. Nếu có một lựa chọn được chấp nhận thì ghi nhớ các thông tin cần thiết các bước thử tiếp theo.Trái lại, nếu không có một lựa chọn nào thích hợp thì làm lại bước trước, xoá bớt các ghi nhớ và quay vềchu trình thử với các lựa chọn còn lại. Hành động này được gọi là quay lui (Back tracking) và các giảithuật thể hiện phương pháp này gọi là các giải thuật quay lui.2. Sử dụng đệ quy quay lui trong trường hợp nào:Thường sử dụng trong các chương trình- cần liệt kê kết quả- Cần duyệt qua các phương án để tìm phương án tối ưu (Bài 9, bài toán đặt hòm phiếu..)- Tìm một phương án – Thử  Tìm thấy phương án thì dừng (Ví dụ: Có N con bò, hỏi có thểsắp hàng sao cho hai bò đực phải đứng cách nhau k bò cái)Ví dụ: Liệt kê các hoán vị của số N, Bài toán tám quân hậu, liệt kê dãy nhị phân độ dài N …3. Cấu trúc của Đệ quy quay lui:Procedure Try(j); {Chọn thực hiện bước thứ j}BeginFor CÁC PHƯƠNG ÁN CHỌN doIf CHỌN ĐƯỢC thenBegin- THỰC HIỆN BƯỚC ĐI THỨ j;- IF THÀNH CÔNG then THÔNG BÁO KẾT QUẢ- HỦY BƯỚC ĐI THỨ j; {Quay lui}End;End;ElseTry(j+1);II. BÀI TẬP:1. Liệt kê tất cả hoán vị của tập {1,2, …, N}: N!Ví dụ: N=3 thì tất cả hoán vị là: 123, 132, 213, 231, 312, 321.(Tệp DQQL_Bai1.inp lưu số tự nhiên N, Tệp DQQL_Bai1.out lưu các hoán vị)2. Lập trình đọc một số n từ tệp, tìm và lưu tất cả các dãy nhị phân có độ dài nVí dụ: N=3  000,001,010,011,100,101,110,1113. Lập trình tìm tất cả chỉnh hợp không lặp chập K của N phần tử. n!/(n-k)!DQQL_Bai3.inpDQQL_Bai3.out2412134513 14 15 31 34 35 41 43 45 51 53 544. Lập trình tìm tất cả chỉnh hợp lặp chập K của N phần tử: n^kDQQL_Bai4.inpDQQL_Bai4.out239Giáo viên: Lê Thanh Phú5|Tra n gTài liệu bồi dưỡng học sinh giỏi THPT – Môn Tin học124Phần II: Chuyên đề nâng cao11 12 14 21 22 24 41 42 44Bài 5. Bài toán tám quân hậu:Xét bàn cờ kích thước 8x8. Hỏi có bao nhiêu cách đặt 8 quân hậu lên bàn cờ này sao cho chúngkhông thể ăn lẫn nhau.Bài 6: Đảo chữ cáiBạn phải viết chương trình đưa ra tất cả các từ có thể có phát sinh từ một tập các chữ cái.Ví dụ: Cho từ “abc”, chương trình của bạn phải đưa ra được các từ "abc", "acb", "bac", "bca", "cab" và"cba" (bằng cách khảo sát tất cả các trường hợp khác nhau của tổ hợp ba chữ cái đã cho).InputDữ liệu vào được cho trong tệp input.txt chứa một số từ. Dòng đầu tiên là một số tự nhiên cho biết số từđược cho ở dưới. Mỗi dòng tiếp theo chứa một từ. Trong đó, một từ có thể chứa cả chữ cái thường hoặchoa từ A đến Z. Các chữ thường và hoa được coi như là khác nhau. Một chữ cái nào đó có thể xuất hiệnnhiều hơn một lần.OutputVới mỗi từ đã cho trong file Input, kết quả nhận được ra file Output phải chứa tất cả các từ khác nhauđược sinh từ các chữ cái của từ đó. Các từ được sinh ra từ một từ đã cho phải được đưa ra theo thứ tựtăng dần của bảng chữ cái.DQQL_Bai6.inpDQQL_Bai6.out2abc acb bac bca cab cbaacbaac aca caaaacBài 7: Trò chơi LineTrò chơi Line là trò chơi di chuyển các viên bi trong một hình vuông 9 x 9 ô. Bi được ăn khi tạothành các hàng, cột, đường chéo gồm 5 viên bi liên tiếp cùng màu.Một thuật toán được sử dụng trong trò chơi là tìm đường đi để di chuyển một viên bi. Giả sử tròchơi Line tổng quát có n dòng, n cột. Đánh số các dòng từ 1 đến n theo thứ tự từ trên xuống dưới, đánhsố các cột từ 1 đến n theo thứ tự từ trái sang phải. Giả sử có một viên bi tại ô (y, x) - dòng y cột x, bi cóthể di chuyển đến 1 trong 4 ô (y+1, x), (y-1, x), (y, x+1), (y, x-1), nếu ô đó đang trống. Cho vị trí bắt đầu vàvị trí kết thúc của viên bi, hãy viết chương trình xác định xem có tồn tại đường đi để di chuyển viên bihay không.Dữ liệu nhập: gồm các dòng sau- Dòng thứ nhất gồm năm số n, sy, sx, dy, dx, mỗi số cách nhau một khoảng trắng (2 ≤ n ≤ 9; 1 ≤ sy, sx, dy,dx ≤ n). sy là chỉ số dòng, sx là chỉ số cột của viên bi cần di chuyển. dy là chỉ số dòng, dx là chỉ số cột củavị trí cần di chuyển viên bi đến.- Trong n dòng tiếp theo, mỗi dòng gồm n số nguyên 0 hoặc 1, mỗi số cách nhau một khoảng trắng, biểuthị tình trạng của trò chơi. Số 1 nghĩa là vị trí ô đó có bi, số 0 nghĩa là vị trí ô đó đang trống.(Dữ liệu cho bảo đảm tại ô (sy, sx) có giá trị là 1, tại ô (dy, dx) có giá trị là 0)Dữ liệu xuất:- Nếu tìm được đường đi, in ra YES.- Nếu không tìm được đường đi, in ra NO.Bai7.inpBai7.outBai7.inpBai7.out21122YES21122NO10111010Bài 8: ốc sên ăn rauGiáo viên: Lê Thanh Phú6|Tra n gTài liệu bồi dưỡng học sinh giỏi THPT – Môn Tin họcPhần II: Chuyên đề nâng caoCó một khu vườn hình chữ nhật kích thước n x m ô vuông (n dòng, m cột). Ta đánhsố các dòng từ 1 đến n theo chiều từ trên xuống dưới, các cột từ 1 đến m theochiều từ trái qua phải. Tại những ô vuông là đất bình thường người ta trồng rau. Tuynhiên có một số ô là đá nên không trồng rau được. Có một chú ốc sên tại ô (y, x), ylà vị trí dòng, x là vị trí cột. Từ một ô, chú ốc sên chỉ có thể di chuyển sang 4 ô liền kề(y-1, x), (y+1, x), (y, x-1), (y, x+1). Nếu gặp ô đá thì ốc sên không đi vào được.Ốc sên đang rất đói. Bạn hãy xác định xem chú có thể ăn được số lượng rau nhiều nhất là bao nhiêu.Dữ liệu vào: gồm các dòng sau:- Dòng thứ nhất gồm bốn số nguyên n, m, y, x, mỗi số các nhau một khoảng trắng (1 ≤ y ≤ n ≤ 100,1 ≤ x ≤m ≤ 100).- Trong n dòng tiếp theo, mỗi dòng gồm m số nguyên 0 hoặc 1 biểu thị vườn rau, mỗi số cách nhau mộtkhoảng trắng. Số 0 nghĩa là ô rau, còn số 1 nghĩa là ô đá.(Dữ liệu cho đảm bảo ô (y, x) là ô rau)Dữ liệu xuất:- Là một số nguyên xác định số lượng ô lớn nhất mà ốc sên có thể di chuyển đến.Ví dụ:Ocsen.inpOcsen.outOcsen.inpOcsen.out45241011111001000010011000001001Bài 9: (5 điểm) Tắt đènTên file chương trình: TFLI.PASTrong một thành phố có N đường phố xếp hàng ngang và N đườngphốxếp hàng dọc tạo thành hình bàn cờ như hình vẽ bên (ví dụ với N = 5).Tại mỗi giao lộ có một cột đèn đường. Trên mỗi đường phố có mộtcôngtắc có thể bật hoặc tắt tất cả các cột đèn thuộc đường phố đó. Như vậy mỗicộtđèn có thể được bật/tắt bởi hai công tắc, một thuộc đườngngang và một thuộc đường dọc. Hiện tại có một số cột đèn đang sáng.Em hãy viết chương trình tìm cách tắt tất cả các cột đèn trên sao cho số lần tắt công tắc là ítnhất.Dữ liệu vào: Cho ở file văn bản TFLI.INP có cấu trúc như sau:- Dòng 1: ghi duy nhất số nguyên dương N (2 ≤ N ≤ 10);- N dòng tiếp theo, mỗi dòng ghi N số 0 hoặc 1, số 0 biểu thị cột đèn đang tắt, số 1 biểu thị cột đèn đangsáng. Các số ghi cách nhau một dấu cách.Kết quả: ghi ra file văn bản TFLI.OUT ghi duy nhất số lần tắt công tắc tìm được.Ví dụ :TFLI.INP50101011010211110101001010TFLI.OUT3Giải thíchTắt các công tắc ởdòng 3, cột 2 và cột4.Bài 10: Điền số vào ma trậnGiáo viên: Lê Thanh Phú7|Tra n gTài liệu bồi dưỡng học sinh giỏi THPT – Môn Tin họcPhần II: Chuyên đề nâng caoHãy lập thuật toán điền các phần tử của ma trận NxN (2 ≤ N ≤ 200) các số -1, 0, 1 sao cho tổng các sốcủa mọi hình vuông con 2x2 đều bằng 0 và tổng các số của ma trận trên là lớn nhất. Ma trận có cácphần tử bằng 0 là ma trận cơ sở và không được gọi là một cấu hình. Dữ liệu vào: tập tin MATRAN.INPchứa số N là cấp của ma trận Kết quả: xuất ra tập tin MATRAN.OUT gồm:••Ma trận tìm được cấp NHàng tiếp theo là tổng các số của ma trận tìm được Ví dụ:MATRAN.INP5112122MATRAN.OUT0 1 0 1-1 0 -1 00 1 0 1-1 0 -1 00 1 0 151 00 -10Bài 11: Quân tượng đi lạc:Có một quân tượng trong cờ tướng đi lạc vào một bàn cờ vua. Bàn cờ vua có kích thước là 8 x 8,các dòng được đánh số từ 1 đến 8 theo thứ tự từ trên xuống dưới, các cột được đánh số từ 1 đến 8 theothứ tự từ trái qua phải. Quân tượng đi lạc đang nằm ở ô (y, x), dòng y cột x. Để có thể quay trở lại bàn cờtướng, quân tượng phải tìm cách di chuyển đến một cổng thoát tại ô (ty, tx) trên bàn cờ vua. Bạn hãytính xem quân tượng phải di chuyển ít nhất bao nhiêu nước đi để đến được cổng thoát này.Ghi chú: Quân tượng cờ tướng di chuyển theo đường chéo 2 ô một, từ ô (y, x) có thể đi đến mộttrong bốn ô (y-2, x-2), (y-2, x+2), (y+2, x-2), (y+2, x+2).Dữ liệu nhập:- Là bốn số nguyên y, x, ty, tx mỗi số cách nhau một khoảng trắng (1 ≤ y, x, ty, tx ≤ 8)Dữ liệu xuất:- Nếu quân tượng không thể di chuyển đến cổng thoát, mãi mãi ở lại bàn cờ vua, in ra -1.- Nếu quân tượng có thể di chuyển đến cổng thoát, in ra số bước di chuyển ít nhất.Quto.inpQuto.outQuto.inpQuto.out1112-135752Giáo viên: Lê Thanh Phú8|Tra n g