SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN
Đơn vị: Trƣờng THPT Phan Đăng Lƣu
SÁNG KIẾN KINH NGHIỆM
Đề tài:
SỬ DỤNG PHƢƠNG PHÁP QUY HOẠCH ĐỘNG ĐỂ
GIẢI MỘT SỐ BÀI TOÁN CÓ TÍNH TRUY HỒI TRONG
NGÔN NGỮ LẬP TRÌNH C++
Môn/Lĩnh vực: Tin học
Ngƣời thực hiện: Nguyễn Thị Thƣơng
Hồ Văn Chiến
Tổ: Toán - Tin
Điện thoại: 0976607114 - 0979783682
Có đính kèm:
Mô hình Phần mềm Phim ảnh Hiện vật khác
Năm học: 2021 - 2022
MỤC LỤC
Phần I. ĐẶT VẤN ĐỀ ............................................................................................... 1
1. Lý do chọn đề tài .................................................................................................. 1
2. Mục tiêu, nhiệm vụ của đề tài ............................................................................... 1
3. Đối tƣợng nghiên cứu ........................................................................................... 1
4. Phƣơng pháp nghiên cứu ..................................................................................... 2
Phần II. NỘI DUNG NGHIÊN CỨU ...................................................................... 2
1.Cơ sở lý luận .......................................................................................................... 2
2. Thực trạng vấn đề nghiên cứu .............................................................................. 2
3. Nội dung vấn đề nghiên cứu ................................................................................. 3
3.1. Tên chủ đề ...................................................................................................... 3
3.2. Cơ sở lý thuyết ................................................................................................ 3
3.2.1. Khái niệm về phƣơng pháp quy hoạch động ............................................. 3
3.2.2. Các bƣớc giải bài toán quy hoạch động .................................................... 3
3.2.3. Biện pháp lựa chọn và cài đặt chƣơng trình. ............................................. 4
3.3. Các bài tập áp dụng ......................................................................................... 7
3.3.1. Dạng bài toán về dãy con liên tiếp ........................................................... 7
3.3.2. Dạng bài toán về dãy con không liên tiếp ................................................. 10
3.3.3. Dạng bài toán Dãy con có tổng bằng S. .................................................... 18
3.3.4. Dạng bài toán Biến đổi xâu ....................................................................... 22
3.3.5. Dạng bài toán Ghép cặp ............................................................................ 30
Phần III. KẾT LUẬN VÀ KIẾN NGHỊ .................................................................. 36
3.1. Kết luận ........................................................................................................... 36
3.2. Kiến nghị ......................................................................................................... 36
TÀI LIỆU THAM KHẢO ........................................................................................ 37
1
Phần I. ĐẶT VẤN ĐỀ:
1. Lý do chọn đề tài:
Chúng ta thấy Tin Học đƣợc ứng dụng vào hầu hết tất cả các lĩnh vực của cuộc
sống và đã đóng vai trò rất lớn trong sự phát triển của xã hội.
Thấy đƣợc tầm quan trọng của Tin học, thế giới nói chung và Việt Nam nói
riêng đã có những đầu tƣ lớn cho lĩnh vực này. Đặc biệt trong giáo dục nâng cao
dân trí về Tin Học và đào tạo nguồn nhân lực có chất lƣợng cao.
Phụ huynh và các thế hệ học sinh sau này cũng đã bắt đầu chú trọng và đã chọn
các nghành nghề liên quan đến công nghệ thông tin nhiều hơn.
Tuy nhiên trong hệ thống giáo dục nƣớc ta hiện nay môn Tin học chƣa đƣợc
quan tâm đúng với tầm quan trọng của nó. Tin Học đang bị xem là môn phụ trong
trƣờng học dẫn đến học sinh ít đầu tƣ cho môn học này, gây ra không ít khó khăn
cho giáo viên trong nhà trƣờng và đặc biệt chọn đội ngũ học sinh giỏi. Mặt khác
môn Tin học có đặc thù riêng, học sinh giỏi đi thi chủ yếu chấm bài tự động trên
phần mềm themis nên phụ thuộc lớn vào thời gian thực hiện (thời gian chạy)
chƣơng trình và giới hạn độ lớn dữ liệu mà bài toán yêu cầu. Vì vậy lập trình ngoài
việc chú ý đến giới hạn dữ liệu bài toán thì cần lựa chọn thuật toán tối ƣu để đảm
bảo yêu cầu bài toán đặt ra. Vì vậy để giải bài toán trong Tin Học thƣờng phải xác
định đƣợc:
- Bài toán thuộc lớp nào.
- Sử dụng phƣơng pháp tối ƣu nào để giải nó.
Trong quá trình nghiên cứu và bồi dƣỡng học sinh giỏi chúng tôi gặp khá nhiều
bài toán về dãy con và bài toán xử lí xâu. Đây là một nội dung khá phổ biến trong
các đề thi học sinh giỏi và là một nội dung khá khó. Với mong muốn tìm ra các
giải pháp tối ƣu cho các bài toán này, chúng tôi mạnh dạn trình bày sáng kiến kinh
nghiệm: SỬ DỤNG PHƢƠNG PHÁP QUY HOẠCH ĐỘNG ĐỂ GIẢI MỘT
SỐ BÀI TOÁN CÓ TÍNH TRUY HỒI TRONG NGÔN NGỮ LẬP TRÌNH
C++
2. Mục tiêu, nhiệm vụ của đề tài:
Nhằm giúp học sinh đứng trƣớc 1 bài toán, xác định đƣợc là bài toán đó có thể
áp dụng đƣợc quy hoạch động không và cách giải cụ thể nhƣ thế nào, đánh giá, so
sánh đƣợc thời gian thực hiện chƣơng trình (độ phức tạp của thuật toán). Cách
nhận diện và lập công thức quy hoạch động
3. Đối tƣợng nghiên cứu:
Sử dụng phƣơng pháp quy hoạch động để giải một số bài toán có tính truy hồi
trong C++ nhƣ: Tìm dãy con; đếm dãy con; Tính tổng dãy con; và các bài toán liên
quan đến xâu nhƣ tìm xâu con chung dài nhất và biến đổi xâu.
2
4. Phƣơng pháp nghiên cứu:
Để trình bày sáng kiến kinh nghiệm này chúng tôi sử dụng kết hợp nhiều
phƣơng pháp nhƣ: Nghiên cứu tài liệu, nghiên cứu theo chuyên đề, thực nghiệm,
so sánh, phân tích kết quả thực nghiệm, ý kiến đóng góp của đồng nghiệp trong
thực tiễn giảng dạy
Phần II. NỘI DUNG NGHIÊN CỨU:
1. Cơ sở lý luận:
Sự phát triển nhƣ vũ bão của Tin học và những đóng góp lớn của Tin học trong
sự phát triển xã hội không thể phủ nhận đƣợc, đặc biệt trong dịp dịch Covid 19 vai
trò của Tin học đã đƣợc khẳng định, mọi ngƣời dân nói chung và phụ huynh học
sinh nói riêng đã nhìn thấy đƣợc vai trò quan trọng của Tin học trong mọi lĩnh vực
kinh tế, văn hóa và giáo dục. Chắc chắn mọi ngƣời đã có cái nhìn nhận khác và
thấy môn Tin Học rất quan trọng.
Xã hội phát triển, đòi hỏi Tin học cũng phát triển để đáp ứng nhu cầu của xã
hội. Để đáp ứng những đòi hỏi của sự phát triển đó phải có kế hoạch đào tạo bồi
dƣỡng những cá nhân có niềm say mê và có năng khiếu trong lĩnh vực tin học và
trang bị vốn kiến thức cơ sở vững chắc, giúp cho mục tiêu đi trƣớc đón đầu, rút
ngắn khoảng cách về trình độ tin học giữa nƣớc ta và thế giới.
Trong quá trình nghiên cứu, giảng dạy, chúng ta gặp rất nhiều các bài tập toán
tin. Các bài tập dạng này rất phong phú và đa dạng. Thực tế chƣa có thuật toán
hoàn chỉnh có thể áp dụng cho mọi bài toán. Tuy nhiên ngƣời ta đã tìm ra một số
thuật toán chung nhƣ: tham lam, quay lui, quy hoạch động, các giải thuật trên đồ
thị... Các thuật toán này có thể áp dụng để giải một lớp khá rộng các bài toán hay
gặp trong thực tế. Trong quá trình ôn thi học sinh giỏi của trƣờng, việc truyền đạt
các kiến thức về một số thuật toán nhƣ: quay lui, quy hoạch động, tham lam, các
giải thuật trên đồ thị… là rất cần thiết cho học sinh để phát triển tƣ duy và lập trình
giải các bài toán tin học. Tạo lập và củng cố lòng say mê tìm hiểu và khám phá cho
học sinh khi giải các bài toán tin.
Trong quá trình dạy bồi dƣỡng chúng tôi nhận thấy, nếu học sinh thực hiện tốt
việc lựa chọn và cài đặt chƣơng trình tối ƣu khi giải các bài tập về dãy con và các
bài tập xử lí xâu nói riêng và các bài tập lập trình nói chung thì chất lƣợng học sinh
giỏi sẽ đƣợc nâng cao.
2. Thực trạng vấn đề nghiên cứu:
Thực trạng dạy học môn Tin học trong trƣờng phổ thông Phan Đăng Lƣu hiện
nay:
Hiện nay nhu cầu xã hội đang cần rất nhiều kĩ sƣ Công Nghệ Thông tin và lao
động có trình độ cao. Tuy nhiên việc đào và bồi dƣơng học sinh yêu thích môn tin
học ở các trƣờng phổ thông gặp rất nhiều khó khăn.
3
- Môn Tin học vẫn đang bị xem là môn “phụ”, không tham gia thi tốt nghiệp
hay đại học cao đẳng vì thế môn Tin Học chƣa nhận đƣợc sự quan tâm của nhà
trƣờng cũng nhƣ phụ huynh và học sinh.
Mặt khác, để lập trình đòi hỏi học sinh phải có một kiến thức cơ bản tốt, phải có
khả năng về tƣ duy và đam mê.
Vì vậy động viên và tuyển chọn đƣợc các em vào đội tuyển học sinh giỏi môn
tin học ở trƣờng rất khó
Trong thực trạng đó chúng tôi muốn tìm hiểu, nghiên cứu, và truyền những
kinh nghiệm, hiểu biết của mình để truyền lại đam mê cho những học sinh ham
thích môn Tin học.
3. Nội dung vấn đề nghiên cứu:
3.1. Tên chủ đề:
SỬ DỤNG PHƢƠNG PHÁP QUY HOẠCH ĐỘNG ĐỂ GIẢI MỘT SỐ BÀI
TOÁN CÓ TÍNH TRUY HỒI TRONG NGÔN NGỮ LẬP TRÌNH C++
3.2. Cơ sở lý thuyết:
3.2.1. Khái niệm về phương pháp quy hoạch động:
Các thuật toán đệ quy có ƣu điểm dễ cài đặt, tuy nhiên do bản chất của quá trình
đệ quy, các chƣơng trình này thƣờng kéo theo những đòi hỏi lớn về không gian bộ
nhớ và một khối lƣợng tính toán khổng lồ, nên một thuật toán hiệu quả là cực kỳ
cần thiết. 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 đƣợc lựa chọn nhiều nhất.
Quy hoạch động (Dynamic programming) là một kỹ thuật nhằm đơn giản hóa
việc tính toán các công thức truy hồi bằng cách lưu trữ toàn bộ hay một phần kết
quả tính toán tại mỗi bước với mục đích sử dụng lại. Bản chất của quy hoạch động
là thay thế mô hình tính toán “từ trên xuống” (Top-down) bằng mô hình tính toán
“từ dưới lên” (Bottom-up).
Từ “programming” ở đây không liên quan gì tới việc lập trình cho máy tính, đó
là một thuật ngữ mà các nhà toán học hay dùng để chỉ ra các bƣớc chung trong
việc giải quyết một dạng bài toán hay một lớp các vấn đề. Không có một thuật toán
tổng quát để giải tất cả các bài toán quy hoạch động.
Mục đích của phần này là cung cấp một cách tiếp cận mới trong việc giải quyết
các bài toán tối ƣu mang bản chất đệ quy, đồng thời đƣa ra các ví dụ từ dễ đến khó
để học sinh có thể làm quen và hình thành các kỹ năng trong việc tiếp cận các bài
toán quy hoạch động.
3.2.2. Các bước giải bài toán quy hoạch động:
Có 4 bƣớc để giải 1 bài toán bằng quy hoạch động:
Bước 1: Xây dựng hàm mục tiêu: