Sáng kiến kinh nghiệm Sử dụng Quy hoạch động để giải quyết một số bài toán trong bồi dưỡng học sinh giỏi môn Tin học

 SỞ GD & ĐT NGHỆ AN 
 TRƯỜNG THPT LÊ VIẾT THUẬT 
 SÁNG KIẾN KINH NGHIỆM 
 Tên đề tài: 
 SỬ DỤNG QUY HOẠCH ĐỘNG 
 ĐỀ GIẢI QUYẾT MỘT SỐ BÀI TOÁN 
TRONG BỒI DƯỠNG HỌC SINH GIỎI MÔN TIN HỌC 
 Lĩnh vực: TIN HỌC 
 Tác giả: Trần Thị Anh Thư 
 Trần Diệu Thúy 
 Tổ: Toán - Tin 
 Năm học 2022 – 2023 
 2 
 - Phương pháp thực nghiệm 
- Phương pháp so sánh đối chiếu 
 IV. Cấu trúc của đề tài 
 Phần một: Đặt vấn đề 
 Phần hai: Nội dung 
 Phần ba: Kết luận 
 2 
 là mỗi kiểu khó khác nhau, không có một công thức chung cho tất cả các bài toán đó 
được. 
 Vậy khi nào chúng ta nên áp dụng đến thuật toán này? Thường bài toán có hai 
tính chất này là bạn có thể sử dụng thuật toán quy hoạch động vào. Đó chính là bài 
toán con gối nhau và cấu trúc con tối ưu. 
 Sử dụng thuật toán quy hoạch động khi nào? 
 Bài toán con gối nhau 
 Bài toán con gối nhau là bài toán nhỏ hơn và được chia từ bài toán ban đầu ra. 
Việc sử dụng lặp lại nhiều lần này, thuật toán sẽ lưu kết quả mà không cần tính lại, 
giúp bạn tiết kiệm rất nhiều thời gian. Việc giải một bài toán con nhiều lần thì không 
thể tránh khỏi việc trùng lời giải của các bài toán con. 
 Khi các bài toán con không gối nhau thì việc áp dụng thuật toán này cũng bằng 
không. Quy hoạch động không thể tối ưu được với thuật toán tìm kiếm nhị phân. Lý 
do vì khi chia bài toán lớn thành các bài toán nhỏ và mỗi bài toán chỉ cần giải một 
lần mà không được gọi lại. 
 Bài toán tính Fibonacci là ví dụ rất điển hình của bài toán con gối nhau. Bằng 
cách cộng fibonacci thứ n-1 và n-2 sẽ tính được số fibonacci thứ n. Bài toán con của 
số fibonacci thứ n chính là bài toán tính fibonacci n-1 và n-2. Công thức tính toán số 
Fibonacci được tính như sau: 
 def fib(n): 
 if n <= 1: 
 return n 
 return fib(n -1) + fib(n – 2) 
 Quy hoạch động chính là một trong số những giải pháp cực kỳ hiệu quả có thể 
tối ưu hóa quá trình tính toán này. Trước khi tiến hành tính những bài lớn thì mỗi 
bài toán con sẽ được lưu lại. Nhờ đó, mà việc tính toán giảm đi đáng kể, mỗi bài 
toán con chỉ cần tính đúng một lần. Nhờ đó mà thuật toán này được sử dụng rất nhiều 
trong các cuộc thi lập trình giúp các thí sinh giảm đáng kể thời gian tính toán. 
 Cấu trúc con tối ưu 
 Bài toán có cấu trúc con tối ưu là gì? Cấu trúc con tối ưu chính là tập hợp các 
lời giải tối ưu từ các bài toán con để tìm ra lời giải bài toán lớn. Bài toán có cấu trúc 
 4 
 Phương pháp lập bảng này trái ngược hoàn toàn với phương pháp ghi nhớ. Cách 
tiếp cận này sẽ không dùng đệ quy và giải quyết bài toán con liên quan từ dưới lên. 
Bạn trực tiếp giải tất cả bài toán nhỏ và điền vào bảng N chiều. Sau đó, dùng kết quả 
trong bảng để tìm ra dần lời giải cho bài toán ban đầu. Cách tiếp cận này hiệu quả 
và được sử dụng nhiều hơn phương pháp ghi nhớ bởi nó sẽ không làm tốn bộ nhớ 
và số lần gọi hàm. 
 1.2. Độ phức tạp của thuật toán 
 Giả sử ta có hai thuật toán P1 và P2 với thời gian thực hiện tương ứng là T1(n) 
 2 2 3 3
= 100n (với tỷ suất tăng là n ) và T2(n) = 5n (với tỷ suất tăng là n ). Khi n > 20 thì 
T1 < T2. Sở dĩ như vậy là do tỷ suất tăng của T1 nhỏ hơn tỷ suất tăng của T2. Như 
vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương trình 
thay vì xét chính bản thân thời gian thực hiện.Cho một hàm T(n), T(n) gọi là có độ 
phức tạp f(n) nếu tồn tại các hằng C, N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0 (tức 
là T(n) có tỷ suất tăng là f(n)) và kí hiệu T(n) là O(f(n)) (đọc là “ô của f(n)”). 
 2
 Các hàm thể hiện độ phức tạp có các dạng thường gặp sau: log2n, n, nlog2n, n , 
 3 n n
n , 2 , n!, n . Trong cách viết, ta thường dùng logn thay thế cho log2n cho gọn. 
 Khi ta nói đến độ phức tạp của thuật toán là ta nói đến hiệu quả thời gian thực 
hiện chương trình nên có thể xem việc xác định thời gian thực hiện chương trình 
chính là xác định độ phức tạp của thuật toán. 
 1.3. Phương pháp lựa chọn và cài đặt chương trình tối ưu khi giải một 
 số dạng bài tập về dãy con 
 Đối với mỗi dạng bài tập về dãy con, chúng tôi đưa ra một bài toán cơ bản, từ 
mỗi bài toán cơ bản chúng tôi trình bày từ 2 hoặc 3 cách giải (cả cách làm của học 
sinh và cách làm chúng tôi định hướng cho học sinh làm). Với phương châm“ mưa 
dầm thấm lâu”, chúng tôi không hướng dẫn học sinh cách làm tối ưu ngay mà khi 
phát vấn một dạng bài tập mới mà yêu cầu học sinh làm theo các trình tự sau: 
Bước 1: Xác định bài toán 
Bước 2: Suy nghĩ tìm ra thuật toán, viết chương trình, tính độ phức tạp (Có thể nhiều 
cách). 
Bước 3: Trao đổi cách làm của mình với bạn để tìm cái hay cái dở. 
Bước 4: Sử dụng phần mềm Themis-chấm bài tự động để chấm cách làm của mình 
(với 10 bộ test hoặc nhiều hơn mà giáo viên đã xây dựng sẵn, mỗi bộ test cấu hình 
là 1 điểm, thời gian chạy không quá 1 giây). 
Bước 5: Nhận xét sự tối ưu của thuật toán. 
Bước 6: Giáo viên định hướng cách làm tối ưu hơn (nếu có). 
Bước 7: Sử dụng phần mềm Themis để chấm tất cả các cách đã viết chương trình. 
Bước 8: Dựa vào kết quả, lựa chọn chương trình có độ phức tạp nhỏ nhất, thời gian 
thực hiện mỗi test nhỏ nhất và chương trình ngắn gọn dễ hiểu nhất. 
Bước 9: Lập trình giải các bài tập tương tương với cách đã lựa chọn. 
 6 
 2.2. Thực trạng dạy học và kiểm tra đánh giá của giáo viên 
 a) Khảo sát thực trạng 
 Chúng tôi đã tiến hành tìm hiểu thực trạng việc dạy học và kiểm tra đánh giá 
của giáo viên (gồm 6 giáo viên dạy Tin học tại trường THPT Lê Viết Thuật). 
 b) Phân tích, đánh giá thực trạng 
 Chúng tôi nhận thấy: 
- Việc dạy học của giáo viên đang hướng dẫn và sử dụng các bài toán, thuật toán cơ 
bản. (chủ yếu sử dụng sách giáo khoa và sách bài tập Tin học 11) 
- Việc kiểm tra đánh giá của giáo viên vẫn còn nặng theo chuẩn kiến thức kĩ năng. 
- Đối với những HS có học lực môn Tin khá, giỏi, GV chưa tổ chức bồi dưỡng tập 
trung hết được mà chỉ dành hướng dẫn 1 số ít HS có tham gia đội tuyển HSG. GV 
cũng chưa có 1 tài liệu cụ thể để dạy bồi dưỡng HSG mà chỉ tìm hiểu tham khảo để 
hướng dẫn HS. Việc sử dụng các tài liệu chuyên tin cũng gặp khó khăn với năng lực 
HS của trường. 
 2.3. Thực trạng về tài liệu tham khảo 
 a) Khảo sát thực trạng: 
 Để có được kết luận về thực trạng tài liệu tham khảo, chúng tôi đã tiến hành 
khảo sát các tài liệu tham khảo: 
 1. Sách giáo khoa và sách bài tập môn Tin học lớp 11 (NXB GD Việt Nam). 
 b) Phân tích, đánh giá thực trạng: 
 Từ kết quả khảo sát đó, chúng tôi có nhận xét như sau: 
 - Các sách trên đề cập đến các thuật toán Sắp xếp, tìm kiếm không đề cập đến 
thuật toán về quy hoạch động. 
 - Đối với môn Tin học sách tham khảo dùng cho học sinh trong phần lập trình 
không phong phú như các môn tự nhiên khác nên khó khăn trong việc giảng dạy và 
học nội dung này. 
 - Các chương trình mà một số tài liệu đưa ra rất khó hiểu và phức tạp không 
phù hợp năng lực học sinh đại trà Trường THPT Lê Viết Thuật. 
 Vì vậy việc nghiên cứu và áp dụng đề tài “Sử dụng Quy hoạch động để giải 
quyết một số bài toán trong bồi dưỡng học sinh giỏi môn Tin học” hi vọng sẽ trở 
thành nguồn tài liệu tham khảo hữu ích cho giáo viên và học sinh trong quá trình 
dạy và học. 
 II. Sử dụng Quy hoạch động để giải quyết một số bài toán trong bồi 
 dưỡng học sinh giỏi môn Tin học 
 1. Dạng bài tập chủ đề về đoạn con đạt giá trị tối ưu (tổng, độ dài đạt 
 max, min) 
 Bài 1: Đoạn con có Tổng lớn nhất 
 8 
 Bài 2: Dãy con đan dấu 
 Cho dãy số nguyên a[1], a[2],..., a[n]. Tìm dãy con đan dấu có giá lớn nhất của 
dãy số trên. 
 Dãy con đan dấu được định nghĩa như sau: Giả sử ta chọn dãy con bắt đầu từ i 
và kết thúc tại j của dãy số trên, lúc đó giá trị của dãy đan dấu sẽ là a[i] – a[i + 1] + 
a[i + 2] - ... +(-) a[j]. 
 Input: Gồm có hai dòng, dòng đầu là số nguyên dương n ≤ 1000000, dòng thứ 
hai chứa n số nguyên mô tả dãy số trên. 
 Output: Đưa ra một dòng là kết quả bài toán. 
Ví dụ: 
 Input Output 
 7 21 
 1 -2 7 -3 2 3 9 
Thuật toán: 
 - Gọi F[i][0] là dãy đan dấu có giá trị lớn nhất kết thúc tại i, và a[i] mang dấu + 
ở trước, còn F[i][1] là dãy đan dấu có giá trị lớn nhất kết thúc tại i, và a[i] mang dấu 
- ở trước. Lúc này, tương tự như bài 1, F[i][0] sẽ được tính dựa trên F[i – 1][1] nếu 
ta lấy dãy đan dấu nhiều hơn 1 phần tử, hoặc chỉ lấy a[i] nếu như ta lấy đúng 1 phần 
tử, còn F[i][1] sẽ luôn phải được tính dựa trên F[i-1][0], do a[i] khi đứng một mình 
không thể mang dấu - ở trước nó theo định nghĩa ở trên. 
 - Lúc này kết quả của ta sẽ là max(F[i][0], F[i][1]) với mọi i từ 1 tới n. 
 - Độ phức tạp: O(N). 
 Chương trình: 
 #include 
 usingnamespace std; 
 constlonglong INF =1e18; 
 int n; 
 int a[1000005]; 
 longlong F[1000005][2]; 
 int main(){ 
 ios::sync_with_stdio(false); 
 cin.tie(0); cout.tie(0); 
 cin >> n; 
 for(int i =1; i <= n; i++){ 
 cin >> a[i];} 
 for(int i =0; i <= n; i++){ 
 F[i][0]= F[i][1]=-INF;} 
 for(int i =1; i <= n; i++){ 
 F[i][0]= max(0LL, F[i -1][1])+ a[i]; 
 F[i][1]= F[i -1][0]- a[i];} 
 longlong answer =-INF; 
 10 
 F[i]=1; 
 if(a[i]> a[i -1]) F[i]+= F[i -1];} 
 int answer =0; 
 for(int i =1; i <= n; i++){ 
 answer = max(answer, F[i]);} 
 cout << answer << endl; 
 return0; 
 } 
 Bài 4: Dãy con dài nhất tăng 2 
 Cho dãy số nguyên a[1], a[2],..., a[n]. Tìm dãy con dài nhất trong dãy mà các 
phần tử của nó tăng dần từ trái qua phải. 
 Dãy con của một dãy số là dãy bất kỳ thu được khi xóa đi một vài (có thể không) 
số của dãy ban đầu, và các số còn lại giữ nguyên vị trí của nó. 
Input: Gồm có hai dòng, dòng đầu là số nguyên dương n ≤ 5000, dòng thứ hai chứa 
n số nguyên mô tả dãy số trên. 
Output: Đưa ra một dòng là kết quả bài toán. 
Ví dụ: 
 Input Output 
 10 6 
 1 7 2 8 3 6 4 10 5 9 
Thuật toán: 
 - Gọi F[i]là dãy con tăng dài nhất kết thúc tại vị trí i. Lúc này ta sẽ phải tính 
F[i] dựa trên các giá trị F[j] với j < i, do dãy con kết thúc tại vị trí i có thể được xây 
dựng bằng cách lấy một dãy con kết thúc ở một vị trí j < i, và nếu như a[j] < a[i] thì 
ta thêm a[i] vào sau để tạo thành một dãy tăng. Vì thế công thức quy hoạch động của 
ta sẽ là F[i] = max(F[j]) + 1, điều kiện j < i và a[j] < a[i]. 
 - Tương tự như các ví dụ ở trên, kết quả của ta sẽ là vị trí có F max. 
 - Độ phức tạp: O(N^2). 
 Chương trình: 
 #include 
 usingnamespace std; 
 int n; 
 int a[5005]; 
 int F[5005]; 
 int main(){ 
 ios::sync_with_stdio(false); 
 cin.tie(0); cout.tie(0); 
 cin >> n; 
 for(int i =1; i <= n; i++){ 
 cin >> a[i];} 
 12 
 longlong F[1000005]; 
 int main(){ 
 ios::sync_with_stdio(false); 
 cin.tie(0); cout.tie(0); 
 cin >> n; 
 for(int i =1; i <= n; i++){ 
 cin >> a[i];} 
 for(int i =1; i <= n; i++){ 
 F[i]=-INF;} 
 F[1]= a[1]; 
 for(int i =1; i <= n; i++){ 
 if(i +1<= n) F[i +1]= max(F[i +1], F[i]+ a[i +1]); 
 if(2* i <= n) F[2* i]= max(F[2* i], F[i]+ a[2* i]); 
 if(2* i +1<= n) F[2* i +1]= max(F[2* i +1], F[i]+ a[2* i +1]);} 
 longlong answer =-INF; 
 for(int i =1; i <= n; i++){ 
 answer = max(answer, F[i]);} 
 cout << answer << endl; 
 return0; 
 } 
 Bài 6. 
 Cho dãy số có n phần tử và Q truy vấn, mỗi truy vấn cho một đoạn [L, R] thuộc 
[1,n], yêu cầu đưa ra tổng các phần tử thuộc đoạn [L, R]. 
Input: - Dòng đầu gồm số nguyên dương n ≤ 1000000, số phần tử của dãy. 
- Dòng thứ hai gồm n số nguyên, miêu tả dãy số. 
- Dòng thứ ba chứa số nguyên dương Q ≤ 1000000, miêu tả số truy vấn. 
- Tiếp theo gồm Q dòng, mỗi dòng là một câu hỏi [L, R] như đã mô tả. 
Output: In ra Q dòng mỗi dòng là một câu trả lời cho mỗi truy vấn. 
Ví dụ: 
 Input Output 
 10 21 
 1 7 -2 8 -3 6 4 -10 5 9 10 
 5 6 
 1 7 -1 
 2 8 25 
 3 4 
 7 9 
 1 10 
Thuật toán: 
 - Với mỗi câu hỏi, ta có thể trả lời một cách ngây thơ bằng cách duyệt qua mọi 
phần tử trong đoạn [L, R], dùng một biến sum để lưu tổng và cộng dần giá trị của 
từng phần tử vào sum. Tuy nhiên, nêu làm như vậy thì độ phức tạp của thuật toán có 
thể lên tới O(Q*N), không đủ để qua được giới hạn của đề bài. 
 14 
 10 14 
 1 7 -2 8 -3 6 4 -10 5 9 24 
 2 
 3 6 
 6 10 
 Thuật toán: 
 - Mấu chốt của bài toán này nằm ở việc làm sao ta có thể lấy được dãy con có 
tổng lớn nhất của một dãy đã cho, điều này rất đơn giản, ta chỉ việc lấy tất cả những 
số > 0 của dãy và dĩ nhiên dãy được tạo bởi các số đó luôn là dãy con có tổng lớn 
nhất của dãy ban đầu, và trường hợp đặc biệt khi mà dãy không có số nào >= 0, thì 
dãy con có tổng lớn nhất của nó sẽ là dãy rỗng, với tổng = 0. 
 - Đến đây, bài toán trở về giống với bài 6, chỉ khác ở chỗ công thức quy hoạch 
động của ta sẽ thay đổi đôi chút, bởi vì ta sẽ không lấy các số < 0 vào mảng sum của 
mình. 
 - Độ phức tạp: O(N + Q). 
 Chương trình: 
 #include 
 usingnamespace std; 
 int n, Q, a[1000005]; 
 longlong sum[1000005]; 
 int main(){ 
 ios::sync_with_stdio(false); 
 cin.tie(0); cout.tie(0); 
 cin >> n; 
 for(int i =1; i <= n; i++){ 
 cin >> a[i];} 
 sum[0]=0; 
 for(int i =1; i <= n; i++){ 
 sum[i]= sum[i -1]+ max(0, a[i]); 
 } 
 cin >> Q; 
 for(int i =1; i <= Q; i++){ 
 int L, R; 
 cin >> L >> R; 
 cout << sum[R]- sum[L -1]<< endl;} 
 return0; 
 } 
 Bài 8. 
 Cho một xâu ký tự S chỉ gồm các ký tự Latinh in hoa. Yêu cầu đếm số lượng 
xâu con là “THU” ở trong S. Xâu con của một xâu là một xâu thu được bằng cách 
xóa đi một vài ký tự của xâu ban đầu. 
 Input: - Dòng đầu là số tự nhiên n ≤ 1000000, độ dài xâu S. 
 16 
 longlong result =0; 
 for(int i =2; i < n; i++){ 
 if(S[i]=='H'){ 
 result +=(1LL* leftT[i]* rightU[i]);}} 
 cout << result << endl; 
 return0; 
 } 
 Bài 9. 
 Cho một xâu ký tự S chỉ gồm các ký tự Latinh in hoa. Yêu cầu tìm xâu con liên 
tiếp dài nhất mà các phần tử của nó là giống nhau. 
 Input: - Dòng đầu là số tự nhiên n ≤ 1000000, độ dài xâu S. 
 - Dòng thứ hai gồm n ký tự Latinh in hoa mô tả xâu S. 
 Output: In ra một dòng là độ dài của xâu thỏa mãn. 
 Ví dụ: 
 Input Output 
 14 4 
 AZZZZBBYKHAAAI 
 Thuật toán: 
 - Gọi F[i] là độ dài xâu con liên tiếp dài nhất mà mọi phần tử của nó là giống 
nhau và xâu con đó kết thúc tại vị trí i, ta có nếu như S[i] = S[i – 1] thì F[i] = F[i – 
1] + 1, còn nếu không thì F[i] = 1, do nếu S[i] = S[i – 1] thì việc ghép S[i] vào xâu 
con dài nhất kết thúc ngay trước đó thì ta tất nhiên sẽ được xâu con dài nhất kết thúc 
tại i, còn nếu không thì S[i] và S[i – 1] không thể được ghép với nhau, và F[i] = 1. 
 - Độ phức tạp: O(N). 
 Chương trình: 
 #include 
 usingnamespace std; 
 int main(){ 
 ios::sync_with_stdio(false); 
 cin.tie(0); cout.tie(0); 
 int n; 
 string S; 
 cin >> n >> S; 
 S =' '+ S; 
 vector F(n +1,0); 
 int ans =0; 
 for(int i =1; i <= n; i++) 
 { 
 if(i ==1) F[i]=1; 
 else{ 
 if(S[i]== S[i -1]) F[i]= F[i -1]+1; 
 else F[i]=1; 
 18