Sáng kiến kinh nghiệm THPT: Sử dụng phương pháp chia để trị để giải một số bài toán

Mục tiêu chính của đề tài là nghiên cứu về phương pháp “Chia để trị” để giải một số bài toán. Giúp cho việc ôn thi học sinh giỏi đạt kết quả cao. Tạo ra nguồn tài liệu tham khảo về phương pháp cũng như thuật toán nhằm hỗ trợ cho học sinh, giáo viên dạy bồi dưỡng học sinh giỏi tin học.
Nội dung trích xuất từ tài liệu:
Sáng kiến kinh nghiệm THPT: Sử dụng phương pháp chia để trị để giải một số bài toán SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN TRƯỜNG THPT THÁI HÒA SÁNG KIẾN KINH NGHIỆMSỬ DỤNG PHƯƠNG PHÁP CHIA ĐỂ TRỊ ĐỂ GIẢI MỘT SỐ BÀI TOÁN Lĩnh vực : Tin học Tên tác giả : Châu Đức Vinh Tổ : Toán Tin Điện thoại : 0942 910 226 Năm học: 2020- 2021 1 A. PHẦN MỞ ĐẦU I. Lí do chọn đề tài Hiện nay tài liệu dạng chuyên đề nâng cao phục vụ cho việc bồi dưỡng họcsinh giỏi môn Tin học là chưa thật sự đầy đủ và tổng quát, đặc biệt là nhữngchuyên đề khá mới và rất khó, giờ đã được đưa vào các đề thi học sinh giỏi tỉnhnhư: Chia để trị, Quy hoạch động, … Từ thực tiễn giảng dạy tin tại trường THPT tôi thấy rằng để đạt hiệu quả caotrong bồi dưỡng học sinh giỏi, cần có cách thiết kế bài giảng cho phù hợp với nộidung kiến thức dựa trên tài liệu chuyên đề đầy đủ rõ ràng từ lý thuyết đến bàitập và theo đúng xu thế chung của các kì thi học sinh giỏi các cấp hiện nay vàtrong tương lai, để mang lại thành tích cao cho đội tuyển học sinh giỏi trong các kìthi. Xuất phát từ cơ sở trên, tôi đã chọn đề tài “Sử dụng phương pháp chia đểtrị để giải một số bài toán”, sáng kiến này sẽ giúp học sinh của trường THPT TháiHòa vận dụng các kiến thức vào làm tốt các dạng đề thi học sinh giỏi tỉnh có liênquan đến phương pháp chia để trị, phục vụ cho việc bồi dưỡng học sinh giỏi củatrường. II. Mục đích của đề tài - Mục tiêu chính của đề tài là nghiên cứu về phương pháp “Chia để trị” đểgiải một số bài toán. - Giúp cho việc ôn thi học sinh giỏi đạt kết quả cao - Tạo ra nguồn tài liệu tham khảo về phương pháp cũng như thuật toán nhằmhỗ trợ cho học sinh, giáo viên dạy bồi dưỡng học sinh giỏi tin học. III. Đối tượng và phạm vi nghiên cứu 1. Đối tượng nghiên cứu - Sử dụng phương pháp chia để trị và một số bài toán - Học sinh giỏi tin khối 11, giáo viên giảng dạy học sinh giỏi tin 11 2. Phạm vi nghiên cứu Sử dụng phương pháp chia để trị để giải một số bài toán bồi dưỡng học sinhgiỏi tin học 11. IV. Phương pháp nghiên cứu - Thu thập, phân tích các tài liệu và thông tin liên quan đến phương phápchia để trị. - Lựa chọn một số bài toán để sử dụng phương pháp chia để trị. 2 - Thiết kế các bài toán đã được lựa chọn trong chương trình tin học 11 để bồidưỡng học sinh giỏi. - Dùng ngôn ngữ lập trình Free Pascal để cài đặt bài toán và chạy thửnghiệm trên một số bộ test để đánh giá kết quả. B. NỘI DUNG SÁNG KIẾN KINH NGHIỆM I. Cơ sở lý luận: - Cách tiếp cận về tri thức mới, hiện đại của học sinh trong trường THPT ởmột số trường thuộc trung du miền núi nói chung trong đó có THPT Thái Hòa nóiriêng là rất khó khăn vì: Thứ nhất là thiếu tài liệu chuyên sâu về bồi dưỡng họcsinh giỏi, thứ hai các em hầu như chưa quan tâm lắm đến lập trình bởi lẽ nó khó. - Vì vậy tôi đã tham khảo tài liệu để viết đề tài về phương pháp chia để trị từlý thuyết đến thuật toán và có một số bài toán cho các em vận dụng để thực hànhtrên máy tính. Từ đó các em làm tốt các đề bài có dạng tương tự trong các kì thichọn học sinh giỏi tin học. II. Nội dung và giải pháp thực hiện 1. Khái niệm: Chia để trị là một tư tưởng rất phổ biến trong cuộc sống và được áp dụng rấthiệu quả trong Tin học. Tư tưởng cơ bản của phương pháp chia để trị là Người taphân bài toán thành các bài toán con, các bài toán con lại tiếp tục được phân thànhcác bài toán con nhỏ hơn, cứ tiếp tục như thế cho đến khi ta nhận được bài toáncon đã có thuật giải hoặc có thể dễ dàng đưa ra thuật giải. Sau đó kết hợp nghiệmcủa các bài toán con để nhận được nghiệm của bài toán con lớn hơn để cuối cùngnhận được nghiệm của bài toán cần giải. Thông thường các bài toán con được phânchia là cùng dạng với bài toán ban đầu chỉ có cỡ của chúng là nhỏ hơn. 2. Sơ đồ chung: Các bài toán có thể giải quyết bằng phương pháp chia để trị thông qua 3bước: Bước 1: Chia: Chia bài toán cần giải thành một loạt các bài toán con độc lập. Tại bước này thì bài toán ban đầu sẽ được chia thành các bài toán con chođến khi không thể chia nhỏ được nữa. Các bài toán con sẽ trở thành 1 bước nhỏtrong việc giải quyết bài toán lớn. Bước 2. Trị: Giải quyết bài toán con một cách đệ quy. Tại bước này ta sẽ phải tìm phương án để giải quyết cho bài toán con mộtcách cụ thể. Bước 3. Kết hợp lời giải lại để suy ra lời giải 3 Khi đã giải quyết xong cái bài toán nhỏ, lặp lại các bước giải quyết đó và kếthợp lại những lời giải đó để suy ra kết quả cần tìm (có thể dạng đệ quy). 3. Thuật toán β: Giả sử chúng ta có thuật toán α để giải bài toán kích thước dữ liệu vào n vớithời gian bị chặn bởi cn2 (c: hằng số). Xét thuật giải β để giải bài toán bằng cách: - Bước 1: Chia bài toán cần giải thành 3 bài toán con với kích thước n/2. - Bước 2: Giải 3 bài toán bằng thuật toán α. - Bước 3: Tổng hợp lời giải của 3 bài toán con để thu được lời giải của bàitoán. Tính đúng đắn của thuật toán: Giả sử bước 3 đòi hỏi thời gian dn (d: hằng sô). Gọi: T α(n)= thời gian của thuật toán α. T β(n)= thời gian của thuật toán β Ta có: T α(n)= cn2 (theo giả thuyết) T β(n)= 3. T α(n/2) + dn = ¾.cn2 + dn. Nếu: dn < c.n2/4 hay n > 4.d/c thì thuật toán β nhanh hơn thuật toán α. Do 4.d/c làhằng số nên với n đủ lớn ta luôn có n > 4.d/c. Điều đó cho thấy việc sử d ...