Sáng kiến kinh nghiệm THPT: Giúp học sinh rèn luyện và nâng cao kĩ năng lập trình qua việc lựa chọn thuật toán tối ưu phù hợp với dữ liệu bài toán

Mục tiêu nghiên cứu của sáng kiến kinh nghiệm là nêu ra các định hướng giúp học sinh có thể lựa chọn thuật toán tối ưu phù hợp với dữ liệu bài toán trong một số dạng bài toán quen thuộc trên ngôn ngữ lập trình C++. Từ đó bồi dưỡng học sinh năng lực giải quyết vấn đề trong giải toán Tin học, đồng thời rèn luyện và nâng cao kĩ năng lập trình cho các em. Đặc biệt là học sinh tham gia dự thi học sinh giỏi cấp tỉnh THCS, THPT hoặc thi vào các trường chuyên.
Nội dung trích xuất từ tài liệu:
Sáng kiến kinh nghiệm THPT: Giúp học sinh rèn luyện và nâng cao kĩ năng lập trình qua việc lựa chọn thuật toán tối ưu phù hợp với dữ liệu bài toán Së GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN TRƯỜNG THPT NGUYỄN DUY TRINH ---***--- SÁNG KIẾN KINH NGHIỆM“GIÚP HỌC SINH RÈN LUYỆN VÀ NÂNG CAO KỸ NĂNG LẬP TRÌNH QUA VIỆC LỰA CHỌN THUẬT TOÁN TỐI ƯU PHÙ HỢP VỚI DỮ LIỆU BÀI TOÁN” MÔN: TIN HỌC GIÁO VIÊN: NGUYỄN THỊ TÚ ANH TỔ: TOÁN TIN NĂM HỌC: 2020 – 2021 ĐT: 0942797783 NGHI LỘC, THÁNG 3/2021 1 MỤC LỤCI. ĐẶT VẤN ĐỀ ................................................................................................................. 31. Lý do chọn đề tài ............................................................................................................. 32. Mục đích nghiên cứu của SKKN..................................................................................... 33. Nhiệm vụ nghiên cứu của SKKN .................................................................................... 44. Đối tượng nghiên cứu của SKKN ................................................................................... 46. Phương pháp thực hiện .................................................................................................... 47. Đóng góp của SKKN ....................................................................................................... 4II. NỘI DUNG .................................................................................................................... 51. Cơ sở lí luận của đề tài .................................................................................................... 52. Thực trạng của vấn đề trước khi áp dụng SKKN ............................................................ 5 2.1. Đặc điểm tình hình ................................................................................................... 5 2.2. Thực trạng trước khi nghiên cứu .............................................................................. 63. Các giải pháp giải quyết vấn đề ....................................................................................... 6 3.1. Cơ sở lý thuyết.......................................................................................................... 7 3.1.1. Độ phức tạp thuật toán ...................................................................................... 7 3.1.1.1. Tính hiệu quả của thuật toán ...................................................................... 7 3.1.1.2. Tại sao cần thuật toán có tính hiệu quả? .................................................... 7 3.1.1.3. Đánh giá thời gian thực hiện thuật toán ..................................................... 8 3.1.1.4. Các quy tắc đánh giá thời gian thực hiện thuật toán .................................. 9 3.1.1.5. Ước lượng độ phức tạp thuật toán tương ứng với độ lớn dữ liệu............. 10 3.1.2. Lựa chọn thuật toán ......................................................................................... 11 3.2. Lựa chọn thuật toán tối ưu phù hợp với dữ liệu bài toán ....................................... 11 3.2.1. Dạng 1: Các bài toán liên quan đến số học ..................................................... 12 3.2.2. Dạng 2: Sử dụng thuật toán sắp xếp ............................................................... 20 3.2.2.1. Bài toán sắp xếp........................................................................................ 20 3.2.2.2. Bài tập ví dụ.............................................................................................. 23 3.2.3. Dạng 3: Sử dụng thuật toán tìm kiếm............................................................. 32 3.2.3.1. Bài toán tìm kiếm ..................................................................................... 32 3.2.3.2. Bài tập ví dụ.............................................................................................. 34 3.2.4. Bài tập luyện tập .............................................................................................. 404. Tính mới của SKKN ...................................................................................................... 435. Hiệu quả của SKKN ...................................................................................................... 446. Những hướng phát triển của đề tài ................................................................................ 44III. KẾT LUẬN VÀ KIẾN NGHỊ .................................................................................. 451. Kết luận.......................................................................................................................... 452. Kiến nghị ....................................................................................................................... 45TÀI LIỆU THAM KHẢO............................................................................................... 46 2 I. ĐẶT VẤN ĐỀ1. Lý do chọn đề tài Khi giải các bài toán Tin học người lập trình luôn mong muốn viết chươngtrình với thuật toán tối ưu để có thể giải với dữ liệu lớn, thời gian thực hiện nhanh,bộ nhớ hạn chế…Tuy nhiên, bài toán Tin học thường đa dạng, phong phú nên để cóthể tìm được thuật toán tối ưu phù hợp dữ liệu bài toán là việc không hề dễ dàng.Đây là vấn đề nhiều giáo viên gặp khó khăn trong việc giảng dạy học sinh học lậptrình, cũng như công tác ôn thi học sinh giỏi để đạt kết quả cao. Ở trường phổ thô ...