Sáng kiến kinh nghiệm Ứng dụng thuật toán đệ quy - khử đệ quy trong giảng dạy bồi dưỡng học sinh giỏi

Nội dung text: Sáng kiến kinh nghiệm Ứng dụng thuật toán đệ quy - khử đệ quy trong giảng dạy bồi dưỡng học sinh giỏi

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO QUẢNG TRỊ TRƯỜNG THPT HƯỚNG HÓA SÁNG KIẾN KINH NGHIỆM Tên đề tài: ỨNG DỤNG THUẬT TOÁN ĐỆ QUY - KHỬ ĐỆ QUY TRONG GIẢNG DẠY BỒI DƯỠNG HỌC SINH GIỎI HỌ VÀ TÊN GIÁO VIÊN: NGUYỄN TIẾN LONG TỔ TIN HỌC TRƯỜNG THPT HƯỚNG HÓA Hướng Hóa, Tháng 7 năm 2020
2. MỤC LỤC PHẦN I. ĐẶT VẤN ĐỀ 4 1. LÝ DO CHỌN ĐỀ TÀI 4 2. MỤC ĐÍCH NGHIÊN CỨU 4 3. ĐỐI TƯỢNG NGHIÊN CỨU 5 4. ĐỐI TƯỢNG KHẢO SÁT, THỰC NGHIỆM 5 5. PHƯƠNG PHÁP NGHIÊN CỨU 5 6. PHẠM VI VÀ THỜI GIAN NGHIÊN CỨU 5 PHẦN II. NỘI DUNG 6 1. THUẬT TOÁN ĐỆ QUY 6 1.1. Khái niệm 6 1.2. Phân loại 7 1.3. Thuật toán đệ quy 8 1.4. Chương trình con đệ quy 11 1.4.1. Hàm đệ quy 11 1.4.2. Thủ tục đệ quy 11 1.5. Các bước xây dựng chương trình con đệ quy 12 1.6. Cơ chế thực hiện thuật toán đệ quy 13 1.7. Một số bài toán về đệ quy 15 1.7.1. Bài toán tháp Hà Nội 15 1.7.2. Bài toán chia thưởng 18 1.7.3. Bài toán sắp xếp mảng – Thuật toán sắp xếp nhanh 20 1.7.4. Bài toán tìm kiếm – Thuật toán tìm kiếm nhị phân 24 2. KỸ THUẬT KHỬ ĐỆ QUY 27 2.1. Lý do sử dụng kỹ thuật khử đệ quy 27 2.2. Một số kỹ thuật khử đệ quy đơn giản 28 2.3. Khử một số dạng đệ quy thường gặp 28 2.4. Nhận xét chung về kỹ thuật khử đệ quy 31 PHẦN III. KẾT LUẬN VÀ KIẾN NGHỊ 32 I. KẾT LUẬN 32 II. KIẾN NGHỊ 32 TÀI LIỆU THAM KHẢO 33 2
3. PHẦN I. ĐẶT VẤN ĐỀ 1. LÝ DO CHỌN ĐỀ TÀI Việc nâng cao chất lượng giáo dục mũi nhọn là một vấn đề cấp thiết hiện nay được nhà trường và toàn ngành giáo dục tỉnh nhà đặc biệt quan tâm, chú trọng. Bồi dưỡng học sinh giỏi là một nhiệm vụ quan trọng không thể thiếu của ngành giáo dục nói chung và của các trường nói riêng đặc biệt là đối với mỗi một giáo viên tham gia bồi dưỡng thì đây là một nhiệm vụ không dễ dàng. Bồi dưỡng học sinh giỏi là cả một quá trình, không thể ngày một ngày hai, mà phải có tính chiến lược dài trong suốt cả một quá trình, có thể một, hai hoặc ba năm học. Chỉ có quá trình này mới cung cấp được tương đối đầy đủ các kiến thức cần thiết cho học sinh và phát hiện chính xác khả năng học tập của các em, từ đó mới có thể thành lập các đội tuyển tham dự kỳ thi học sinh giỏi các cấp đạt kết quả như mong đợi. Các nội dung liên quan đến đệ quy, khử đệ quy, hay đệ quy quay lui không phải là nội dung quá mới trong việc giảng dạy, có thể dễ dàng tìm thấy các tài liệu tham khảo liên quan, nhưng chưa có tài liệu nào đầy đủ, chi tiết, bài tập đa dạng phong phú để các giáo viên cũng như các em học sinh có thể hiểu được toàn bộ kiến thức liên quan. Phần bài tập đệ quy- khử đệ quy là phần bài tập khó thường chiếm một phần điểm trong các đề thi học sinh giỏi, cũng là phần có số dạng bài và phương pháp giải phong phú. Mặt khác các bài tập về đệ quy luôn gây nhiều hứng thú và đôi khi sẽ gặp vấn đề khó giải quyết nếu như không hiểu tường tận về nó. Với những lý do trên và qua thực tiễn giảng dạy nhiều năm, tôi đã tìm hiểu nghiên cứu, tham khảo tài liệu và xây dựng nên đề tài: “ỨNG DỤNG THUẬT TOÁN ĐỆ QUY - KHỬ ĐỆ QUY TRONG GIẢNG DẠY BỒI DƯỠNG HỌC SINH GIỎI” nhằm giúp cho giáo viên bồi dưỡng học sinh giỏi cũng như giúp các em học sinh giỏi có kinh nghiệm trong việc áp dụng thuật toán đệ quy để lập trình cho các bài toán. 2. MỤC ĐÍCH NGHIÊN CỨU Nhằm giúp giáo viên và học sinh khi đứng trước một bài toán, xác định được là bài toán đó có thể áp dụng được thuật toán đệ quy hay không? Và cách giải cụ thể như thế nào? Từ đó tôi đề ra mục đích, nhiệm vụ của việc thực hiện đề tài như sau: 3
4. - Giới thiệu khái niệm “thuật toán đệ quy”, giới thiệu khái niệm đệ quy, chương trình con đệ quy, các bước xây dựng chương trình con đệ quy và cơ chế thực hiện thuật toán đệ quy và một số bài toán đệ quy điển hình. - Giới thiệu kỹ thuật khử đệ quy 3. ĐỐI TƯỢNG NGHIÊN CỨU Sáng kiến “Ứng dụng thuật toán đệ quy – khử đệ quy trong giảng dạy bồi dưỡng học sinh giỏi” có đối tượng nghiên cứu là các bài toán giải bằng thuật toán đệ quy. Nội dung đề tài sử dụng ngôn ngữ lập trình C++ để giải quyết các bài toán. 4. ĐỐI TƯỢNG KHẢO SÁT, THỰC NGHIỆM Đề tài lấy đối tượng khảo sát, thực nghiệm là học sinh giỏi môn Tin học trường THPT Hướng Hóa mà bản thân đã và đang trực tiếp giảng dạy. 5. PHƯƠNG PHÁP NGHIÊN CỨU Chủ yếu là nghiên cứu đề tài, tham khảo tài liệu, ý kiến đóng góp của đồng nghiệp và đặc biệt là đúc rút kinh nghiệm qua thực tiễn giảng dạy. 6. PHẠM VI VÀ THỜI GIAN NGHIÊN CỨU Trong khuôn khổ của một đề tài sáng kiến tôi chỉ khái quát nội dung lý thuyết và giải một số bài tập ứng dụng thuật giải đệ quy – khử đệ quy. Đề tài được nghiên cứu trong quá trình học tập và giảng dạy, bồi dưỡng các đội tuyển học sinh giỏi, giới hạn thời gian nghiên cứu trong 2 năm học: năm học 2018 - 2019 và 2019 - 2020. 4
5. PHẦN II. NỘI DUNG 1. THUẬT TOÁN ĐỆ QUY 1.1. Khái niệm Đệ quy là một khái niệm cơ bản trong toán học và khoa học máy tính. Một đối tượng được gọi là đệ quy nếu nó hoặc một phần của nó được định nghĩa thông qua khái niệm về chính nó. Ví dụ 1: Định nghĩa số tự nhiên bằng đệ quy như sau: - 0 là số tự nhiên. - Nếu k là số tự nhiên thì k+1 cũng là số tự nhiên. Theo đó, ta sẽ có 1 = 0 +1 là số tự nhiên, 2 = 1+1 cũng là số tự nhiên, Cứ như vậy ta sẽ định nghĩa được các số tự nhiên khác lớn hơn. Do đó, số tự nhiên là một khái niệm mang bản chất đệ quy. Ví dụ 2: Định nghĩa xâu kí tự bằng đệ quy như sau: - Xâu rỗng là một xâu kí tự. - Một kí tự bất kỳ ghép với một xâu kí tự sẽ tạo thành một xâu mới. Thuật toán đệ quy đóng vai trò quan trọng trong việc giải quyết nhiều bài toán. Một thuật toán đệ quy là thuật toán có yêu cầu thực hiện lại chính thuật toán đó với mức độ dữ liệu nhỏ hơn. Trong lĩnh vực lập trình, một chương trình máy tính được gọi là đệ quy nếu trong chương trình đó có lời gọi chính nó. Nhưng một chương trình không thể gọi mãi chính nó, vì như vậy sẽ tạo ra một vòng lặp vô hạn. Do đó, một chương trình đệ quy trước khi gọi lại chính nó bao giờ cũng có một thao tác kiểm tra điều kiện dừng. Nếu điều kiện dừng thỏa mãn thì quá trình gọi đệ quy sẽ chấm dứt. Nhìn chung, các chương trình đệ quy đều có những đặc điểm sau: - Chương trình này có thể gọi lại chính nó, mục đích là giải quyết vấn đề tương tự nhưng trong phạm vi nhỏ hơn. - Vấn đề nhỏ hơn này cho tới một lúc nào đó sẽ đơn giản tới mức chương trình có thể tự giải quyết được mà không cần gọi tới chính nó nữa, khi đó chương trình đệ quy kết thúc. Mô tả thuật toán đệ quy gồm 2 phần: - Phần neo (phần cơ sở/phần dừng): mô tả trường hợp suy biến (cá biệt) của đối tượng qua một thao tác cụ thể xác định. - Phần quy nạp (phần đệ quy): mô tả đối tượng thông qua chính đối tượng đó một cách trực tiếp hoặc gián tiếp. Ví dụ 3: Xét bài toán tính n! (Với n là một số nguyên bất kỳ). 5
6. Ta có: n! = n(n-1)! Do đó ta có thể mô tả bài toán dưới dạng đệ quy như sau: 1 khi n 0 n! n(n -1)! khi n 0 Với bài toán này ta xác định : - Phần neo : khi n = 0 thì n! = 1. - Phần quy nạp : Khi n>0 thì n ! = n(n-1) ! Ví dụ 4: Định nghĩa các số Fibonacci như sau : 1 khin 0 n 1 Fn Fn-1 Fn-2 khin 1 Hãy tính Fn với n cho trước. Với bài toán này ta xác định : - Phần neo: khi n = 0 hoặc n = 1 thì Fn = 1. - Phần quy nạp: khi n>1 thì Fn = Fn-1 +Fn-2 Ưu điểm của phương pháp mô tả đệ quy: có thể thực hiện một số lượng lớn các thao tác tính toán thông qua một thuật toán ngắn gọn, đơn giản (Mô tả một bài toán lớn chỉ qua một số ít thao tác). Hạn chế: Tốn bộ nhớ (nếu quản lý không tốt có thể gây tràn bộ nhớ) và thời gian thực hiện. Ví dụ 5 : Thuật toán đệ quy sử dụng ngay định nghĩa đệ quy của các số Fibonacci ở ví dụ 4 như sau: int F(int n) { if (n<2) return 1; else return F(n-1) + F(n-2); } Qua đó, ta thấy thuật toán đệ quy trên rất ngắn gọn, đơn giản, dễ hiểu và nêu bật lên bản chất của vấn đề nhưng do việc gọi đệ quy ở bài toán trên tạo ra những tính toán thừa nhiều lần, không cần thiết gây lãng phí bộ nhớ và thời gian thực hiện. 1.2. Phân loại Các chương trình đệ quy thường chia thành 2 loại: - Đệ quy trực tiếp: là loại đệ quy mà đối tượng được mô tả trực tiếp qua nó: A mô tả qua A, B, C, trong đó B, C, không chứa A. 6
7. - Đệ quy gián tiếp: là loại đệ quy mà đối tượng được mô tả gián tiếp qua nó: A được mô tả qua A1, A2, , An, trong đó có một Ai được mô tả qua A. Ví dụ 1: Chương trình tính ước số chung lớn nhất của hai số nguyên dựa vào thuật toán Euclide sau là chương trình con đệ quy thuộc dạng đệ quy trực tiếp: int UCLN(int m, int n) { if (n==0) return m; else return UCLN (n, m % n); } Ví dụ 2: Mô tả đệ quy hai dãy số {Xn} và {Yn} sau thuộc dạng đệ quy gián tiếp: X0 = 1; Xn = Xn-1 + Yn-1; 2 Y0 = 1; Yn = n Xn-1 + Yn-1; 1.3. Thuật toán đệ quy Thuật toán đệ quy là thuật toán có chứa thao tác gọi lại chính nó. Thuật toán đệ quy cho phép mô tả một dãy lớn các thao tác bằng một số ít các thao tác trong đó có chứa thao tác gọi lại thuật toán. Tức là nếu ta có lời giải S cho bài toán P, ta lại sử dụng lời giải đó cho bài toán P’ giống P nhưng kích thước nhỏ hơn thì lời giải S đó được gọi là lời giải đệ quy (thuật toán đệ quy). Thực thi thuật toán đệ quy có thể dẫn tới một tiến trình gọi đệ quy không kết thúc khi đó không có khả năng gặp trường hợp neo (điều kiện dừng), vì vậy ta cần quan tâm đến điều kiện dừng. Để kiểm soát quá trình gọi đệ quy của thuật toán đệ quy P người ta thường gắn thao tác gọi P với việc kiểm tra một điều kiện B xác định và biến đổi qua mỗi lần gọi P và quá trình gọi P sẽ dừng khi B không còn thỏa. Mô hình tổng quát của một thuật toán đệ quy được biểu diễn như sau: P  if (B) P[S, P] hoặc P  P[S, if (B) P] Thông thường với thuật toán đệ quy P, để đảm bảo P sẽ dừng sau n lần gọi ta chọn B là (n>0). Khi đó, mô hình tổng quát của một thuật toán đệ quy có dạng như sau: P(n)  if (n>0) P[S, P(n-1)] hoặc P(n)  P[S, if (n>0) P(n-1)] 7
8. Một số dạng thuật toán đệ quy đơn giản thường gặp: - Đệ quy tuyến tính: + Một hàm được gọi là đệ quy tuyến tính nếu bên trong thân hàm có duy nhất một lời gọi hàm lại chính nó một cách trực tiếp (tường minh). + Là dạng đệ quy trực tiếp và đơn giản nhất có dạng sau: P {if(điều kiện dừng) thực hiện S; else { thực hiên S*; gọi P; } } Với S, S* là các thao tác không đệ quy. Ví dụ: Tính tổng các chữ số của số nguyên dương n. Ta phân tích bài toán này dưới dạng đệ quy như sau: Gọi Tong(n) là tổng các chữ số của số nguyên dương n. Ta có: Tong(n) { if(n=0) Tong = 0; else Tong=Tong(n / 10) +(n % 10); } Trong đó: P là Tong(n), S là lệnh gán Tong = 0, S* là lệnh rỗng. Viết hàm bằng ngôn ngữ C++: int TCS(int n) { if (n==0) return 0; else return (n % 10)+ TCS(n / 10); } - Đệ quy nhị phân : + Một hàm được gọi là đệ quy nhị phân nếu bên trong thân hàm có hai lời gọi hàm lại chính nó một cách trực tiếp có dạng sau: P {if(điều kiện dừng) thực hiện S; else 8