1
MỤC LỤC
CÁC KÝ HIỆU VIẾT TẮT TRONG SÁNG KIẾN KINH NGHIỆM .......................... 3
I. Lời giới thiệu ............................................................................................................... 4
II. Tên sáng kiến: ............................................................................................................ 5
III. Tác giả sáng kiến: ..................................................................................................... 5
IV. Chủ đầu tư tạo ra sáng kiến:..................................................................................... 5
V. Lĩnh vực áp dụng sáng kiến: ..................................................................................... 5
VI. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử: ....................................... 5
VII. Mô tả bản chất của sáng kiến: ................................................................................ 5
PHẦN I: SƠ ĐỒ NỘI DUNG SÁNG KIẾN KINH NGHIỆM ................................ 6
PHẦN II: NỘI DUNG SÁNG KIẾN KINH NGHIỆM ............................................. 7
I. Một số khái niệm cơ bản về phương pháp quy hoạch động ............................... 7
1.1. Khái niệm .................................................................................................... 7
1.2. Các bước giải quyết bài toán bằng phương pháp quy hoạch động. ............ 7
II. So sánh phương pháp quy hoạch động với các phương pháp khác ................ 11
2.1. Phương pháp quy hoạch động và phương pháp đệ quy ............................ 11
2.2. Phương pháp quy hoạch động và phương pháp vét cạn ........................... 15
III. Cài đặt chương trình cho một số bài toán đơn giản thường gặp .................... 15
Ví dụ 1: Bài toán tính an (n là số nguyên dương). ........................................... 16
Ví dụ 2: Tính n! (n là số nguyên dương) ......................................................... 18
Ví dụ 3: Dãy số fibonacci: ............................................................................... 20
Ví dụ 4: Bài toán tháp Hà Nội .......................................................................... 22
Ví dụ 5: Bài toán cái túi ................................................................................... 24
IV. Bài tập tự giải ................................................................................................. 29
Bài toán 1: Dãy con có tổng bằng S ................................................................ 29
Bài toán 2: Dãy con có tổng lớn nhất ............................................................... 29
Bài toán 3: Chia kẹo ......................................................................................... 30
VIII. Những thông tin cần bảo mật: Không ................................................................. 30
2
IX. Các điều kiện cần thiết để áp dụng sáng kiến: Học sinh đội tuyển Tin học lớp 10,
11, 12. ........................................................................................................................... 30
X. Đánh giá lợi ích thu được hoặc dự kiến có thể thu được do áp dụng sáng kiến theo ý
kiến của tác giả: ............................................................................................................ 30
XI. Danh sách những tổ chức/cá nhân đã tham gia áp dụng thử hoặc áp dụng sáng kiến
lần đầu: ......................................................................................................................... 32
TÀI LIỆU THAM KHẢO ............................................................................................ 33
3
CÁC KÝ HIỆU VIẾT TẮT TRONG SÁNG KIẾN KINH NGHIỆM
Ký hiệu
Ý nghĩa
SKKN
Sáng kiến kinh nghiệm
THPT
Trung học phổ thông
ĐQ
Đệ quy
DQ
Đệ quy
QHĐ
Quy hoạch động
QHD
Quy hoạch động
PP
Phương pháp
NXB
Nhà xuất bản
4
BÁO CÁO KẾT QUẢ
NGHIÊN CỨU, ỨNG DỤNG SÁNG KIẾN
I. Lời giới thiệu
Hiện nay, công nghệ thông tin xuất hiện ở mọi nơi, sự phát triển nhanh chóng
của nó giúp cuộc sống của con người trở nên tốt đẹp hơn. Công nghệ thông tin giúp các
nhà khoa học tạo ra những nghiên cứu vượt bậc nhờ việc tính toán và xử lý một khối
lượng công việc khổng lồ của máy tính. Chúng có thể thực hiện hàng tỷ phép tính trong
vài giây. Rất nhiều phần mềm ra đời nhằm giúp con người giải quyết công việc dễ dàng
hơn. Các phần mềm được viết nhờ các Lập trình viên dựa trên các ngôn ngữ lập trình
và Pascal là một ngôn ngữ lập trình giúp những người mới học lập trình dễ tiếp cận.
Tại các trường Trung học phổ thông hiện nay, nhiệm vụ quan trọng là đào tạo
một cách toàn diện đồng thời chú trọng bồi dưỡng năng lực của học sinh. Chính vì vậy
một trong những tiêu chí đánh giá chất lượng giáo dục của trường THPT là kết quả của
việc thực hiện hoạt động bồi dưỡng học sinh giỏi. Đối với mỗi giáo viên THPT, bồi
dưỡng học sinh giỏi là một nhiệm vụ quan trọng và khó khăn. Nó đòi hỏi giáo viên phải
tìm hiểu, học tập rất nhiều kiến thức về chuyên ngành và các phương pháp giảng dạy
thích hợp. Đối với giáo viên bộ môn Tin học, bồi dưỡng học sinh giỏi đòi hỏi giáo viên
phải hiểu biết về lập trình và cần có các phương pháp giảng dạy thuật toán tốt giúp học
sinh dễ dàng tiếp thu và vận dụng. Học sinh muốn đạt kết quả cao trong kỳ thi học sinh
giỏi tỉnh và cao hơn cần phải có lượng kiến thức lớn và sâu trong việc lập trình. Những
kiến thức này đối với chương trình phổ thông bình thường là không đủ đáp ứng. Nhiệm
vụ của giáo viên là cung cấp thêm cho các em kiến thức, phương pháp lập trình để học
sinh đạt kết quả tốt trong kỳ thi. Có nhiều phương pháp được dùng để thiết kế thuật
toán như: Đệ quy (Recursion), quy hoạch động (Dynamic programming), chia để trị
(Divide and conquer), vét cạn (Exhaustivesearch), tham lam (Greedy algorithms) ...
Trong đó, mỗi thuật toán chỉ áp dụng cho những lớp bài toán phù hợp. Trong ngành
khoa học máy tính, đệ quy là chìa khóa để thiết kế nhiều giải thuật quan trọng và cũng
là cơ sở của quy hoạch động (Dynamic Programming). Quy hoạch động là một phương
pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con
gối nhau (Overlapping subproblem) và cấu trúc con tối ưu (Optimal substructure).
Phương pháp quy hoạch động là một phương pháp hiệu quả trong việc giải bài toán tối
ưu hoá rời rạc. Có một số bài toán sử dụng phương pháp quy hoạch động lại cho hiệu
quả cao hơn so với các phương pháp khác. Trong các kỳ thi học sinh giỏi tỉnh và cao
hơn hiện nay, từ 30% đến 40% các bài thi cần đến quy hoạch động và đây là những bài
toán khó, đòi hỏi học sinh phải có tư duy lập trình cao. Có thể có những cách khác để
giải bài toán đó. Nhưng vì các bài thi đều có xét đến thời gian thực hiện (chạy) chương
trình, cũng như dung lượng bộ nhớ để lưu trữ và thực hiện chương trình đó. Nên một
thuật toán hiệu quả là cực kỳ cần thiết. Có nghĩa là cùng một bài toán, cách nào mà thời
5
gian thực hiện càng nhanh, chiếm ít bộ nhớ hơn sẽ được đánh giá cao hơn. Và trong
những trường hợp như vậy, quy hoạch động là một trong những thuật toán phù hợp.
Chỉ cần làm được những bài này là học sinh gần như có giải. Tuy nhiên, các em thường
hay bị nhầm lẫn và khó phân biệt được khi thuật toán sử dụng phương pháp quy hoạch
động và các phương pháp khác. Nên việc làm cho các em học sinh phổ thông có thể
phân biệt và thấy được sự ưu việt của quy hoạch động từ đó sử dụng thành thạo phương
pháp này trong lập trình không phải là vấn đề dễ dàng. Hiểu rõ các thuật toán là bước
đầu giúp các em học sinh tự tin đồng thời phân tích bài toán và xác định phương pháp
giải đúng đắn sẽ giúp các em có thành tích tốt hơn. Là một giáo viên giảng dạy bộ môn
Tin học ở trường trung học phổ thông, sau nhiều năm tham gia dạy bồi dưỡng đội tuyển
thi học sinh giỏi, tôi nhận thấy việc bồi dưỡng học sinh giỏi là nhiệm vụ vô cùng quan
trọng và việc ứng dụng phương pháp quy hoạch động trong thiết kế thuật toán là một
mảng kiến thức rất cần thiết đối với học sinh tham gia đội tuyển học sinh giỏi môn Tin
học.
Vì vậy tôi chọn đề tài “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” làm đề tài nghiên cứu. Hy vọng đây sẽ
là một tư liệu hữu ích cho các giáo viên, học sinh và những người quan tâm đến phần
kiến thức này.
II. 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.
III. 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
- Số điện thoại: 0977 212 636
- E_mail: nguyenthiha.gvnguyenvietxuan@vinhphuc.edu.vn
IV. Chủ đầu tư tạo ra sáng kiến: Nguyễn Thị Hà
V. Lĩnh vực áp dụng sáng kiến: Dạy bồi dưỡng học sinh đội tuyển Tin học, giáo viên
hoặc những người quan tâm tới lập trình.
VI. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử: Năm 2017 – 2018.
VII. Mô tả bản chất của sáng kiến: