Sáng kiến kinh nghiệm Đề xuất một số bài tập vận dụng phương pháp Quy hoạch động để nâng cao chất lượng bồi dưỡng học sinh giỏi Tin học cấp THPT

 2 
 THUYẾT MINH MÔ TẢ GIẢI PHÁP 
 VÀ KẾT QUẢ THỰC HIỆN SÁNG KIẾN 
1. Tên sáng kiến: Đề xuất một số bài tập vận dụng phương pháp Quy hoạch 
động để nâng cao chất lượng bồi dưỡng học sinh giỏi Tin học cấp trung học 
phổ thông. 
2. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử: Tháng 4/2020 
3. Các thông tin cần được bảo mật: không 
4. Mô tả các giải pháp cũ thường làm : 
 Trước đây, khi lập trình giải một bài toán, học sinh thường lựa chọn ngay 
cách giải dễ cài đặt (sử dụng phương pháp duyệt, đệ quy,) và tập trung vào việc 
đưa ra đáp số đúng mà chưa quan tâm đến việc đưa ra đáp số đúng trong thời gian 
ngắn nhất. Phương pháp duyệt, đệ quy, đảm bảo được việc tìm ra nghiệm đúng, 
chính xác nhưng nhược điểm thời gian thực thi lâu, độ phức tạp lớn. Do đó 
phương pháp này thường chỉ phù hợp với các bài toán có kích thước nhỏ. 
 Với yêu cầu ngày càng cao của những bài toán thi học sinh giỏi: đòi hỏi 
một thuật toán thỏa mãn được giới hạn dung lượng, giới hạn thời gian thực hiện 
thì phương pháp duyệt, đệ quy không đáp ứng được. 
5. Sự cần thiết phải áp dụng giải pháp sáng kiến: 
 Qua nhiều năm bồi dưỡng học sinh giỏi tin học cấp trung học phổ thông, 
tôi luôn tìm hiểu nhiều tài liệu, tìm các dạng bài tập để hướng dẫn cho học sinh. 
Tuy nhiên với những bài liên quan đến phương pháp quy hoạch động thường là 
học sinh bỏ qua (giải bài toán bằng cách khác) hoặc chỉ thuộc công thức của một 
bài và chỉ làm được một bài đó. Từ thực tế đó, tôi nhận thấy cần có các bài tập 
tương tự cùng một dạng để học sinh vừa làm quen với mỗi dạng bài toán quy 
hoạch động đó, vừa rèn kỹ năng giải toán bằng quy hoạch động. Sau thời gian 
tìm hiểu, áp dụng, tôi nhận thấy các bài tập tôi đề xuất (áp dụng phương pháp 
quy hoạch động ) đã giúp học sinh không còn lạ lẫm với phương pháp quy 
hoạch động, đồng thời làm quen, nhận diện được một số bài tập tương tự bài 
toán quy hoạch động điển hình, từ đó giải được trọn vẹn bài toán đó. 
 Cấu trúc đề thi học sinh giỏi một vài năm gần đây thể hiện rõ ràng sự 
phân hóa bằng việc: 
 - Bài thi được chấm bằng các test, có so sánh thời gian chạy chương trình 
 của các thí sinh để đánh giá. Các test của mỗi câu được chỉ rõ về số lượng, 
 giới hạn dữ liệu, số điểm tương ứng đạt được. 
 - Các bài toán trong đề có tỉ lệ % theo yêu cầu mức độ mục tiêu của đề. 
 Trong đó có một bài (chiếm tỉ lệ 10-15%) yêu cầu mức độ vận dụng cao, 
 4 
lại 3 dạng bài quy hoạch động cơ bản và phân tích, chỉ ra dấu hiệu nhận diện 3 
dạng bài, cụ thể: 
 Dạng 1: bài dãy con tăng nhiều phần tử nhất. Đặc điểm nhận diện: 
 - Dựa vào tính chất dãy con tăng: Phần tử đứng trước nhỏ hơn phần tử đứng sau 
 - Khi cập nhật L(i) chỉ phụ thuộc vào các phần tử L(j) (j=1..i-1) đứng trước 
nó. (Li phụ thuộc vào L1,L2,,Li-1) 
 Ví dụ: 
 * Bài toán: Cho dãy a có n phần tử a1,a2,an. Hãy tìm một dãy con tăng 
có nhiều phần tử nhất của dãy. 
 * Đặc điểm nhận diện và công thức quy hoạch động 
 Gọi L(i) là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ a1 
đến ai và phần tử cuối cùng là ai. Khi đó L(i) được cập nhập từ các L(j) với j 
nhận các giá trị từ 1 đến i-1. Vậy công thức quy hoạch động tính L(i) chỉ có thể 
xây dựng từ L(1), L(2),L(i-1), hay nói cách khác công thức tính L(i) chỉ phụ 
thuộc vào phần tử đứng trước. 
 Ta có công thức QHĐ để tính L(i) như sau: 
 L(1) = 1 
 L(i) = max(1, L(j)+1 với mọi phần tử j: 0 < j < i và aj ≤ ai). 
 Bảng phương án là một mảng một chiều L để lưu trữ các giá trị của hàm 
QHĐ L(i). Đoạn chương trình tính các giá trị của mảng L như sau: 
 for i := 1 to n do 
 begin 
 L[i] := 1; 
 for j:=1 to i - 1 do 
 if (a[j]<=a[i]) and (L[i]<L[j]) then L[i]:=L[j]+1; 
 end; 
 Dạng 2: bài cái túi (mỗi lần chọn 1 vật). Đặc điểm nhận diện: 
 Mỗi lần cập nhật L(i,t), tùy việc chọn đồ vật vào túi hay không chọn vào 
túi, chỉ phụ thuộc vào 2 phần tử ngay trước nó L(i-1,t) và L(i-1,t-ai) 
 Ví dụ: 
 * Bài toán: Có n đồ vật, vật thứ i có trọng lượng ai và giá trị bi. Hãy chọn 
ra một số các đồ vật, mỗi vật một cái để xếp vào 1 cái túi (vali/ ba lô) có trọng 
lượng tối đa M sao cho tổng giá trị của cái túi là lớn nhất. 
 * Đặc điểm nhận diện và công thức quy hoạch động: 
 Gọi L(i,t) là tổng giá trị lớn nhất khi được chọn i vật từ vật 1 đến vật i cho 
vào cái túi với tổng khối lượng không vượt quá t. L(n,M) sẽ là đáp số của bài 
toán (là giá trị lớn nhất có được nếu chọn n vật và tổng khối lượng không vượt M). 
 6 
tìm vị trí ô xuất phát và hành trình đi từ cột 1 đến cột n sao cho tổng các số ghi 
trên đường đi qua là lớn nhất (nhỏ nhất). 
 * Đặc điểm nhận diện và công thức quy hoạch động: 
 Tìm câu trả lời cho câu hỏi: Từ ô nào đến được ô (i,j)? 
 Bước 1: Vẽ hình (2 bảng kích cỡ mxn của đề bài: 1 bảng đường đi ban 
đầu A , 1 bảng sẽ là bảng phương án F) 
 Bước 2: Thiết lập tham chiếu sang các ô xung quanh: từ 1 ô ban đầu có 
thể sang những ô kề cạnh hay kề đỉnh nào (đề bài cho), 
 Bước 3: Lần ngược lại tìm công thức quy hoạch động: để tới được ô (i,j) 
thì đi qua những ô nào 
 Gọi F[i, j] là số điểm lớn nhất (nhỏ nhất) có thể có được khi tới ô A[i, j]. 
Rõ ràng đối với những ô ở cột 1 thì F[i, 1] = A[i, 1]. Với những ô (i, j) ở các cột 
khác: Vì chỉ những ô (i, j – 1), (i – 1, j – 1), (i + 1, j –1) là có thể sang được ô (i, 
j), và khi sang ô (i, j) thì số điểm được cộng thêm A[i, j] nữa. Chúng ta cần F[i, 
j] là số điểm lớn nhất (nhỏ nhất) có thể nên 
 F[i, j] = max(F[i, j - 1], F[i –1, j - 1], F[i + 1, j - 1]) + A[i, j] (Hoặc min). 
 Ta dùng công thức truy hồi này tính tất cả các F[i, j]. Cuối cùng chọn ra 
F[i, n] là phần tử lớn nhất trên cột n của bảng F và từ đó truy vết tìm ra đường đi 
nhiều điểm nhất 
 A F 
 (1,1) (1,1) 
 A(i-1,j+1) F(i-1,j-1) 
 A(i,j) A(i,j+1) F(i,j-1) F(i,j) 
 A(i+1,j+1) F(i+1,j-1) 
 (m,n) (m,n) 
Chi tiết tín hiệu nhận diện 3 dạng bài trên được trình bày ở phụ lục 1, dưới đây 
là bảng đặc điểm nhận dạng mỗi dạng bài trong 3 dạng mà giải pháp 1 đề cập đến: 
 Bảng 1. Tín hiệu nhận diện 3 dạng bài quy hoạch động cơ bản 
 Dạng bài Đặc điểm nhận dạng 
Dạng 1: Bài toán dãy con - Dựa vào tính chất dãy con tăng: Phần tử đứng 
tăng có nhiều phần tử nhất trước nhỏ hơn phần tử đứng sau. 
 - Khi cập nhật L(i) chỉ phụ thuộc vào các phần 
 tử L(j) (j=1..i-1) đứng trước nó. (Li phụ thuộc 
 vào L1, L2, , Li-1) 
Dạng 2: Bài toán cái túi (mỗi Mỗi lần cập nhật L(i,j), tùy việc chọn đồ vật vào 
 8 
đoạn chương trình chính. Dưới đây là một bài toán tương tự, chi tiết 6 bài còn lại 
ở phụ lục 1. 
 Bài 1. Dãy con không giảm dài nhất 
 Cho dãy số nguyên a= a1, a2, , an. (n<=5000, -10000<=ai<=10000). 
 Một dãy con không giảm của dãy đã cho là dãy các phần tử còn lại của dãy đó 
 sau khi ta xóa bỏ một hoặc một số phần tử bất kì của nó, các phần tử của dãy 
 con tạo thành dãy không giảm. 
 Ví dụ: dãy 1, 2, 10, 11, 12 là một dãy con không giảm của dãy 1, 4, 2, 10, 9, 8, 
 17, 11, 7, 12. 
 Yêu cầu: Tìm dãy con không giảm của dãy a gồm nhiều phần tử nhất. 
 Dữ liệu: đọc từ file văn bản DAYCON.INP gồm: 
 + Dòng 1: ghi số N là số lượng phần tử của dãy 
 + Các dòng tiếp theo: ghi N số a1, a2, , an. các số cách nhau ít nhất một 
 dấu cách 
 Kết quả: ghi ra file văn bản DAYCON.OUT gồm 2 dòng: 
 + Dòng 1: ghi độ dài dãy con tìm được 
 + Các dòng tiếp theo: ghi giá trị các phần tử được chọn vào dãy con từ 
 dãy ban đầu. 
 Ví dụ: 
 DAYCON.INP DAYCON.OUT 
 11 8 
 1 2 3 8 9 4 5 6 20 9 10 1 2 3 4 5 6 9 10 
Đặc điểm nhận diện và công thức quy hoạch động 
 - Đặc điểm nhận diện: 
 Tính chất của dãy con không giảm là phần tử đứng trước không lớn hơn phần 
 tử đứng sau. Nên khi xét đến phần tử ai, ta cần tìm phần tử aj (j<i) nào đó thỏa 
 mãn tính chất của dãy con không giảm. Giá trị tối ưu cần tìm là max về độ dài 
- Công thức quy hoạch động: 
 Gọi L[i] là độ dài dãy con không giảm dài nhất các phần tử xét từ a[1..i] 
và phần tử cuối cùng phải là a[i]. Vậy yêu cầu của bài toán ban đầu: max(L[i]) 
 L[1]: là độ dài dãy con không giảm dài nhất các phần tử xét từ a[1..1] và 
phần tử cuối cùng phải là a[1]. Vậy: L[1] = 1 
 Tính L[i]: L[i] = max(1, L[j] + 1), với điều kiện: j < i, a[j] <= a[i] 
 - Bảng phương án: 
 10 
 4 4 
 5 4 
 9 10 
 4 4 
Đặc điểm nhận diện và công thức quy hoạch động 
 - Đặc điểm nhận diện: 
 Tại thời điểm i, việc chọn hay không chọn ai vào túi phụ thuộc vào thời 
điểm i-1 ngay trước nó có tạo ra được tổng t hay tổng t-ai hay không 
 - Công thức quy hoạch động: 
 Gọi L(i,t) là tổng giá trị lớn nhất khi được chọn i vật từ 1 đến i cho vào ba lô 
với tổng khối lượng không vượt quá t. 
 L(n,m) sẽ là đáp số của bài toán (là giá trị lớn nhất có được nếu chọn n vật 
và tổng khối lượng không vượt m). 
 Công thức tính L(i,t) như sau: 
 L(i,0)=0; L(0,t)=0. 
 L(i,t)=L(i–1,t) nếu t<Wi. 
 L(i,t)=max(L(i–1,t), L(i–1,t–wi)+vi) nếu t ≥ wi. Trong đó: L(i–1,t) là giá trị có 
 được nếu không đưa vật i vào balô, L(i–1,t–wi)+vi là giá trị có được nếu chọn vật i. 
Điền giá trị vào bảng phương án L(i,t) 
 t 0 1 2 3 4 5 6 7 8 9 10 11 
 Wi Vi i 0 0 0 0 0 0 0 0 0 0 0 0 
 3 3 1 0 0 0 3 3 3 3 3 3 3 3 3 
 4 4 2 0 0 0 3 4 4 4 7 7 7 7 7 
 5 4 3 0 0 0 3 4 4 4 7 7 7 7 7 
 9 10 4 0 0 0 3 4 4 4 7 7 10 10 10 
 4 4 5 0 0 0 3 4 4 4 7 8 10 10 10 
 Đoạn chương trình tính các giá trị của mảng L (bảng phương án): 
 void QHD() 
 { 
 int i,j; F[0][0]=0; 
 for(i=1; i<=n; i++) 
 for(j=0; j<=M; j++) 
 { 
 F[i][j]=F[i-1][j]; 
 if((W[i]<=j)&&(F[i][j]<F[i-1][j-W[i]]+V[i])) F[i][j]=F[i-1][j-W[i]]+V[i]; 
 } 
 } 
 12 
 Gọi F[i, j] là số điểm lớn nhất có thể có được khi tới ô A[i, j]. Rõ ràng đối 
với những ô ở cột 1 thì F[i, 1] = A[i, 1]. Với những ô (i, j) ở các cột khác: Vì chỉ 
những ô (i, j – 1), (i – 1, j – 1), (i + 1, j –1) là có thể sang được ô (i, j), và khi 
sang ô (i, j) thì số điểm được cộng thêm A[i, j] nữa. Chúng ta cần F[i, j] là số 
điểm lớn nhất (nhỏ nhất) có thể nên 
 F[i, j] = max(F[i, j - 1], F[i –1, j - 1], F[i + 1, j - 1]) + A[i, j] 
 Ta dùng công thức truy hồi này tính tất cả các F[i, j]. Cuối cùng chọn ra 
F[i, n] là phần tử lớn nhất trên cột n của bảng F và từ đó truy vết tìm ra đường đi 
nhiều điểm nhất 
 - Đoạn chương trình: 
 void QHD() 
 { 
 for(int i=1;i<=M;i++)F[i][1]=A[i][1]; 
 for(int j=2;j<=N;j++) 
 for(int i=1;i<=M;i++) 
 F[i][j]=max(max(F[i-1][j-1],F[i][j-1]),F[i+1][j-1])+A[i][j]; 
 } 
7.2. Thuyết minh về phạm vi áp dụng sáng kiến: 
 Sáng kiến được áp dụng dạy học sinh lớp 11 tham gia các kì thi chọn học 
sinh giỏi các cấp (cấp huyện và đặc biệt cấp tỉnh). 
 Sáng kiến được áp dụng giảng dạy tại trường THPT Yên Thế và tại 02 
trường THPT khác trên địa bàn tỉnh Bắc Giang1. 
7.3. Thuyết minh về lợi ích kinh tế, xã hội của sáng kiến: 
-Về lợi ích kinh tế: 
 Tiết kiệm thời gian, công sức của giáo viên khi dạy chuyên đề quy hoạch 
động trong bồi dưỡng học sinh giỏi. Giải pháp trong sáng kiến kinh nghiệm có 
thể tiếp tục xây dựng mở rộng các dạng bài tương tự của các bài quy hoạch động 
cơ bản để thành tư liệu tham khảo cho giáo viên, tự nghiên cứu, xây dựng của 
những năm học sau. Qua đó tiết kiệm được các chi phí khác như: chi phí đi lại, 
mua tài liệu tham khảo, 
- Về lợi ích xã hội: 
 Sáng kiến sau khi được triển khai và áp dụng đã trao quyền chủ động cho học 
sinh trong mọi hoạt động học tập, kích thích được hứng thú học tập và sáng tạo 
1 Các trường THPT: Bố Hạ, Việt Yên số 1 
 14 
 Trường THPT Yên Thế: 
Kết quả 
bài kiểm 
tra lần 1 
Kết quả 
bài kiểm 
tra lần 2 
 Trường THPT Bố Hạ 
 Kết quả 
 bài kiểm 
 tra lần 1 
 Kết quả 
 bài kiểm 
 tra lần 2