Sáng kiến kinh nghiệm Phương pháp quy hoạch động và ứng dụng vào giải một số bài toán bồi dưỡng học sinh giỏi, thi chuyên bằng ngôn ngữ lập trình Pascal và C++

 MỤC LỤC 
Phần I. Đặt vấn đề: ................................................................................................. 5 
1. Lí do chọn đề tài ................................................................................................. 5 
2. Mục đích nghiên cứu, đóng góp mới của đề tài ............................................... 5 
3. Đối tượng nghiên cứu .......................................................................................... 6 
4. Phương pháp nghiên cứu ................................................................................... 6 
5. Phạm vi nghiên cứu ............................................................................................ 6 
6. Cấu trúc của đề tài .............................................................................................. 6 
 1. Cơ sở lý luận ................................................................................................... 6 
 2. Cơ sở thực tiễn ................................................................................................ 6 
Phần II. Nội dung: ................................................................................................... 7 
1. Cơ sở lý luận......................................................................................................... 7 
 1. 1. Giới thiệu .................................................................................................... 7 
 1. 2. Phương pháp quy hoạch động .................................................................... 7 
 1.2.1. Khái niệm ............................................................................................. 7 
 1.2.2. Đặc điểm chung của phương pháp quy hoạch động ............................. 9 
 1.2.3. Các bước giải bài toán bằng quy hoạch động ....................................... 9 
 1. 3. Cách tiếp cận quy hoạch động .................................................................... 9 
 1. 4. Lớp các bài toán được giải bằng quy hoạch động ..................................... 9 
 1. 5. Ưu điểm và hạn chế của quy hoạch động ................................................. 10 
 1.5.1. Ưu điểm ............................................................................................... 10 
 1.5.2. Hạn chế................................................................................................ 10 
2. Cơ sở thực tiễn ................................................................................................... 10 
 2.1. Thực trạng của vấn đề trước khi áp dụng đề tài ........................................ 11 
 2.1.1. Đặc điểm tình hình .............................................................................. 11 
 2.1.2. Thực trạng trước khi nghiên cứu ........................................................ 11 
 2.1.3. Các giải pháp giải quyết vấn đề .......................................................... 12 
 2.2. Rèn luyện kỹ năng vận dụng phương pháp Quy hoạch động để giải một số 
 bài toán cơ bản đến nâng cao ........................................................................... 12 
 2.2.1. Bài toán 1. Tìm dãy con không giảm nhiều phần tử nhất ................... 12 
 2.2.2. Bài toán 2. Dãy con chung dài nhất ................................................... 15 
 2.2.3. Bài toán 3. dãy con có tổng bằng s ..................................................... 19 
 2.2.4. Bài toán 4. chia kẹo ............................................................................. 23 
 3 
 Phần I. Đặt vấn đề 
1. Lí do chọn đề tài 
 Tự học tập, nghiên cứu là một nhiệm vụ quan trọng của mỗi giáo viên để 
 nâng cao trình độ chuyên môn, phục vụ cho công tác giảng dạy và đặc biệt là 
 trong bồi dưỡng đội tuyển học sinh giỏi. 
 Trong những năm gần đây, trong các đề thi học sinh giỏi tỉnh, quốc gia cũng 
 như các bài tập trên các trang giải bài trực tuyến vn.spoj.com, vnoi.info,  có 
 nhiều bài tập nếu chúng ta sử dụng những kiến thức cơ bản như đệ quy, duyệt, 
 chia để trị,  có thể giải quyết được nhưng gặp nhiều khó khăn về mặt tốc độ 
 cũng như giới hạn dữ liệu. Trong khi đó nếu chúng ta sử dụng phương pháp quy 
 hoạch động hoặc các phương pháp trên có kết hợp với quy hoạch động thì cho 
 một hiệu quả cao. 
 Quy hoạch động là một phương pháp rất hiệu quả để giải lớp bài toán trong 
 Tin học. Đặc biệt là những bài toán tối ưu, khi sử dụng phương pháp quy hoạch 
 động chương trình chạy nhanh, cách viết chương trình rõ ràng. Nhưng không 
 phải bài toán nào cũng có thể áp dụng được bằng phương pháp quy hoạch động. 
 Vậy thường những bài toán như thế nào thì áp dụng được phương pháp quy 
 hoạch động và cách giải một bài toán quy hoạch động như thế nào là một vấn đề? 
 Mặt khác hiện nay khi bồi dưỡng thi học sinh giỏi giáo viên có thể lựa chọn 
 1 trong 3 ngôn ngữ lập trình là Pascal, C++ hoặc là Python. Pascal là ngôn ngữ 
 lập trình đã cũ, câu lệnh dài và không được hỗ trợ nhiều. Python là ngôn ngữ lập 
 trình mới nhất, câu lệnh ngắn gọn, hỗ trợ nhiều trong khi viết chương trình. Tuy 
 nhiên một số bài toán khi chạy chương trình còn hạn chế về mặt thời gian. Chính 
 vì vậy hiện nay thi học sinh giỏi thì ngôn ngữ lập trình C++ được lựa chọn nhiều 
 nhất. Cho nên trong đề tài này tôi sử dụng ngôn ngữ lập trình C++ để viết chương 
 trình cũng như minh hoạ thuật toán. Ngoài ra tôi còn minh hoạ chương trình bằng 
 ngôn ngữ lập trình Pascal (Link code minh hoạ bằng ngôn ngữ lập trình pascal 
 để ở phần phụ lục của đề tài) cho một số bạn đọc dễ hiểu và nắm bắt tốt hơn khi 
 chưa tiếp cận nhiều với ngôn ngữ lập trình C++. 
 Vì những lý do trên, với những kinh nghiệm và tìm hiểu của bản thân, tôi 
 đưa ra đề tài “phương pháp quy hoạch động và ứng dụng vào giải một số bài 
 toán bồi dưỡng học sinh giỏi, thi chuyên bằng ngôn ngữ lập trình Pascal và 
 C++” . 
2. Mục đích nghiên cứu, đóng góp mới của đề tài 
 - Đề tài nêu ra các định hướng giúp học sinh có thể tiếp cận phương pháp Quy 
hoạch động để giải một số bài toán tối ưu phù hợp với dữ liệu bài toán. 
 - Giúp người đọc tiếp cận ngôn ngữ lập trình C++ tốt hơn trong khi lập trình. 
 - 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 
 5 
 Phần II. Nội dung: 
1. Cơ sở lý luận 
 Giới thiệu về phương pháp Quy hoạch động, các bước tiếp cận với phương 
pháp Quy hoạch động, cách nhận diện xem bài toán tối ưu nào có thể giải bằng 
phương pháp quy hoạch động và nếu giải thì cách giải như thế nào? Trình bày các 
dạng, phân tích và cài đặt chương trình cụ thể để bạn đọc dễ hiểu nhất. Qua đó có 
thể vận dụng để giải quyết các bài toán về sau. 
1. 1. Giới thiệu 
 Phương pháp quy hoạch động do nhà toán học người Mỹ Richard Bellman 
(1920 – 1984) phát minh năm 1953. 
 Phương pháp quy hoạch động (dynamic programming) là một kỹ thuật được 
áp dụng để giải nhiều lớp bài toán, đặc biệt là bài toán tối ưu. 
 Vậy bài toán tối ưu là gì?. Đó chính là bài toán có nhiều nghiệm chấp nhận 
được mỗi nghiệm có một giá trị đánh giá. Mục tiêu đặt ra là tìm nghiệm tối ưu, đó 
là nghiệm có giá trị đánh giá nhỏ nhất hoặc lớn nhất (tối ưu). 
 Khi tiến hành giải một bài toán phức tạp (bài toán lớn) ban đầu người ta 
thường đi chia bài toán đó thành các bài toán con độc lập đơn giản để giải, khi tiến 
hành giải xong các bài toán con ta tổng hợp lời của các bài toán con và đó chính là 
bài toán lớn cần giải. Đây chính là phương pháp chia để trị được sử dụng rất thông 
dụng trong quá trình lập trình giải các bài toán trong Tin học. Nhưng đối với những 
bài toán phức tạp nếu chúng ta sử dụng phương pháp này thì sẽ mất test ở những 
dữ liệu lớn. Vì chưa tối ưu về mặt thời gian. Chính vì vậy phương pháp Quy hoạch 
động ra đời nhằm cải tiến về vấn đề này. 
1. 2. Phương pháp quy hoạch động 
1.2.1. Khái niệm 
 Phương pháp quy hoạch động 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 toàn bộ hay một phần kết quả tính toán 
của mỗi bước trước đó với mục đích sử dụng lại (Công thức truy hồi là công thức 
thể hiện quan hệ giữa các bước trong một bài toán và kết quả của các bước sau 
thường dựa vào kết quả của các bước trước đó. Kết quả của bước cuối cùng chính 
là kết quả bài toán cần tìm). 
 Vậy bản chất của quy hoạch động =Chia để trị+Mảng (Lưu lại kết quả) 
 Phương pháp quy hoạch động sử dụng nguyên lý bottom - up, nghĩa là “ đi từ 
dưới lên”. Đầu tiên ta phải giải các bài toán con đơn giản nhất, có thể tìm ngay ra 
nghiệm. Sau đó kết hợp các bài toán con này lại để tìm lời giải cho bài toán lớn 
hơn và cứ như thế cho đến khi giải được bài toán yêu cầu. với phương pháp này 
mỗi bài toán con sau khi giải xong đều được lưu trữ lại và đem ra sử dụng nếu cần. 
Khi đó sẽ tiết kiệm được bộ nhớ và thời gian thực hiện. 
 7 
 Như vậy để tính được f(5) máy tính phải thực hiện mất 1 lần f(4), 2 lần f(3), 3 
lần f(2), 2 lần f(1). Nhưng cách 2 thì không như vậy nó tính f(1), f(2) từ đó tính 
f(3), và tính được f(4), f(5). Khi đó mỗi giá trị chỉ phải tính một lần và cần lấy f[i] 
nào thì lấy ra. 
1.2.2. Đặc điểm chung của phương pháp quy hoạch động 
 - Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất (bài toán cơ 
sở) để từ đó từng bước giải quyết bài toán lớn hơn cho tới khi giải được bài toán 
lớn nhất là bài toán ban đầu. 
 - Quy hoạch động cần có bảng phương án: chính là không gian lưu trữ lời giải 
các bài toán con để tìm cách phối hợp chúng, đây là bảng phương án của quy 
hoạch động. Thường kết quả cuối cùng của bảng phương án chính là kết quả của 
bài toán cần tìm. 
1.2.3. Các bước giải bài toán bằng quy hoạch động 
 Bước 1: Giải tất các bài toán cơ sở (thường là dễ nhất). lưu các lời giải vào 
bảng phương án. Đây là điều kiện dừng của bài toán 
 Bước 2: Xây dựng công thức truy hồi : bằng cách phối hợp những lời giải của 
bài toán nhỏ hơn đã lưu trong bảng phương án để tìm lời giải của bài toán lớn hơn 
(công thức truy hồi) và lưu vào bảng phương án, nhờ có công thức truy hồi này ta 
tính được bảng phương án. 
 Bước 3: Dựa vào bảng phương án, ta truy vết tìm nghiệm tối ưu. Đây chính là 
kết quả của bài toán. 
1. 3. Cách tiếp cận quy hoạch động 
 Quy hoạch động thường dùng một trong 2 cách tiếp cận sau : 
 - Tiếp cận từ dưới lên (Bottom up) 
 Là phương pháp đi từ cái riêng đến cái chung, từ các thành phần ở mức cao 
tới các đối tượng thành phần ở mức thấp, từ mức đơn vị chương trình tới mức tổng 
thể. 
 - Tiếp cận từ trên xuống ( Top down) 
 Là phương pháp phân rã vấn đề có hệ thống từ trên xuống. 
 Cách tiếp cận từ dưới lên hiệu quả hơn từ trên xuống nên cách tiếp cận từ dưới 
lên được sử dụng nhiều hơn. 
1. 4. Lớp các bài toán được giải bằng quy hoạch động 
 Nhưng không phải bài toán tối ưu nào cũng giải được bằng phương pháp quy 
hoạch động. Thường những bài toán có đặc điểm sau: 
 - Khi bài toán có tính chất truy hồi. 
 9 
2.1. Thực trạng của vấn đề trước khi áp dụng đề tài 
2.1.1. Đặc điểm tình hình 
* Thuận lợi: 
 - Với sự bùng nổ của ngành công nghệ thông tin cũng như chương trình 
 giáo dục phổ thông 2018 các em học sinh, phụ huynh ngày càng quan tâm hơn. 
 - Ngày nay số lượng học sinh có máy tính cá nhân ngày càng nhiều, các em 
 có điều kiện để học tập, nghiên cứu và lập trình được nhiều hơn. 
 - Các cuộc thi lập trình này ngày càng tổ chức nhiều hơn, việc học, xem tài 
 lệu cũng dễ dàng hơn, có thể xem các tài liệu trên web cũng như các kênh như 
 youtube. 
* Khó khăn: 
 - Do môn Tin học chưa có trong tổ hợp môn thi tốt nghiệp và đại học nên 
 các em và phụ huynh chưa quan tâm đến nên việc chọn học sinh giỏi cũng như 
 các em chưa thực sự đầu tư chuyên sâu vào lập trình. 
 - Những kiến thức trong chương trình Tin học phổ thông còn hạn chế, hoặc 
 chưa đủ đáp ứng cho việc giải một số bài toán trong các kỳ thi học sinh giỏi 
 Tỉnh khi có yêu cầu dữ liệu lớn cùng thời gian thực hiện ngắn. 
 - Các tài liệu tổng hợp các cách để giải quyết các bài toán yêu cầu cao như 
 vậy chưa có nhiều để học sinh tham khảo, ôn luyện. 
2.1.2. Thực trạng trước khi nghiên cứu 
 Ngày nay công nghệ thông tin là một trong những ngành hót, nhân lực còn 
thiếu, mỗi năm sinh viên ra trường chưa đáp ứng đủ yêu cầu thị trường, mức thu 
nhập nghành công nghệ thông tin là khá cao, nên việc quan tâm của các em ngày 
càng nhiều, nhất là trong các cuộc thi lập trình. 
 Năm học này thì trường đại học và khoa học công nghệ Hà Nội đã có 9 ngành 
cho học sinh đăng kí thi tổ hợp môn: Toán , Lý, Tin 
 Với sự phát triển nhanh về tốc độ cũng như sự quan tâm đến của nghành công 
nghệ thông tin ngày càng cao thì đề thi học sinh giỏi Tin học cũng đòi hỏi ngày càng 
nâng cao hơn. Trong các đề thi học giỏi thì người ta quan tâm về thời gian thực 
hiện và độ lớn của dữ liệu đầu vào. Đa số giáo viên gặp khó khăn trong việc hướng 
dẫn học sinh giải bài toán thế nào để đạt được trọn vẹn yêu cầu của bài toán. 
 Đối với những bài toán phức tạp và có dữ liệu lớn thì giáo viên và học sinh 
còn gặp khó khăn, chưa giải quyết vấn đề một cách triệt để. Dẫn đến sẽ mất test. 
Chương trình chưa tối ưu chỉ ăn test với dữ liệu nhỏ. 
 11 
 * Kết quả: ghi ra file văn bản DAYCON.OUT gồm 2 dòng: 
 - Số max là độ dài dãy con không giảm dài nhất tìm được 
 - Chỉ số xuất hiện của các số hạng của dãy con trong dãy đã cho. 
 * Ví dụ: 
 DAYCON.INP DAYCON.OUT 
 10 5 
 6 5 8 12 6 9 7 13 2 13 6 8 12 13 13 
 *Cách giải: 
 Gọi l[i] là độ dài dãy con không giảm dài nhất, các phần tử lấy trong miền từ 
an đến ai và phần tử bắt đầu là a[i] (i=n, n-1,..., 0). 
 Bài toán sử dụng thêm 2 phần tử: a[0]= -32768 và a[n+1]=32767 chắc chắn 
thuộc dãy con không giảm dài nhất. Khi đó độ dài dãy con không giảm dài nhất bắt 
đầu từ a[n+1] là 1, dãy bắt đầu từ a[i], ..., a[n+1]; 
 Bước 1: Giải các bài toán cơ sở và lưu vào bảng phương án 
 L[n+1]=1; với a[n+1]=32767 nên chắc chắn thuộc dãy con không giảm dài 
nhất. 
 Bước 2: Tìm công thức truy hồi 
 Khi xét tới phần tử a[i] thì a[i] phải nối vào đầu 1 dãy con không giảm mà bắt 
đầu phần tử a[j] nào đó phải thõa mãn a[i]<=a[j] (j=i+1,...,n+1). 
 Nhưng trong đó các a[j]>=a[i] thì ta phải chọn jmax để dãy con không giảm 
bắt đầu từ a[jmax] dài nhất. Nên công thức truy hồi của bài toán là: 
 L[i]=max{l[j] | j=i+1,..., n+1 thõa mãn a[i]<=a[j]} +1 
 Bước 3: Dựa vào bảng phương án, ta truy vết tìm nghiệm tối ưu. 
 * Tính bảng phương án: dựa vào giá trị l[n+1]=1 để tính tiếp l[i] (i= n, n-
1,...,0). Dùng t[i] để lưu lại các vị trí jmax. 
 Xét ví dụ: N=10; a=(6 5 8 12 6 9 7 13 2 13) ta có bảng phương án 
 I 0 1 2 3 4 5 6 7 8 9 10 11 
 A -32768 6 5 8 12 6 9 7 13 2 13 32767 
 L 7 6 6 5 4 5 4 4 3 3 2 1 
 T 1 3 3 6 8 6 8 8 10 9 10 11 
 13 
 l[n+1]=1; 
 t[n+1]=n+1; 
 for (int i=n;i>=0;i--) 
 { jmax=n+1; 
 for (int j=i+1;j<=n+1;j++) 
 if ((a[i]l[jmax])) jmax=j; 
 l[i]=l[jmax]+1; 
 t[i]=jmax; 
 } } 
 void Truyvet() 
 { fo <<l[0]-2; 
 fo <<"\n"; 
 int i=0; 
 while (t[i]!=n+1) 
 { fo <<a[t[i]]<<" "; 
 i=t[i]; 
 } 
 } main() 
 { 
 nhap(); qhd(); truyvet(); 
 } 
2.2.2. Bài toán 2. Dãy con chung dài nhất 
 Cho dãy số nguyên a=(a1, a2,,aM ), b=(b1, b2,,bN ), với M, N <=100. 
 Hãy tìm một dãy con chung c=(c1, c2,,cK ) của a và b gồm nhiều số hạng 
nhất. Dãy c nhận được bằng cách xóa đi một số hạng của dãy a, c cũng nhận được 
bằng cách xóa đi một số số hạng của dãy b, sau khi xóa ở hai dãy giữ nguyên thứ 
tự các phần tử còn lại 
 * Dữ liệu vào: từ file văn bản DAYCC.INP gồm 3 dòng: 
 - Dòng 1 ghi hai số nguyên M, N. 
 - Dòng 2 ghi các số a1, a2,,aM 
 - Dòng 3 ghi các sô b1, b2,,bN 
 15