Nội dung sáng kiến được trình bày logic, phù hợp với trình độ phát triển tư duy của học sinh từ nhận biết, thông hiểu đến vận dụng, nâng cao và sáng tạo qua đó giúp cho học sinh phát triển tư duy tổng hợp và rèn luyện các kĩ năng viết chương trình sử dụng phương pháp quy hoạch động.
Lời giới thiệu
Công nghệ thông tin hiện diện khắp nơi và phát triển nhanh chóng, mang lại nhiều lợi ích cho cuộc sống con người Nhờ khả năng tính toán và xử lý khối lượng công việc lớn, máy tính giúp các nhà khoa học thực hiện những nghiên cứu đột phá với hàng tỷ phép tính trong vài giây Sự ra đời của nhiều phần mềm đã giúp con người giải quyết công việc một cách dễ dàng hơn Các phần mềm này được phát triển bởi các lập trình viên thông qua các ngôn ngữ lập trình, trong đó Pascal là một ngôn ngữ lý tưởng cho những người mới bắt đầu học lập trình.
Tại các trường Trung học phổ thông, việc đào tạo toàn diện và bồi dưỡng năng lực học sinh là nhiệm vụ quan trọng Một tiêu chí đánh giá chất lượng giáo dục là kết quả bồi dưỡng học sinh giỏi, đặc biệt đối với giáo viên bộ môn Tin học Để bồi dưỡng học sinh giỏi, giáo viên cần nắm vững kiến thức lập trình và các phương pháp giảng dạy thuật toán hiệu quả Học sinh cần có kiến thức sâu về lập trình để đạt kết quả cao trong các kỳ thi học sinh giỏi Giáo viên phải cung cấp thêm kiến thức và phương pháp lập trình, sử dụng các thuật toán như đệ quy, quy hoạch động, chia để trị, và tham lam Quy hoạch động là phương pháp hiệu quả trong giải bài toán tối ưu hóa rời rạc, đặc biệt trong các kỳ thi học sinh giỏi, nơi từ 30% đến 40% bài thi yêu cầu sử dụng quy hoạch động Việc lựa chọn thuật toán hiệu quả rất quan trọng vì nó ảnh hưởng đến thời gian thực hiện và dung lượng bộ nhớ.
Trong lĩnh vực lập trình, các thuật toán thực hiện nhanh và chiếm ít bộ nhớ được đánh giá cao, trong đó quy hoạch động là một phương pháp hiệu quả Học sinh cần nắm vững quy hoạch động để có thể giải quyết các bài toán khó, nhưng thường gặp khó khăn trong việc phân biệt nó với các phương pháp khác Việc giúp học sinh nhận ra ưu điểm của quy hoạch động và sử dụng thành thạo phương pháp này không phải là điều dễ dàng Hiểu rõ các thuật toán sẽ giúp học sinh tự tin hơn trong việc phân tích bài toán và tìm ra phương pháp giải đúng, từ đó nâng cao thành tích học tập Là giáo viên dạy Tin học tại trường trung học phổ thông, tôi nhận thấy việc bồi dưỡng học sinh giỏi và ứng dụng quy hoạch động trong thiết kế thuật toán là rất cần thiết cho những em tham gia đội tuyển học sinh giỏi môn Tin học.
Tôi đã chọn nghiên cứu đề tài “Giúp học sinh tiếp cận với phương pháp quy hoạch động thông qua một số bài toán đơn giản trong Tin học” Hy vọng tài liệu này sẽ hữu ích cho giáo viên, học sinh và những ai quan tâm đến kiến thức này.
Tên sáng kiến
Giúp học sinh tiếp cận với phương pháp quy hoạch động bằng một số bài toán đơn giản trong Tin học.
Tác giả sáng kiến
- Họ và tên: Nguyễn Thị Hà
- Địa chỉ tác giả sáng kiến: Xã Đại Đồng – huyện Vĩnh Tường – tỉnh Vĩnh Phúc
- E_mail: nguyenthiha.gvnguyenvietxuan@vinhphuc.edu.vn
Lĩnh vực áp dụng sáng kiến
hoặc những người quan tâm tới lập trình.
Mô tả bản chất của sáng kiến
SƠ ĐỒ NỘI DUNG SÁNG KIẾN KINH NGHIỆM
NỘI DUNG SÁNG KIẾN KINH NGHIỆM
Một số khái niệm cơ bản về phương pháp quy hoạch động
* Quy hoạch động (Dynamic Programming) là một phương pháp rất hiệu quả giải nhiều bài toán tin học, đặc biệt là những bài toán tối ưu
Quy hoạch động trong ngành khoa học máy tính là một phương pháp hiệu quả giúp giảm thời gian chạy của các thuật toán Phương pháp này thể hiện rõ các tính chất của những bài toán con gối nhau, từ đó tối ưu hóa quá trình giải quyết vấn đề.
(Overlapping subproblem) và cấu trúc con tối ưu (Optimal substructure)
Phương pháp quy hoạch động là một kỹ thuật giải quyết vấn đề bắt đầu từ các bài toán nhỏ nhất (bài toán cơ sở) và dần dần tiến tới các bài toán lớn hơn cho đến khi đạt được giải pháp cho bài toán lớn nhất (bài toán ban đầu) Ý tưởng cốt lõi của quy hoạch động là tránh tính toán lại các bài toán con đã được giải, thể hiện sức mạnh của nguyên lý chia để trị ở mức độ cao.
* Một bài toán P muốn giải bằng phương pháp quy hoạch động cần có 2 đặc điểm sau:
Bài toán P tuân theo nguyên lý tối ưu Bellman, cho phép sử dụng các lời giải tối ưu của các bài toán con ở mức thấp để dần dần tìm ra lời giải tối ưu cho các bài toán con ở mức cao hơn, cuối cùng dẫn đến lời giải tối ưu cho bài toán P.
- Bài toán P có các bài toán con phủ chồng lên nhau, nghĩa là không gian bài toán con “hẹp” không tạo dạng hình cây
1.2 Các bước giải quyết bài toán bằng phương pháp quy hoạch động
Để xây dựng hàm mục tiêu F(i) cho bài toán con cấp i, ta áp dụng nguyên lý tối ưu của Bellman nhằm phân rã bài toán ban đầu thành các bài toán con có cấu trúc tương tự Việc giải quyết bài toán con cấp i sẽ phụ thuộc vào kết quả của các bài toán con trước đó, từ đó giúp tối ưu hóa quá trình giải quyết.
- Bước 2: Xác định các bài toán cơ sở
Bài toán cơ sở là những bài toán nhỏ nhất mà chúng ta có thể dễ dàng biết hoặc tính được kết quả Chúng đóng vai trò quan trọng trong việc tìm nghiệm cho các bài toán phức tạp hơn.
- Bước 3: Xây dựng công thức truy hồi
Dựa vào ý nghĩa của hàm mục tiêu, chúng ta xác định mối quan hệ giữa các bài toán con ở các cấp khác nhau Từ đó, chúng ta có thể xây dựng công thức tính toán kết quả của bài toán cấp i dựa trên kết quả của các bài toán con ở cấp trước.
- Bước 4: Lập bảng phương án
Sử dụng công thức truy hồi và nghiệm các bài toán cơ sở tính nghiệm tất cả các bài toán con và lưu trữ chúng vào bảng phương án
- Bước 5: Kết luận nghiệm của bài toán
Dựa vào bảng phương án chỉ ra nghiệm của bài toán Các bước giải quyết trên tuy rất cụ thể nhưng vẫn trừu tượng đối với học sinh
Bài toán 1: Tính a n (n là số nguyên dương)
- Bước 1: Hàm mục tiêu: f(i) là lũy thừa của a i
- Bước 2: Các bài toán cơ sở: f(0) = 1;
- Bước 3: Công thức truy hồi: f(i) = a* f(i-1)
- Bước 5: Nghiệm f(n) của bài toán
- Bước 1: Hàm mục tiêu: f(i) là giai thừa của số i
- Bước 2: Các bài toán cơ sở: f (0) = 1; f(1) = 1
- Bước 3: Công thức truy hồi: f(i) = i* f(i-1)
- Bước 5: Nghiệm F(n) của bài toán
Bài toán 3: Tìm số Fibonaci thứ N?
- Bước 1: Hàm mục tiêu: f(i) là số fibonaci thứ i
- Bước 2: Các bài toán cơ sở: f(0) = 1; f(1) = 1
- Bước 3: Công thức truy hồi: f (i) = f(i-1) + f(i-2)
- Bước 5: Nghiệm f(n) của bài toán
Bài toán 4: Tháp Hà Nội
Chuyển n chiếc đĩa từ cọc 1 sang cọc 2 theo thứ tự từ lớn đến nhỏ có sử dụng cọc
3 làm cọc trung gian Mỗi lần di chuyển được 1 đĩa Và đĩa đĩa lớn phải ở dưới đĩa nhỏ
- Bước 2: Các bài toán cơ sở: f(1): = 1
- Bước 3: Công thức truy hồi: f(i):=2*f(i-1)+1
- Bước 5: Nghiệm f(n) của bài toán
Bài toán 5: Bài toán cái túi
Trong siêu thị có n gói hàng (n
