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

Mục tiêu nghiên cứu của đề tà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.
Nội dung trích xuất từ tài liệu:
Sáng kiến kinh nghiệm THPT: Ứng dụng thuật toán đệ quy - khử đệ quy trong giảng dạy bồi dưỡng học sinh giỏi 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ỆMTê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 MỤC LỤCPHẦN I. ĐẶT VẤN ĐỀ.................................................................................. 31. LÝ DO CHỌN ĐỀ TÀI .............................................................................. 32. MỤC ĐÍCH NGHIÊN CỨU ...................................................................... 33. ĐỐI TƯỢNG NGHIÊN CỨU .................................................................... 44. ĐỐI TƯỢNG KHẢO SÁT, THỰC NGHIỆM .......................................... 45. PHƯƠNG PHÁP NGHIÊN CỨU .............................................................. 46. PHẠM VI VÀ THỜI GIAN NGHIÊN CỨU............................................. 4PHẦN II. NỘI DUNG .................................................................................... 51. THUẬT TOÁN ĐỆ QUY ........................................................................... 51.1. Khái niệm.............................................................................................. 51.2. Phân loại ................................................................................................ 61.3. Thuật toán đệ quy ................................................................................... 71.4. Chương trình con đệ quy ...................................................................... 10 1.4.1. Hàm đệ quy....................................................................................... 10 1.4.2. Thủ tục đệ quy .................................................................................. 111.5. Các bước xây dựng chương trình con đệ quy........................................ 111.6. Cơ chế thực hiện thuật toán đệ quy...................................................... 121.7. Một số bài toán về đệ quy..................................................................... 14 1.7.1. Bài toán tháp Hà Nội......................................................................... 14 1.7.2. Bài toán chia thưởng ......................................................................... 17 1.7.3. Bài toán sắp xếp mảng – Thuật toán sắp xếp nhanh .......................... 19 1.7.4. Bài toán tìm kiếm – Thuật toán tìm kiếm nhị phân............................ 232. KỸ THUẬT KHỬ ĐỆ QUY .................................................................... 26 2.1. Lý do sử dụng kỹ thuật khử đệ quy ..................................................... 26 2.2. Một số kỹ thuật khử đệ quy đơn giản .................................................. 27 2.3. Khử một số dạng đệ quy thường gặp .................................................... 27 2.4. Nhận xét chung về kỹ thuật khử đệ quy ................................................ 31PHẦN III. KẾT LUẬN VÀ KIẾN NGHỊ .................................................. 32 I. KẾT LUẬN .............................................................................................. 32 II. KIẾN NGHỊ ........................................................................................... 32TÀI LIỆU THAM KHẢO............................................................................ 33 2 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ệnnay đượ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ủangà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ỗimộ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ặcba năm học. Chỉ có quá trình này mới cung cấp được tương đối đầy đủ các kiếnthứ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ôngphả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àiliệ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 đadạng phong phú để các giáo viên cũng như các em học sinh có thể hiểu đượctoà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ôngâ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ểutườ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ểunghiên cứu, tham khảo tài liệu và xây dựng nên đề tài: “ỨNG DỤNG THUẬTTOÁN ĐỆ QUY - KHỬ ĐỆ QUY TRONG GIẢNG DẠY BỒI DƯỠNG HỌCSINH GIỎI” nhằm giúp cho giáo viên bồi dưỡng học sinh giỏi cũng như giúpcác em học sinh giỏi có kinh nghiệm trong việc áp dụng thuật toán đệ quy để lậptrì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áchgiả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: ...