Sáng kiến kinh nghiệm 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

n giải bài 
toán tối ưu 
- Thuật toán vét cạn là thuật toán tìm phương án 
tối ưu của bài toán bằng cách lựa chọn một 
phương án trong tập hợp tất cả các phương án của 
bài toán để tìm ra phương án tối ưu. Trong nhiều 
bài toán, không gian các phương án quá lớn. Vét 
cạn giúp tìm ra kết quả tối ưu nhưng độ phức tạp 
lớn, thường là hàm mũ trong khi phương pháp 
quy hoạch động độ phức tạp là đa thức. Do vậy, 
khi áp dụng thuật toán vét cạn không đảm bảo về 
thời gian cũng như kĩ thuật. Vét cạn là xét toàn 
bộ trường hợp, rồi tìm ra kết quả. 
- Ưu điểm của vét cạn là chắc chắn tìm ra lời giải 
(nếu có) 
- Nhược điểm của nó là có thể chạy quá lâu, vượt 
mức thời gian cho phép 
Chú ý: Vét cạn theo nghĩa thông thường là xét 
hết mọi đối tượng hay mọi trường hợp. Trong lập 
trình, vét cạn là phương pháp được dùng khi 
không còn phương pháp nào hiệu quả hơn có thể 
sử dụng được. 
III. Cài đặt chương trình cho một số bài toán đơn giản thường gặp 
Vì trong đề tài chỉ nói đến những bài toán đơn giản nên thường là những bài toán 
dễ tìm ra phương pháp giải và phương pháp giải thường dùng là đệ quy hoặc quy hoạch 
16 
động. Nên phần ví dụ trong SKKN này mỗi bài toán tôi chỉ xin phép đề cập đến mối 
tương quan giữa hai phương pháp là đệ quy và quy hoạch động. Tức là trong phần 
chương trình của từng bài tôi thường có thêm biến “đếm” để đếm số lần lặp thực hiện 
trong từng bài khi chạy cùng số test để người học có thể thấy được cái nào hay, cái nào 
ngắn hơn. Giúp người học dể hiểu, dễ phân biệt và rút ra được cái hay và cái chưa hay 
của quy hoạch động trong từng bài toán. 
Ví dụ 1: Bài toán tính an (n là số nguyên dương). 
Cách xác định bài toán 
 - Input: a, n 
 - Output: giá trị an 
Ý tưởng của bài toán 
 - Ta thấy n = 0 thì f(0) =1 
 n = 1 thì f(1) = a 
 n = 2 thì f(2) = f(1)*a 
 n = 3 thì f(3) = f(2)*a 
 .. 
 n = i thì f(i) = f(i-1)*a 
 - Trong bài toán này có giá trị chặn là n = 0 
Cài đặt chương trình 
Phương pháp QHĐ Phương pháp ĐQ 
uses crt; 
var n,i,a,dem:longint; 
 g:text; 
 f:array[0..100] of int64; 
 function lthua(a,n:longint):int64; 
begin 
 f[0]:=1; 
 for i:=1 to n do 
 begin 
 f[i]:=a*f[i-1]; 
uses crt; 
var n,a,dem:longint; 
 f:text; 
 function lthua(a,n:longint):int64; 
begin 
 dem:=dem+1; 
 if n =0 then lthua:=1 
 else lthua:=a*lthua(a,n-1); 
end; 
BEGIN 
17 
 dem:=dem+1; 
 end; 
 lthua:=f[i]; 
end; 
BEGIN 
 clrscr; 
 assign(g,'nhap.inp'); reset(g); 
 dem:=0; 
 //write('nhap a,n:=');readln(a,n); 
 readln(g,a,n); 
 close(g); 
 lthua(a,n); 
 assign(g,'xuat.out'); rewrite(g); 
 writeln(g,'KQ BT lthua thuc hien 
bang pp QHD la:'); 
 writeln(g,'so lan lap la:=',dem); 
 write(g,'lthua la:=',lthua(a,n)); 
 close(g); 
 END. 
 clrscr; 
 dem:=0; 
 assign(f,'nhap.inp'); reset(f); 
 //write('nhap a,n:=') ; readln(a,n); 
 readln(f,a,n); 
 close(f); 
 assign(f,'xuat.out'); rewrite(f); 
 lthua(a,n); 
 writeln(f,'KQ BT luy thua thuc hien 
bang pp DE QUY la:'); 
 writeln(f,'so lan lap la:=',dem); 
 write(f,'luy thua la:=',lthua(a,n)); 
 close(f); 
END. 
Chạy thử chương trình 
18 
* Nhận xét: Qua phần chạy thử bộ test 210 ta thấy chương trình chạy bằng quy hoạch 
động số lần lặp là 10. Còn chương trình chạy bằng đệ quy số lần lặp lại bằng 11. Số lần 
lặp sử dụng phương pháp QHĐ ít hơn sử dụng phương pháp ĐQ 1 lần. 
Ví dụ 2: Tính n! (n là số nguyên dương) 
Cách xác định bài toán 
 - Input: n 
 - Output: giá trị giai thừa của n 
Ý tưởng của bài toán 
 - Ta thấy n = 0 thì f(0) =1 
 n = 1 thì f(1) = 1 
 n = 2 thì f(2) = f(1)*2 
 n = 3 thì f(3) = f(2)*3 
 .. 
 n = i thì f(i) = f(i-1)*i 
 - Trong bài toán này có hai giá trị chặn là n = 0 và n = 1 
Cài đặt chương trình 
Phương pháp QHĐ Phương pháp ĐQ 
Uses crt; 
var n,i,dem:longint; 
 g:text; 
 f:array[0..100] of int64; 
 function gthua(n:longint):int64; 
begin 
 f[1]:=1; 
 for i:= 2 to n do 
 begin 
 dem:=dem+1; 
 f[i]:=i*f[i-1]; 
 end; 
Uses crt; 
var dem,n:longint; 
 f:text; 
 function gthua(n:longint):int64; 
begin 
 dem:=dem+1; 
 if n <2 then gthua:=1 
 else gthua:=(n*gthua(n-1)); 
end; 
BEGIN 
 clrscr; 
 dem:=0; 
19 
 exit(f[n]); 
end; 
BEGIN 
 clrscr; 
 dem := 1; 
 //write('nhap n:='); readln(n); 
 //n := 15; 
 assign(g,'nhap.inp'); reset(g); 
 readln(g,n); 
 close(g); 
 assign(g,'xuat.out'); 
 rewrite(g); 
 gthua(n) ; 
 writeln(g,'KQ BT tinh GIAI THUA 
bang PP QHD la:'); 
 writeln(g,'So lan lap la:=',dem); 
 writeln(g,'Giai thua cua so ',n,' co 
gia tri la:=',gthua(n)); 
 close(g); 
END. 
 //write('nhap n:='); readln(n); 
 assign(f,'nhap.inp'); reset(f); 
 readln(f,n); 
 close(f); 
 assign(f,'xuat.out'); rewrite(f); 
 gthua(n) ; 
 writeln(f,'KQ BT tinh GIAI THUA 
bang PP DE QUY la:'); 
 writeln(f,'So lap la:=',dem); 
 writeln(f,'Giai thua cua ',n,' co gia 
tri la:=',GTHUA(n)); 
 close(f); 
END. 
Chạy thử chương trình 
20 
* Nhận xét: Ta chạy thử với test bằng 5 thì số lần lặp của hai phương pháp trên là như 
nhau, đều lặp lại 5 lần. Ta thấy rằng trong trường hợp này phương pháp quy hoạch động 
không hơn gì phương pháp đệ quy. 
Ví dụ 3: Dãy số fibonacci: 
Tính số hạng thứ n của dãy fibonacci bằng phương pháp đệ quy. 
Trong đó chuỗi có giá trị như sau: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 
Cách xác định bài toán 
 - Input: n 
 - Output: giá trị fibonacci của n 
Ý tưởng của bài toán 
 - Ta thấy n = 0 thì f(0) =1 
 n = 1 thì f(1) = 1 
 n = 2 thì f(2) = f(1) + f(0) 
 n = 3 thì f(3) = f(2) + f(1) 
 .. 
 n = i thì f(i) = f(i-1) + f(i-2) 
 - Trong bài toán này có hai giá trị chặn là n = 0 và n = 1 
Cài đặt chương trình 
Phương pháp QHĐ Phương pháp ĐQ 
uses crt; 
var n,i,a,dem:longint; 
 f:array[0..100] of longint; 
 g:text; 
function qhd(n:longint):int64; 
begin 
 f[0]:=1; f[1]:=1; 
 for i:=2 to n do 
 begin 
 f[i]:=f[i-1]+f[i-2]; 
uses crt; 
var n,i,dem:longint; 
 f:text; 
function dq(n:longint):int64; 
begin 
 dem:=dem+1; 
 if n<2 then exit(1) 
 else exit(dq(n-1)+dq(n-2)); 
end; 
BEGIN 
21 
 dem:=dem+1 ; 
 end; 
 qhd:=f[i]; 
end; 
BEGIN 
 clrscr; 
 dem := 2; 
 // Write('nhap n:='); readln(n); 
 assign(g,'nhap.inp'); reset(g); 
 readln(g,n); 
 close(g); qhd(n); 
 assign(g,'xuat.out'); rewrite(g); 
 writeln(g,'KQ BT tinh so FIBO bang 
PP QHD la:'); 
 writeln(g,'So lan lap la:=',dem); 
 writeln(g,'So FIBO thu ',n,' co gia tri 
la:=',qhd(n)); 
 close(g); 
END. 
 clrscr; 
 dem:=0; 
 //Write('nhap n:='); readln(n); 
 assign(f,'nhap.inp'); reset(f); 
 readln(f,n); 
 close(f); 
 dq(n) ; 
 assign(f,'xuat.out'); rewrite(f); 
 writeln(f,'KQ BT tinh so FIBO bang 
PP DE QUY la:'); 
 writeln(f,'So lan lap la:=',dem); 
 writeln(f,'So FIBO thu ',n,' co gia tri 
la:=',dq(n)); 
 close(f); 
END. 
Chạy thử chương trình 
22 
* Nhận xét: Trong bài toán này khi chạy thử với giá trị n nhỏ thì thấy số lần lặp không 
hơn nhau nhiều. Nhưng khi chạy thử với giá trị n lớn hơn thì đối với phương pháp QHĐ 
ta thấy số lần lặp là 41. Còn đối với phương pháp ĐQ số lần lặp là 331 160 281, lớn 
hơn rất nhiều so với QHĐ. Như vậy, trong bài toán này ta chọn PP QHĐ sẽ nhanh hơn 
ĐQ rất nhiều. 
Ví dụ 4: Bài toán tháp Hà Nội 
Chuyển n chiếc đĩa từ cọc 1 sang cọc 2 theo thứ tự từ lớn đến nhỏ. có sử dụng cọc 
3 làm cọc trung gian. Mỗi lần di chuyển được 1 đĩa. Và đĩa đĩa lớn phải ở dưới đĩa 
nhỏ. 
Cách xác định bài toán 
 - Input: n 
 - Output: Số bước thực hiện chuyển đĩa từ cọc này sang cọc khác. 
Ý tưởng của bài toán 
Đầu tiên ta phải chuyển được tất cả (n-1) đĩa nhỏ qua cột thứ hai, chuyển đĩa to 
nhất qua cột thứ ba rồi chuyển (n-1) đĩa từ cột thứ hai sang cột thứ ba. Trò chơi sẽ kết 
thúc! 
Nếu gọi S(n) là số bước để di chuyển n đĩa qua cột ta cần thì: 
 Bước 1: Chuyển (n-1) đĩa bé hơn từ cột (1) sang cột (2). Chúng ta có S(n-1) 
bước di chuyển. 
 Bước 2: Chuyển đĩa to nhất từ cột (1) sang cột (3). Chúng ta có 1 bước di 
chuyển. 
 Bước 3: Chuyển (n-1) đĩa từ cột (2) sang cột (3). Chúng ta có S(n-1) bước di 
chuyển. 
23 
Cài đặt chương trình 
Phương pháp QHĐ Phương pháp ĐQ 
uses crt; 
var dem,i,n:longint; 
 f:array[0..100] of longint; 
 g:text; 
function thaphn(n:longint):longint; 
begin 
 // dem:=dem+1; 
 f[1]:=1; 
 for i:=2 to n do 
 begin 
 f[i]:=2*f[i-1]+1; 
 dem := dem+1; 
 end; 
 thaphn:=f[i]; 
end; 
BEGIN 
 clrscr; 
 dem := 1; 
 //write('Nhap vao so chiec dia:='); 
readln(n); 
 assign(g,'nhap.inp'); reset(g); 
 readln(g,n); 
 close(g); 
 assign(g,'xuat.out'); rewrite(g); 
 writeln(g,'KQ BT thap HA NOI bang 
PP QHD la:'); 
uses crt; 
var dem,n:longint; 
f:text; 
function thaphn(n:longint):longint; 
begin 
 dem:=dem+1; 
 if n=1 then exit(1) 
 else exit (1+2*thaphn(n-1)) ; 
end; 
BEGIN 
 clrscr; 
 dem:=0; 
 assign(f,'nhap.inp'); 
 reset(f); 
 readln(f,n); 
 close(f); 
 assign(f,'xuat.out'); 
 rewrite(f); 
 // write('Nhap vao so chiec dia:='); 
readln(n); 
 writeln(f,'KQ BT thap HA NOI bang 
PP DQ la:'); 
 // thaphn(n); 
 writeln(f,'so lan chuyen la : 
',thaphn(n)); 
 writeln(f,'So lan lap la:=',dem); 
24 
 //thaphn(n); 
 writeln(g,'so lan chuyen la : 
',thaphn(n)); 
 writeln(g,'So lan lap la:=',dem); 
 close(g); 
END. 
 close(f); 
END. 
Chạy thử chương trình 
* Nhận xét: Trong bài toán này cả hai phương pháp đều có số lần lặp như nhau. 
Ví dụ 5: Bài toán cái túi 
Trong siêu thị có n gói hàng (n <= 100), gói hàng thứ i có trọng lượng là Wi <= 
100 và trị giá Vi <= 100. Một tên trộm đột nhập vào siêu thị, sức của tên trộm không 
thể mang được trọng lượng vượt quá M (M <= 100). Hỏi tên trộm sẽ lấy đi những gói 
hàng nào để được tổng giá trị lớn nhất. 
Cách xác định bài toán 
caitui.inp caitui. out 
 Dòng 1: n, m cách nhau ít nhất một 
dấu cách 
 n dòng tiếp theo: Mỗi dòng gồm 2 
số Wi, Vi, là chi phí và giá trị đồ 
vật thứ i. 
Ghi giá trị lớn nhất tên trộm có thể lấy 
Ví dụ 
25 
caitui.inp caitui. out 
5 15 
12 4 
2 2 
1 1 
1 2 
4 10 
15 
Ý tưởng của bài toán 
Giải quyết bài toán trong các trường hợp sau: 
 Mỗi vật chỉ được chọn một lần. 
 Mỗi vật được chọn nhiều lần (không hạn chế số lần) 
Cách giải: 
* Trường hợp mỗi vật được chọn 1 lần 
Ta nhận thấy rằng: Giá trị của cái túi phụ thuộc vào 2 yếu tố: Có bao nhiêu vật 
đang được xét và trọng lượng còn lại cái túi có thể chứa được, do vậy chúng ta có 2 đại 
lượng biến thiên. Cho nên hàm mục tiêu sẽ phụ thuộc vào hai đại lượng biến thiên. Do 
vậy bảng phương án của chúng ta sẽ là bảng 2 chiều. 
Gọi F[i,j] là tổng giá trị lớn nhất của cái túi khi xét từ vật 1 đến vật i và trọng của 
cái túi chưa vượt quá j. Với giới hạn j, việc chọn tối ưu trong số các vật {1,2,,i-1,i} 
để có giá trị lớn nhất sẽ có hai khả năng: 
Nếu không chọn vật thứ i thì F[i,j] là giá trị lớn nhất có thể chọn trong số các vật 
{1,2,,i-1} với giới hạn trọng lượng là j, tức là: 
F[i,j]:=F[i-1,j]. 
Nếu có chọn vật thứ i (phải thỏa điều kiện W[i] ≤ j) thì F[i,j] bằng giá trị vật thứ 
i là V[i] cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các vật 
{1,2,,i-1} với giới hạn trọng lượng j-W[i] tức là về mặt giá trị thu được: 
F[i,j]:=V[i]+F[i-1,j-W[i]] 
Vậy chúng ta phải xem xét xem nếu chọn vật i hay không chọn vật i thì sẽ tốt hơn. 
Từ đó chúng ta có công thức truy hồi như sau. 
 F[0,j] = 0 (hiển nhiên) – Bài toán con nhỏ nhất. 
26 
 F[i,j]= max(F[i-1,j], V[i]+F[i-1,j-W[i]] 
* Trường hợp mỗi vật được chọn nhiều lần: Tương tự như suy luận ở trên ta xét: 
Nếu không chọn vật thứ i thì F[i,j] là giá trị lớn nhất có thể chọn trong số các vật 
{1,2,,i-1} với giới hạn trọng lượng là j, tức là: 
F[i,j]:=F[i-1,j]. 
Nếu có chọn vật thứ i (phải thỏa điều kiện W[i] ≤ j) thì F[i,j] bằng giá trị vật thứ 
i là V[i] cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các vật 
{1,2,,i} (vì vật i vẫn có thể được chọn tiếp) với giới hạn trọng lượng j-W[i] tức là về 
mặt giá trị thu được: 
F[i,j]:=V[i]+F[i,j-W[i]] 
Do vậy chúng ta có công thức truy hồi như sau: 
 F[0,j] = 0 (hiển nhiên) – Bài toán con nhỏ nhất. 
 F[i,j]= max(F[i-1,j], V[i]+F[i,j-W[i]] 
Cài đặt chương trình 
Phương pháp QHĐ Phương pháp ĐQ 
uses crt; 
const 
 fi='nhap.inp'; 
 fn='xuat.out'; 
var 
 g1,g2:text; 
 n,m,i,j,dem:longint; 
 v,w:array[1..100] of longint; 
 f:array[0..100,0..100] of longint; 
//================= 
procedure qhd; 
begin 
 fillchar(f[0],sizeof(f[0]),0); 
 for i:=1 to n do 
uses crt; 
const 
 fi='nhap.inp'; 
 fn='xuat.out'; 
var 
 g1,g2:text; 
 v,w,f:array[0..100] of longint; 
 n,m,i,j,dem,max:longint; 
 kt:array[0..100] of boolean; 
//================= 
procedure test; 
var i1,s1,s:longint; 
begin 
s:=0; s1:=0; 
27 
 for j:=0 to m do 
 begin 
 dem:=dem+1; 
 f[i,j]:=f[i-1,j]; 
 if (j>=v[i]) and 
(f[i-1,j-v[i]]+w[i]>f[i,j]) then 
 f[i,j]:=f[i-1,j-
v[i]]+w[i]; 
 end; 
end; 
//================== 
begin 
 clrscr; 
 assign(g1,fi); reset(g1); 
 assign(g2,fn); rewrite(g2); 
 readln(g1,n,m); 
 for i:=1 to n do 
readln(g1,v[i],w[i]); 
 dem:=0; 
 qhd; 
 writeln(g2, 'KQ cua BT cai tui 
giai = pp qhd la: '); 
 writeln(g2, 'gia tri lon nhat co 
the la: ', f[n,m]); 
 writeln(g2, 'so lan lap la: ', 
dem); 
 close(g1); close(g2); 
end. 
 for i1:=1 to n do 
 begin 
 inc(dem); 
 s:=s+w[f[i1]]; 
 s1:=s1+v[f[i1]]; 
 if s1>m then exit; 
 end; 
 if s>max then max:=s; 
end; 
//=================== 
procedure try(i:longint); 
var j:longint; 
begin 
inc(dem); 
 for j:=0 to n do 
 if (j=0) or (kt[j]) then 
 begin 
 kt[j]:=false; 
 f[i]:=j; 
 if (i=n) then test 
 else try(i+1); 
 kt[j]:=true; 
 end; 
end; 
//=================== 
begin 
 clrscr; 
 assign(g1,fi); reset(g1); 
28 
* Nhận xét: Trong bài toán này ta thấy PP QHĐ có số lần lặp ít hơn rất nhiều so với 
PP ĐQ. 
 assign(g2,fn); rewrite(g2); 
 readln(g1,n,m); 
 v[0]:=0; w[0]:=0; dem:=0; 
 for i:=1 to n do 
 begin 
 kt[i]:=true; 
 readln(g1,v[i],w[i]); 
 end; 
 max:=0; try(1); 
 writeln(g2,' KQ cua BT cai tui 
bang PP DQ la :'); 
 writeln(g2,' gia tri lon nhat : 
',max); 
 writeln(g2,' so lan lap la: ',dem); 
close(g1); close(g2); 
end. 
Chạy thử chương trình 
29 
IV. Bài tập tự giải 
Bài toán 1: Dãy con có tổng bằng S 
Cho N số nguyên dương tạo thành dãy A={A1,,AN}. Tìm một dãy con của A 
có tổng các phần tử bằng S. 
Dữ liệu vào từ file DAYCON.INP 
Dòng đầu tiên ghi hai số nguyên dương N (0≤N≤200) và S (0≤S≤40000) 
Các dòng tiếp theo lần lượt ghi N số hạng của dãy A (0≤Ai≤200) 
Kết quả ra ghi ra file DAYCON.OUT 
Nếu bài toán vô nghiệm ghi số 0. 
Nếu bài toán có nghiệm thì trên dòng thứ nhất ghi số 1. Các dòng tiếp theo, mỗi 
dòng ghi hai số là chỉ số trong dãy A và giá trị của một phần tử được chọn. 
Bài toán 2: Dãy con có tổng lớn nhất 
Cho dãy n số nguyên dương a1, a2, , an. Một dãy con của dãy nói trên là dãy 
được lập từ dãy đã cho bằng cách bỏ đi một số số hạng của dãy và giữ nguyên trật tự 
các số còn lại. Hãy tìm một dãy con thoả mãn tính chất: 
 Không có ba số liên tiếp nào của dãy ban đầu có mặt trong dãy con 
 Trong ba số liên tiếp của dãy ban đầu có ít nhất một số có mặt trong dãy con 
 Tổng các số hạng của dãy con được chọn là lớn nhất có thể được. 
Dữ liệu: Vào từ file CHONSO.INP: 
 Dòng đầu tiên chứa số nguyên dương N (N≤1000) 
 N dòng tiếp theo, dòng thứ i chứa số nguyên dương ai (ai≤30000) 
Kết quả: Ghi ra file văn bản CHONSO.OUT: 
 Dòng đầu tiên chứa hai số nguyên dương M và T trong đó M là số lượng các số 
hạng của dãy con được chọn, T là tổng các số của dãy chon được chọn. 
 M dòng tiếp theo lần lợt mô tả các số hạng của dãy con được chọn, dòng thứ k 
ghi số jk là chỉ só của số hạng được chọn thứ k. 
Ví dụ: 
CHONSO.INP CHONSO.OUT 
6 
2 
21 4 
2 
30 
6 
5 
1 
7 
3 
3 
5 
6 
Bài toán 3: Chia kẹo 
Có N gói kẹo, gói thứ i có A[i] cái kẹo. 
Yêu cầu: Hãy tìm cách chia các gói kẹo này thành 2 phần sao cho độ chênh lệch 
giữa số kẹo ở hai phần là ít nhất có thể được. 0<A[i]<10000, 2N1000 
Dữ liệu vào: Cho trong file CANDY.INP: Gồm N dòng, dòng thứ i chứa số nguyên 
A[i] là số kẹo trong gói thứ i 
Kết quả: Ghi ra file CANDY.OUT: 
 Dòng đầu tiên ghi 3 số: Tổng số kẹo ở phần 1, phần 2 và độ chênh lệch giữa hai 
phần 
 Dòng 2, 3 là số hiệu các gói kẹo ở mỗi phần được chia. 
Ví dụ: 
CANDY.INP CANDY.OUT 
3 
4 
7 
12 
14 12 2 
3 4 7 
12 
VIII. Những thông tin cần bảo mật: Không 
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. 
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ả: 
 Học sinh được học theo nội dung trình bày trong sáng kiến sẽ có cái nhìn toàn 
diện hơn, tự tin hơn khi đối mặt với bài toán trong Tin học từ đó các em sẽ thích học và 
chủ động tìm hiểu kiến thức. Nội dung sáng kiến được trình bày logic, phù hợp với 
trình độ phát triển tư duy của học sinh từ nhận biết, thông hiểu đến vận dụng, nâng cao 
và sáng tạo qua đó giúp cho học sinh phát triển tư duy tổng hợp và rèn luyện các kĩ 
năng viết chương trình sử dụng phương pháp quy hoạch động. 
31 
 Bảng số liệu kết quả của học sinh đội tuyển Tin trường THPT Nguyễn Viết Xuân 
năm học 2017 – 2018 khi chưa thực hiện đề tài: 
STT Khối Số lượng hs 
Số học sinh đạt giải 
Nhất Nhì Ba KK 
1 10 5 0 0 0 2 
2 11 3 0 0 1 1 
3 12 1 0 0 1 0 
- Một số học sinh có tiến bộ rõ rệt khi tiếp cận các bài toán sử dụng phương pháp QHĐ. 
- Nâng cao việc yêu thích học Tin học đối với một bộ phận học sinh và một số em có 
định hướng nghề nghiệp sau này. 
- Bảng số liệu kết quả đạt được của học sinh đội tuyển Tin học – trường THPT Nguyễn 
Viết Xuân năm học 2018 – 2019 sau khi thực hiện đề tài: 
STT Khối Số lượng hs 
Số học sinh đạt giải 
Nhất Nhì Ba KK 
1 10 5 0 1 2 1 
2 11 4 0 1 2 0 
3 12 4 0 1 2 1 
 Bản thân tôi khi viết đề tài này đã phần nào đó rèn luyện cho mình khả năng 
nghiên cứu khoa học, tìm tòi và phân tích và tổng hợp tài liệu từ nhiều nguồn khác 
nhau, tăng cường khả năng tự học, tự bồi dưỡng chuyên môn. 
 Sáng kiến kinh nghiệm sẽ là tài liệu tham khảo cơ bản về phương pháp quy hoạch 
động để trao đổi kinh nghiệm với đồng nghiệp và truyền đạt cho học sinh. 
 Mặc dù đã cố gắng rất nhiều trong quá trình viết sáng kiến kinh nghiệm này 
nhưng do thời gian có hạn nên chắc chắn sẽ không tránh khỏi những sai sót. Kính mong 
quý thầy cô, đồng nghiệp và học sinh chân thành góp ý để sáng kiến kinh nghiệm: 
“Giúp học sinh tiếp cận với thuật toán quy hoạch động bằng một số bài toán đơn giải 
trong Tin học” được hoàn thiện hơn và trở thành một tài liệu hay, hữu ích trong việc 
dạy và học lập trình. 
32 
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: 
STT Tên tổ chức/cá nhân Địa chỉ 
Phạm vi/Lĩnh vực 
áp dụng sáng kiến 
1 Nguyễn Thị Hà 
Trường THPT Nguyễn 
Viết Xuân 
Học sinh đội tuyển Tin 
học khối 10, 11, 12 
Vĩnh Tường, 
Ngày 12 tháng 02 năm 2020 
Thủ trưởng đơn vị/ 
Chính quyền địa phương 
(Ký tên, đóng dấu) 
Vĩnh Tường, 
ngày 14 tháng 02 năm 2020 
CHỦ TỊCH HỘI ĐỒNG 
SÁNG KIẾN CẤP CƠ SỞ 
(Ký tên, đóng dấu) 
Vĩnh Tường, 
ngày 10 tháng 02 năm 2020 
Tác giả sáng kiến 
(Ký, ghi rõ họ tên) 
Nguyễn Thị Hà 
33 
TÀI LIỆU THAM KHẢO 
[1]. Hồ Sĩ Đàm (chủ biên), Đỗ Đức Đông, Lê Minh Hoàng, Nguyễn Thanh Hùng 
(2009), Tài liệu giáo khoa chuyên tin, NXB Giáo dục. 
[2]. Robert Sedgewich – Người dịch: Trần Đan Thư, Vũ Mạnh Tưởng, Dương Vũ Diệu 
Trà, Nguyễn Tiến Huy (In lần thứ 5), Cẩm nang thuật toán, NXB Khoa học và kỹ thuật 
[3]. Lê Minh Hoàng, Bài giảng chuyên đề Giải thuật và lập trình, NXB Đại học sư 
phạm Hà Nội, 1999 – 2002. 
[4]. Trần Lê Hồng Dũ, Phạm Ngọc Chí Nhân – Trường THPT Bến Tre, Các bài toán 
về quy hoạch động. 
[5]. Nguyễn Hưu Điển, Một số vấn đề về thuật toán, NXB Giáo dục 
[6]. Nguyễn Chí Trung, Giáo trình thuật toán và kỹ thuật lập trình Pascal – NXB Sở 
giáo dục và đào tạo Hà Nội.