SKKN:Sử dụng phương pháp quy hoạch động để giải một số bài toán nhằm bồi
dưỡng học sinh giỏi tin học 11.
I. MỞ ĐẦU
I.1.1/ LÝ DO CHỌN ĐỀ TÀI
- Ngày nay cùng với sự phát triển của đất nước, công nghệ thông tin đang đóng một vai
trò hết sức quan trọng, tác động đến hầu hết các lĩnh vực của đời sống xã hội. Việc đào
tạo một thế hệ tương lai có một sự phát triển toàn diện đòi hỏi ngành giáo dục luôn phải
có sự quan tâm đúng mức là điều rất cần thiết để có một nguồn nhân lực đáp ứng yêu
cầu CNH, HĐH mở cửa và hội nhập hướng tới nền kinh tế tri thức của nước ta nói riêng
và thế giới chung.
- Tin học là một môn học mới, việc truyền đạt kiến thức cơ bản trong sách giáo khoa đã
là khó khăn, làm sao để dạy học bồi dưỡng học sinh khá giỏi. Giúp các em không chỉ
nắm được những kiến thức cơ bản mà còn hiểu và giải quyết được những bài toán đòi
hỏi những thuật toán phức tạp hơn: Hoán vị, tổ hợp,tham lam,chia để trị,..đó là việc
khiến các giáo viên phải luôn luôn trăn trở và tìm những phương pháp phù hợp.
- Một thuật toán chỉ giải được một bài toán, nhưng một bài toán lại có thể có rất nhiều
thuật toán khác nhau. Làm thế nào để tìm ra thuật toán phù hợp, nhanh gọn, dễ hiểu, tốn
ít dung lượng bộ nhớ. Phương pháp quy hoạch động là một phương pháp hay, có nhiều
ưu điểm nhưng cũng có nhược điểm đó là khó tìm được công thức truy hồi. Ngoài ra
kiến thức mới cũng làm học sinh khó hấp thụ. Cách giải những bài toán phức tạp nhưng
dùng những kiến thức cũ đôi khi giúp học sinh dễ hiểu hơn. Từ những lí do trên tôi đã
quyết định chọn đề tài “sử dụng phương pháp quy hoạch động để giải một số bài toán
nhằm bồi dưỡng học sinh giỏi tin học 11”
I.1.2/ MỤC ĐÍCH NGHIÊN CỨU ĐỀ TÀI
- Mục tiêu chính của đề tài là nghiên cứu về pháp Quy Hoạch Động để giải một số bài
toán nhằm bồi dưỡng học sinh giỏi tin học 11.
- Giúp cho việc ôn thi học sinh giỏi tin học thi đạt kết quả ngày càng cao.
- Tạo ra nguồn tài liệu tham khảo về phương pháp cũng như thuật toán nhằm hỗ trợ cho
học sinh, giáo viên dạy bồi dưỡng học sinh giỏi tin học 11.
I.1.3/ ĐỐI TƯỢNG NGHIÊN CỨU VÀ PHẠM VI NGHIÊN CỨU
* ĐỐI TƯỢNG NGHIÊN CỨU

động mới. Học sinh sẽ thấy rõ hiệu quả mạnh mẽ của công nghệ thông tin và nhận thức
cần có.
II.2.2/ THỰC TRẠNG VẤN ĐỀ CỦA SÁNG KIẾN KINH NGHIỆM
A*.Thực trạng chung:
Hiện nay nhu cầu xã hội đang rất cần những kĩ sư Công Nghệ Thông tin có trình
độ cao. Tuy nhiên việc đào tạo và bồi dưỡng học sinh yêu thích môn Tin học ở trường
Phổ thông hiện nay đang gặp rất nhiều khó khăn.
Tin học 11 là một môn học mới, để học tốt đượ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 tư duy và niềm đam mê, ngoài ra học sinh
phải có điều kiện thực hành thường xuyên.
Đa số các em học sinh tập trung học các môn khối để ôn thi THPT Quốc Gia nên
không dành được nhiều thời gian cho môn Tin học. Trường đã có máy tính để thực hành
nhưng số lượng ít chưa đủ để tất cả các tiết thực hành đều được đáp ứng. Tài liệu tham
khảo dành cho môn tin học chưa có nhiều nên việc tiếp cận với những kiến thức mới còn
gặp nhiều khó khăn. Đó là cũng thực trạng chung của hầu hết các trường phổ thông hiện
nay.
B* Một số thuận lợi và khó khăn khi thực hiện đề tài ở trường THPT Tĩnh Gia I.
1. Thuận lợi:
* Nhà trường:
Trường THPT Tĩnh Gia 1 là ngôi trường có truyền thống với bề dày 54 năm. Là
trường chuẩn quốc gia nên trường cũng là nơi có điều kiện cơ sở vật chất tương đối đảm
bảo đáp ứng cho điều kiện học tập. Nhà trường đã tạo điều kiện để học sinh có điều kiện
2


SKKN:Sử dụng phương pháp quy hoạch động để giải một số bài toán nhằm bồi
dưỡng học sinh giỏi tin học 11.
tốt nhất để học, tạo điều kiện về máy móc, trang thiết bị phục vụ cho việc dạy và học
môn Tin học.
* Học sinh:

Phương pháp quy hoạch động dùng để giải bài toán tối ưu có bản chất đệ quy, tức là để
tìm phương án tối ưu cho bài toán nào đó có thể đưa về tìm phương án tối ưu của một số
hữu hạn các bài toán con.
- Phương pháp quy hoạch động là một kỹ thuật nhằm đơn giản hoá 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 tại mỗi bước
trước đó với mục đích sử dụng lại.
3


SKKN:Sử dụng phương pháp quy hoạch động để giải một số bài toán nhằm bồi
dưỡng học sinh giỏi tin học 11.
Như vậy, Quy hoạch động = Chia để trị + Mảng (lưu lại kết quả).
- 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 này dung để giải các bài toán tối ưu có bản
chất đệ qui, tức là tìm phương pháp tối ưu cho bài toán đó có thể đưa về tìm phương án
tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài
toán.
- Điểm khác nhau cơ bản giữa quy hoạch động và phương pháp đệ quy là:
+ Phương pháp đệ quy giải quyết bài toán theo hướng TOP _ DOWN, nghĩa là để
giải bài toán ban đầu, ta phải đi giải tất cả các bài toán con của nó. Đây là một phương
pháp hay, tuy nhiên phương pháp này sẽ gặp hạn chế về mặt thời gian, tốc độ do phải
tính đi tính lại nhiều lần một số bài toán con giống nhau nào đó.
+ 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 sẽ 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 tới 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. Do đó tiết kiệm
được bộ nhớ và cải thiện được tốc độ.
+QHĐ có ưu điểm là chương trình thực hiện nhanh do không phải tốn nhiều thời gian
để giải lại các bài toán con đã được giải.


F(2) =1
F(2) = 1

F(2) =1

F(1) = 1

F(1) =1

Để tính được F(5) ta phải gọi F(4) và F(3), tính được F(4) phải gọi F(3) và F(2),
F(1) và F(2) đã cho từ ban đầu.
BẢNG GIÁ TRỊ CỦA FIBONACI
I

0

1

2

3

4

5

6

7


Chương trình minh họa
Function Fib(n:integer):longint;
Begin
IF n=0 THEN fib:=0 else
If n=1 then fib:=1 else
If n=2 then fib:=1
Else fib:=fib(n-1)+ fib(n-2);
End;
Begin
Readln(n);
Writeln(Fib(n));
End.
Cách 2: Phương pháp quy hoạch động
Ta sử dụng mảng S[0..MaxN], S[i] để lưu lại lời giải cho bài toán tính số Fibonacci thứ i
const
MaxN =
1000;
var
s: array[0..MaxN] of int64;
n, k: longint;
function
f(n:longint) :
int64;
Begin
if
s[n]=-1 then
5



i:
longint;
begin
readln(n);
s[0]:=0;
s[1]:=1;
for i:=2
to
n
s[i]
:=
s[i-1] + s[i-2];
Writeln(s[n]);
Readln;
End.

do

Trong cách giải thứ nhất để tìm ra số fibonaci thứ n ta phải tính tất cả các giá trị
trước đó. Tuy nhiên các giá trị tính toán trước đó không được lưu lại. Đối với cách giải
thứ 2 tất cả các giá trị được lưu trong mảng A nên khi cần sử dụng lại những giá trị
trước đó máy tính sẽ không phải tính lại. Để thấy rõ hơn ưu nhược điểm của 2 cách ta
xét ví dụ 2.
Ví dụ 2: Tính tổng 2 số fibonaci thứ n và thứ (n -2).
- Nếu dùng cách giải chia để trị ta có thể tính tổng rất nhanh bằng cách gọi 1 lời gọi
trong chương trình chính:
Tong:=fib(n)+ fib(n-2);
Tuy nhiên với lời gọi trên thì máy tính sẽ phải tính n + (n-2)=2n-2 phép toán.
Trong khi nếu dùng phương pháp quy hoạch động như trong cách 2 ví dụ 1
Ta chỉ cần tính: Tong:=a[n]+a[n-2];

Biết rằng:
C =C

=1
k

+ C n −1

Ý tưởng bài toán:
Bài toán trên cho ta gợi ý về thuật toán đệ quy như sau.
Function C(n,k:Longint):longint;
Begin
If (k=0) or (n=0) then c:=1 else C:=C(n-1,k-1) + C(n-1,k);
End;
Gọi T là thời gian để tính số tổ hợp chập k của n thì ta có phương trình đệ quy như
sau
T(1) =C1 và T(n)=2T(n-1) + C2.
Giải phương trình này ta được T(n) = O(2n) Như vậy là một giải thuật thời gian mũ,
Trong khi chỉ có một đa thức các bài toán con. Điều đó chứng tỏ rằng có những bài
toán con được giải nhiều lần.
Chẳng hặn như tính C(4,2) thì ta phải tính C(3,1) và C(3,2). Tính C(3,1) thì phải tính
C(2,0) và C(2,1). Tính C(3,2) thì phải tính C(2,1) và C(2,2). Như vậy để tính C(4,2)
thì phải tính C(2,1) 2 lần.
Hình minh họa
C(4,2)

C(3,1)
C(3,2)

C(2,0)

3

0

1

1

1

1

2

1

2

2

3

1

3

3

1


begin
Writeln('nhap n,k:'); readln(n,k);
Writeln(tohop(n,k));
readln;
end.
n

Nếu gọi T là thời gian thực hiện giải thuật thì ta có T(n)=

∑ (i − 1) =
i =1

n(n − 1)
= O(n2).
2

Từ đó ta thấy sử dụng thuật toán quy hoạch động hiệu quả hơn nhiều so với thuật toán
đệ quy.
Ví dụ 4: 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à W i ≤ 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
8


SKKN:Sử dụng phương pháp quy hoạch động để giải một số bài toán nhằm bồi
dưỡng học sinh giỏi tin học 11.
đượ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.
Input: File văn bản Tui.inp
+ Dòng 1:chứa 2 số n ,M cách nhau ít nhất 1 dấu cách.

2
3
4
5
6
7
8
9
10 11 12 13 14 15
M
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0

6
3
0
1
2
3
3
3
3
3
3
3
3
3
4
5
6
7
4
0
2
3
4
5
5
5
5
5
5
5

begin
assign(f1,'tui.inp'); reset(f1);
read(f1,n,M);
for i := 1 to n do
readln(f1,W[i],V[i]);
close(f1);
end;
procedure
tinh;
var
i, j: Integer;
begin
FillChar(B[0], SizeOf(B[0]), 0);
for i := 1 to n do
for j := 0 to M do
begin
B[i, j] := B[i - 1, j];
if (j >= W[i]) and (B[i, j] < B[i - 1, j - W[i]] + V[i])
then
B[i, j] := B[i - 1, j - W[i]] + V[i];
end;
end;
procedure Truy_timnghiem;
begin
writeln('gia tri max la:',B[n,M]);
while n 0 do
begin
if B[n, M] B[n - 1, M] then
begin
writeln('goi thu',n,'w=',w[n],'v=',v[n]);

+ Nếu không chọn gói thứ i thì A[i,j] là giá trị lớn nhất có thể bằng cách chọn
trong số các gói {1,2,…,i-1} với giới hạn trọng lượng là j tức là A[i,j] = A[i-1,j].
+ Nếu có chọn gói thứ i (khi Wi ≤j) thì A[i,j]=bi + A[i-1, j- Wi]
Ban đầu
A[0,i] = 0 với i
A[0,i] = 0 với mọi i.
Sau đó A[i,j] sẽ tính theo A[i-1,j] hoặc A[i-1,j-Wi].
Chương trình minh họa
uses crt;
var A:array[0..1000,0..1000] of longint;
W,b:array[1..1000] of longint;
N,M,i,j:longint;
f1,f2:text;
11


SKKN:Sử dụng phương pháp quy hoạch động để giải một số bài toán nhằm bồi
dưỡng học sinh giỏi tin học 11.
begin
clrscr;
assign(f1,'balo.inp'); assign(f2,'balo.out'); reset(f1); rewrite(f2);
readln(f1,N,M);
for i:=1 to N do read(f1,W[i]);
for i:=1 to N do read(f1,b[i]);
for i:=1 to N do A[i,0]:=0;
for i:=1 to M do A[0,i]:=0;
for j:=1 to M do
for i:=1 to N do
Begin
if (j-W[i]>=0) and (b[i]+A[i-1,j-W[i]]>A[i-1,j]) then A[i,j]:=b[i]+A[i-1,j-W[i]];

b1…bn

(với i0) and ai=bj ta có L(i,j) = 1 + L(i-1, j-1)
Phương pháp: Dùng bảng để lưu kết quả của các bài toán con mỗi lần cần đến ta
chỉ truy xuất trong bảng.Nếu ta viết một hàm tính độ dài theo hàm như sau:
Function L(I,j: longint):longint;
Begin
If (i=0) or (j=0) then L:=0
Else

if a[i]=b[j] then L:=1 + L(i-1, j-1)

Else L:= max(L(i-1,j),L(i,j-1));
End;
Tuy đoạn chương trình trên vẫn cho kết quả đúng nhưng về thời gian vẫn bị chậm
lại rất nhiều lại rất nhiều do tính lại nhiều lần kết quả bài toán con nào đó và đồng
thời làm cho chương trình dể bị tràn stack. Để khắc phục hạn chế đó ta dung mảng
để lưu lại kết quả các bài toán con. Xuất phát từ trường hợp đơn giản nhất có thể
tìm nghiệm. Kết hợp các nghiệm đã có ta sẽ nhận được nghiệm của bài toán cở lớn
hơn. Tiếp tục như thế cho tới khi tìm ra nghiệm của bài toán.
Ta chỉ cần duyệt qua một lần như sau để lập bảng.
For i:=1 to length(a) do
For j:=1 to length(b) do
If a[i] = b[j] then
L[i,j] := 1+ L[i-1,j-1]


5

6

0

0

0

0

0

0

0

0

1

0

0

0

1


1

2

2

3

4

0

1

1

2

2

3

3

5

0

1


1

2

3

3

4

4

Xét theo bảng trên thì mỗi lần đi theo thì ta đã chọn được các ô khi a i = bj ( các ô đậm)
khi đó ta được kết quả: c= (AEEC).
Chương trình minh họa
program xauconchung;
uses crt;
var L:array[0..1000,0..1000] of int64;
s1,s2,s3:ansistring;
f:text;
m,n,i,j:longint;
function max(var a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;
begin
clrscr;
assign(f, 'Xau.inp'); reset(f);
readln(f,s1);

end.
Qua thực hiện chương trình cho ta thấy dung quy hoạch động đã khắc phục được
nhiều khuyết điểm về mặt thời gian
Ví dụ 6: Bài toán Dãy con chung dài nhất
- Cho hai số nguyên dương M,N (0
giải quyết các bài toán khó;
Trong quá trình thực hành và làm bài tập cũng tạo cho học sinh tinh thần trách
nhiệm, nhận thức đúng đắn về môn học, khơi dậy lòng say mê môn học và tạo hứng thú
học tập cho học sinh.
16


SKKN:Sử dụng phương pháp quy hoạch động để giải một số bài toán nhằm bồi
dưỡng học sinh giỏi tin học 11.
- Mối quan hệ qua lại giữa các cách giải 1 bài toán sẽ làm học sinh linh hoạt hơn
trong việc lựa trọn thuật toán từ đó có thể lựa chọn thuật toán phù hợp để viết chương
trình
Thông qua các tiết bài tập và thực hành cũng giúp cho giáo viên nắm bắt được
những nhược điểm của học sinh hay mắc phải, những phần kiến thức học sinh thường
nhầm lẫn để củng cố, sửa đổi, bổ sung kịp thời cho các em giúp các em hiểu rõ từng vấn
đề đang vướng mắc trong quá trình thực hiện và học tập.
II/ Ý KIẾN ĐỀ XUẤT.
Để nâng cao chất lượng dạy – học môn tin học, và tạo hứng thú cho các em có
niềm đam mê tin học ngay từ khi đang còn ngồi trên ghế nhà trường rất mong của nhà
trường cùng các ngành có liên quan giúp đỡ về cơ sở vật chất.
Số lượng sách tham khảo môn tin trong nhà trường còn rất hạn chế. Kính mong
được nhà trường và thư viện quan tâm tạo điều kiện bổ sung thêm tài liệu cho học sinh
và giáo viên có điều kiện tiếp cận thêm với tri thức mới.
Trên đây là một số ví dụ tôi đã sử dụng phương pháp QHĐ vào dạy học bồi
dưỡng học sinh giỏi môn tin học 11. Tuy nhiên còn nhiều mặt hạn chế. Rất mong được
sự đóng góp ý kiến của đồng nghiệp để SKKN của tôi có hiệu quả hơn. Đồng thời tôi
mong rằng với chút ít kinh nghiệm của mình có thể góp phần nâng cao chất lượng bộ
môn. Tôi xin chân thành cảm ơn!
XÁC NHẬN CỦA THỦ TRƯỞNG Tĩnh gia, ngày 19 tháng 05 năm 2016
ĐƠN VỊ