SỞ GD & ĐT THANH HÓA
TRƯỜNG THPT YÊN ĐỊNH 2

SÁNG KIẾN KINH NGHIỆM
Tên đề tài:
PHÁT TRIỂN TƯ DUY THUẬT TOÁN
QUA MỘT SỐ BÀI TOÁN LẬP TRÌNH.
Họ và tên: Lương Trung Dũng
Chức vụ: TTCM
Đơn vị công tác: Trường THPT Yên Định 2
SKKN thuộc môn: Tin học
THANH HOÁ, NĂM 2013
A. ĐẶT VẤN ĐỀ
I. CƠ SỞ LÝ LUẬN
Trong các bài toán có những lúc chúng ta tỏ ra bế tắc trước những hướng
đi để tìm lời giải cho bài toán, vấn đề tìm ra một hướng đi đúng đắn cho bài toán
thực sự là một vấn đề khó đối với học sinh nói chung và đối với học sinh học
môn tin học THPT nói riêng. Khi đứng trước một bài toán lạ, không chỉ học sinh
thường tỏ ra lúng túng, mà đối với các giáo viên cũng tỏ ra rất lúng túng không
biết lựa chọn phương pháp nào để đưa ra lời giải cho bài toán. Có nhiều lúc
những bài toán hết sức đơn giản nhưng chúng ta chưa khôn khéo đưa bài toán đó
về dạng quen thuộc để giải bài toán, cuối cùng dẫn tới con đường bế tắc không
tìm ra được lời giải hay thuật toán đúng đắn. Nhìn chung chính học sinh và cả
chúng ta nữa, chúng ta chưa có phương pháp đúng để đưa một bài toán đó từ bài
toán mà chúng ta chưa hề hay biết về bài toán chúng ta đã biết. Với những bài
toán ta luôn hướng tới sự hoàn thiện tư duy và phát triển khả năng thuật toán cho
học sinh. Đặc biệt đối với học sinh khá giỏi ta cần phát triển sự tư duy cho học
sinh để các em có thể phát triển khả năng thuật toán và kỷ thuật lập trình. Chính
vỳ lý do đó mà tôi chọn đề tài “Phát triển tư duy thuật toán qua một số bài
toán lập trình” nhằm xây dựng cho các em kỷ năng tư duy và phát triển tốt
nhất.

4
3 8 5 4
3 4 5 8
Cơ sở sắp xếp: Với dãy N phần tử ta có thể có nhiều cách để xếp. Thuật
toán tráo đổi dễ hiểu đối với học sinh tuy nhiên chưa tối ưu. Ta có thể sử dụng
thuật toán Quicksort để tăng hiệu quả sắp xếp lên nhiều và ta kết hợp sử dụng
nó bằng đề qui.
Đây là một bài toán quen thuộc đối với học sinh trong khi giải bài toán
tìm kiếm. Ta có thể nâng lên sắp xếp chỉ mục để tăng khả năng xắp sếp cho mục
tin lớn
Chúng ta vận dụng bài toán này để giải các bài toán sau:
Bài toán 2: Dãy FAREY.
Ứng với số tự nhiên N>0, ta có dãy Farey gồm các phân số tối giản có giá
trị lớn hơn 0 và nhỏ hơn 1 theo thứ tự tăng dần.
Ví dụ: Với N=4 ta có dãy phân số
1 1 1 2 3
; ; ; ;
4 3 2 3 4
Yêu cầu: Cho số tự nhiên N (0<N<100). Hãy tìm dãy Farey tương ứng.
Dữ liệu: Vào từ file văn bản FAREY.INP chứa duy nhất số N.
Kết quả: Ghi ra File văn bản FAREY.OUT gồm:
• Dòng đầu tiên ghi các tử số của dãy số.
• Dòng tiếp theo ghi các mẫu số của dãy số.
Ví dụ:
FAREY.INP FAREY.OUT
5 1 1 1 2 1 3 2 3 4
5 4 3 5 2 5 3 4 5
Bài toán 3: BĂNG NHẠC.
Người ta cần ghi N bài hát, được mã số từ 1 đến N, vào một băng nhạc có
thời lượng tính theo phút đủ chứa toàn bộ các bài đã cho. Với mỗi bài hát ta biết

Tìm và phát bài 3 cần 5 phút
Tìm và phát bài 1 cần 12 phút
Tổng thời gian phát mỗi bài 1 lần : 19 phút
Bài toán 4: CHỌN VIỆC.
Có N công việc cần thực hiện trên một máy tính, mỗi việc đòi hỏi 1 giời
thực hiện trên máy tính. Với mỗi việc ta biết thời hạn phải nộp kết quả thực hiện
sau khi hoàn thành việc đó và tiền thưởng thu được nếu nộp kết quả trước hoặc
đúng thời điểm quy định. Chỉ có một máy tính trong tay, hãy lập lịch thực hiện
đủ N công việc trên máy tính sao cho tổng số tiền thưởng thu được là lớn nhất và
thời gian hoạt động của máy là nhỏ nhất. Giả thiết rằng máy được khởi động vào
đầu ca, thời điểm t = 0 và chỉ tắt máy sau khi đã hoàn thành đủ N công việc.
Dữ liệu : Vào từ tệp VIEC.INP
- Dòng đầu ghi số N
- N dòng tiếp theo gồm 2 số t và th, t là thời hạn nộp, th là mức thưởng.
Kết quả : Ghi ra tệp VIEC.OUT
- i dòng đầu ghi thời gian việc i được làm.
- Dòng cuối ghi tổng tiền thưởng thu được.
4
Ví dụ
Ý nghĩa : Cho biết 4 việc
- Việc thứ nhất nộp không muộn hơn 1 giờ thưởng 15 ngàn
- Việc thứ hai nộp không muộn hơn 3 giờ thưởng 10 ngàn
- Việc thứ ba nộp không muộn hơn 5 giờ thưởng 100 ngàn
- Việc thứ tư nộp không muộn hơn 1 giờ thưởng 27 ngàn
Ý nghĩa :
- Giờ thứ 1 thực hiện công việc 4 nộp đúng hạn nên được thưởng 27
ngàn.
- Giờ thứ 2 thực hiện công việc 2 nộp đúng hạn nên được thưởng 10
ngàn.
- Giờ thứ 3 thực hiện công việc 3 nộp đúng hạn nên được thưởng 100

VIEC.OUT
4
2
3
1
137
B. GIẢI QUYẾT VẤN ĐỀ.
I. PHÂN TÍCH BÀI TOÁN
Bài toán cơ bản: Cho dãy gồm N phần tử a
1
, a
2
, a
n
. Sắp xếp dãy theo trật
tự không giảm (hoặc không giảm).
Phân tích: Dựa trên cơ sở sắp xếp đã học cơ bản ta dễ dàng giải được bài
toán này bằng cách tráo đổi vị trí các phần tử, tìm phần tử nhỏ nhấp đưa về đầu,
loại bỏ phần tử đó khỏi dãy, tìm tiếp phần tử nhỏ nhất trong dãy còn lại đưa về
đầu, lặp lại công việc cho tới khi dãy chỉ còn 1 phần tử.
Sử dụng phương pháp “chia để trị”. Thực hiện bằng cách phân hoạch dãy
thành 2 phần, sau đó sắp xếp trên từng phần riêng biệt lấy vị trí giữa làm khóa
để chia, ta chọn được một nửa là các phần tử nhỏ hơn khóa, nửa còn lại là các
phần tử lớn hơn khóa. Thực hiện lặp lại như vậy trên các dãy con.
Để sử dụng thuật toán quicksort ở đây ta dùng đệ quy để thực hiện sắp
xếp. Đối với ngôn ngữ Pascal thì Free Pascal đã làm tăng khả năng rất nhiều.
Thuật toán: Ta sử dụng thuật toán tráo đổi và Quicksort; so sánh sắp xếp
trên khoá và sắp xếp theo theo chỉ mục.
- Mảng a lưu tất cả các phần tử từ a
1

Procedure quicksort(d,c:integer);
Var i,j,tg,m:integer;
Begin
I:=d; j:=c; M:= a[(i+j) div 2];
While i<=j do
Begin
While a[i]<m do inc(i);
While a[j]>m do dec(j);
If i<=j then
Begin
Tg:=a[i];A[i]:=a[j];A[j]:=tg;
Inc(i); dec(j);
End;
End;
If d<j then quicksort(d,j);
If c>i then quicksort(i,c);
End;
Sau khi giới thiệu thuật toán Quicksort học sinh đã năm được cách thức
sử dụng thuật toán. Ta hướng tới việc dùng chỉ mục để sắp xếp mảng. ở đây ta
sử dụng mảng b để lưu vị trí (chỉ số) của phần tử trong mảng a. Ta tiến hành cài
đặt thuật toán như sau:
Sắp xếp chỉ mục bằng Quicksort:
Ta khởi tạo chỉ mục cho mảng b là vị trí của chính nó ban đầu của mảng
a. Dùng thủ tục Procedure Init;
Var a:array[1 1000] of integer;
b:array[1.1000] of word;
N:integer;
Procedure Init;
Var i:word;
Begin

Begin
Read(f,a[i]); b[i]:=i;
End;
Close(f);
End;
Procedure ghikq;
Var i:word;
Begin
Assign(f,’Sapxep.out’); Rewrite(f);
For i:=1 to n do write(f,a[b[i]],’ ’);
Close(f);
End;
8
Procedure quicksort(d,c:integer);
Var i,j,tg,m:integer;
Begin
I:=d; j:=c; M:= a[b[(i+j) div 2]];
While i<=j do
Begin
While a[b[i]]<m do inc(i);
While a[b[j]]>m do dec(j);
If i<=j then
Begin
Tg:=b[i];b[i]:=b[j];b[j]:=tg;
Inc(i);dec(j);
End;
End;
If d<j then quicksort(d,j);
If c>i then quicksort(i,c);
End;

• Dòng tiếp theo ghi các mẫu số của dãy số.
Ví dụ:
FAREY.INP FAREY.OUT
5 1 1 1 2 1 3 2 3 4
5 4 3 5 2 5 3 4 5
Phân tích: Khi định hình nhìn vào bài toán, mới nhìn ta thực sự thấy bài
toán này chưa thể dùng 1 mảng 1 chiều để sắp xếp nó. Nhưng ta hãy nghiên cứu
kỷ một chút trong bài toán và có thể rút ra nhận xét quan trọng cho bài toán từ
đó chúng ta có thể nhìn thấy bài toán trở nên quen thuộc hơn.
- Xét một phần tử của dãy ta thấy phần tử của dãy gồm phức hợp 3 giá trị:
tử số, mẫu số và thương của tử và mẫu. Vậy ta có thể tổ chức kiểu bản ghi để
cho phần tử đó trên cơ sở này ta có thể tạo mảng 1 chiều kiểu bản ghi để lưu các
giá trị, sau đó sắp xếp mảng này theo trật tự không giảm.
- Các tử số của phần tử i sẽ nhận giá trị từ 1 đến N-1; Các giá trị của mẫu
sẽ nhận các giá trị từ i+1 đến N (vì tử số phải nhỏ hơn mẫu số).
- Các phân số có thể chưa tối giản, ta phải thực hiện tối giản cho phân số
ở mỗi phần tử.
- Sau khi tối giản có thể một số phần tử trong mảng sẽ bị trùng nhau. Ta
thực hiện lấy 1 phần tử trong các phần tử trùng, các phần tử còn lại ta sẽ loại bỏ.
Kết quả thu được sẽ là dãy Farey.
Thuật toán:
- Mảng a chứa toàn bộ các phần tử tạo ra từ giá trị N thoả mãn nằm trong
khoảng (0,1). Biến k sẽ lưu số lượng phần tử mảng a được sinh ra.
- Mảng b lưu chỉ số của các phần tử.
- Thủ tục Procedure Init để khởi tạo và sinh mảng a thoả mãn nằm trong
khoảng (0,1)
10
- Hàm Function UCLN(a,b:word); để tìm UCLN của tử số và mẫu số của mỗi
phần tử i trong mảng a.
- Thủ tục Procedure Toigian; dùng để tối giản các phân số, trong đó cần sử

Function UCLN(a,b:word):word;
Begin
While a<>b do
If a>b then a:=a-b Else b:=b-a;
11
UCLN:=a;
End;
Procedure Toigian;
Var i:word;
Begin
For i:=1 to k do
Begin
A[i].t:=a[i].t div UCLN(a[i].t,a[i].m);
A[i].m:=a[i].m div UCLN(a[i].t,a[i].m);
End;
Procedure quicksort(d,c:integer);
Var i,j,tg,m:integer;
Begin
I:=d; j:=c; M:= a[b[(i+j) div 2]].th;
While i<=j do
Begin
While a[b[i]].th<m do inc(i);
While a[b[j]].th>m do dec(j);
If i<=j then
Begin
Tg:=b[i];b[i]:=b[j];b[j]:=tg;
Inc(i);dec(j);
End;
End;
If d<j then quicksort(d,j);

- Việc sắp xếp bài toán mang lại phương án tìm ra kết quả dễ dàng.
Bài toán 2: BĂNG NHẠC.
Người ta cần ghi N bài hát, được mã số từ 1 đến N, vào một băng nhạc có
thời lượng tính theo phút đủ chứa toàn bộ các bài đã cho. Với mỗi bài hát ta biết
thời lượng phát của bài đó. Băng sẽ được lắp vào một máy phát nhạc đặt trong
một siêu thị. Khách hàng muốn nghe bài hát bào chỉ việc nhấn phím ứng với bài
đó. Để tìm và phát bài thứ i trên băng, máy xuất phát từ đầu cuộn băng, quay
băng để bỏ đi i-1 bài ghi trước bài đó. Thời gian quay băng bỏ qua mỗi bài và
thời gian phát bài đó được tính là như nhau. Tính trung bình, các bài hát trong
một ngày được khách hàng lựa chọn với số lần như nhau. Hãy tìm cách ghi các
bài hát trên băng sao cho tổng thời gian quay băng trong mỗi ngày là ít nhất.
Dữ liệu : Vào từ file BANGNHAC.INP
- Dòng đầu ghi số N.
- Dòng tiếp theo ghi thời lượng các bài hát tương ứng mỗi số cách nhau 1 dấu
cách.
Kết quả : Ghi ra tệp BANGNHAC.OUT
- Các dòng trên ghi 2 số j và d là mã số bài hát và thời gian tìm phát bài.
- Dòng cuối ghi tổng thời gian quay băng nếu mối bài phát một lần.
Ví dụ :
13
BANGNHAC.INP BANGNHAC.OUT
3
7 2 3
2 2
3 5
1 12
19
BANGNHAC.INP : 3 bài
Bài 1 : phát 7 phút
Bài 2 : phát 2 phút

- Thủ tục Procedure Quicksort sắp xếp dữ liệu mảng theo chỉ mục.
- Thủ tục Procedure ghikq; Thực hiện tính thời gian tổng và ghi kết quả.
Toàn văn chương trình:
14
Var a,b:array[1 200] of integer;
F:text; N:integer;
Procedure Init;
Var i,j:word;
Begin
Assign(f,’Bangnhac.inp’);Reset(f);Readln(f,N);
For i:=1 to n do
Begin
Read(f,a[i]);b[i]:=i;
End;
Close(f);
End;
Procedure ghikq;
Var i,t,tg:word;
Begin
Assign(f,’Bangnhac.out’); Rewrite(f);
T:=0; tg:=0;
For i:=1 to n do
Begin
T:=t+a[b[i]]; tg:=tg+t;
writeln(f,b[i],’ ’,t);
End;
Write(f,tg); Close(f);
End;
Procedure quicksort(d,c:integer);
Var i,j,tg,m:integer;

Có N công việc cần thực hiện trên một máy tính, mỗi việc đòi hỏi 1 giời
thực hiện trên máy tính. Với mỗi việc ta biết thời hạn phải nộp kết quả thực hiện
sau khi hoàn thành việc đó và tiền thưởng thu được nếu nộp kết quả trước hoặc
đúng thời điểm quy định. Chỉ có một máy tính trong tay, hãy lập lịch thực hiện
đủ N công việc trên máy tính sao cho tổng số tiền thưởng thu được là lớn nhất
và thời gian hoạt động của máy là nhỏ nhất. Giả thiết rằng máy được khởi động
vào đầu ca, thời điểm t=0 và chỉ tắt máy sau khi đã hoàn thành đủ N công việc.
Dữ liệu : Vào từ tệp VIEC.INP
- Dòng đầu ghi số N
- N dòng tiếp theo gồm 2 số t và th, t là thời hạn nộp, th là mức thưởng.
Kết quả : Ghi ra tệp VIEC.OUT
- i dòng đầu ghi thời gian việc i được làm.
- Dòng cuối ghi tổng tiền thưởng thu được.
Ví dụ
Ý nghĩa : Cho biết 4 việc
- Việc thứ nhất nộp không muộn hơn 1 giờ thưởng 15 ngàn
- Việc thứ hai nộp không muộn hơn 3 giờ thưởng 10 ngàn
- Việc thứ ba nộp không muộn hơn 5 giờ thưởng 100 ngàn
16
VIEC.INP
4
1 15
3 10
5 100
1 27
- Việc thứ tư nộp không muộn hơn 1 giờ thưởng 27 ngàn
Ý nghĩa :
- Giờ thứ 1 thực hiện công việc 4 nộp đúng hạn nên được thưởng 27
ngàn.
- Giờ thứ 2 thực hiện công việc 2 nộp đúng hạn nên được thưởng 10

17
VIEC.OUT
4
2
3
1
137
- Chỉ mục b[i]= v>0 cho biết v đứng thứ i trong dãy được sắp giảm theo giá trị
tiền thưởng và việc v chưa được xếp. B[i]=v<0 cho biết việc v đã xếp xong trong lần
duyệt đầu tiên.
Thuật toán :
- Các biến mảng a: tiền thưởng, t: thời gian giao nộp, b: chỉ mục, h: trục thời
gian ; các biến m: số việc đã xếp, tg: tổng số tiền thưởng.
- Thủ tục Procedure Init để khởi tạo các giá trị ban đầu và đọc dữ liệu đầu
vào.
- Thủ tục Procedure quicksort để sắp xếp mảng a theo chỉ mục dựa trên tiền
thưởng.
- Thủ tục Procedure xepviec để chọn và ưu tiên xếp các công việc thưởng cao
vào vị trí theo ý tưởng đã phân tích.
- Thủ tục Procedure donviec để dồn các việc đã xếp về đầu, vị trí trống sẽ thực
hiện xếp các công việc không có thưởng cho hoàn thành N công việc.
- Thủ tục Procedure xeptiep xếp các công việc còn lại cho hết và hoàn thành.
- Thủ tục Procedure Ghikq để ghi kết quả bài toán theo yêu cầu của bài toán
đặt ra.
Toàn văn chương trình :
Var a,b,t, h :array[1 200] of integer ;
m, n, tg :integer ;
Procedure Init;
Var i,j:word;
Begin

Begin
v:=b[i] ; {việc nào}
For k :=t[v] downto 1 do
If h[k]= 0 then
Begin
h[k] :=v ; b[i] :=-v ;
Break ;
End ;
End ;
End ;
Procedure Donviec ;
Var i :integer ;
Begin
tg :=0 ;
{Tìm giờ trống đầu tiên trong h}
For i :=1 to 200 do
If h[i]= 0 then
Begin
m :=i ; break ;
End ;
Else tg :=tg+a[h[i]] ;
If M>N then exit ;
For i :=m+1 to 200 do
If h[i]>0 then
Begin
h[m] :=h[i]; tg :=tg+a[h[i]] ;
Inc(m) ;
If m>n then exit ;
End ;
End ;

còn là đơn giản.
- Để đánh giá và rút bài toán sắp xếp cho những bài toán này thì giải thuật
tham lam cho chúng ta cách thức để hiểu được vấn đề
- Không chỉ là sắp xếp đơn thuần cho các bài toán với kích thước lớn như
trên, các bài toán này cho ta thấy được ý nghĩa to lớn của sắp xếp bằng chỉ mục
là rất cần thiết.
- Ta hoàn toàn có thể tăng kích thước mục tin trong việc sắp xếp, lợi dụng
phương pháp tham lam này để giải quyết các bài toán phức tạp hơn như bài toán
xếp ba lô, cây bao trùm,…
- Thông qua các bài toán ta tăng dần kỷ năng tư duy của học sinh. Việc
phát triển bài toán được nâng lên rõ rệt .
20
C. PHẦN KẾT LUẬN
1. Kết quả nghiên cứu.
Sau khi việc thực hiện áp dụng phương pháp vào việc giảng dạy môn tin
học ở chương trình phổ thông tôi đã thu được nhiều thành công vượt trội hơn
hẳn. Học sinh dễ dàng nhận dạng và thể hiện các bài toán tin học sau khi hiểu và
vận dụng phương pháp thì chất lượng đã tăng lên rõ rệt. Điều này đã chứng
minh tính đúng đắn của phương pháp, chứng minh kết quả trong phương pháp
dạy học trong trường phổ thông đối với bộ môn Tin. So sánh tỉ lệ học sinh hiểu
được thuật toán bằng phương pháp này trên những đối tượng học sinh ta hoàn
toàn tin tưởng vào kết quả thu được về khả năng nhận dạng và thể hiện bài toán.
Thực tế tôi đã theo dõi trên các lớp đã dạy thì tỉ lệ năm bắt được các bài toán và
thuật toán đã tăng lên từ 25-30% so với khi chưa áp dụng.
2. Kiến nghị đề xuất
a. Đối với trường.
- Có thể dành cho giáo viên có áp dụng phương pháp này nhằm làm tăng
chất lượng giảng dạy và kết quả học tập của học sinh. Không chỉ đối với giáo
viên giảng dạy môn Tin học mà có thể áp dụng phương pháp này cho những bộ
môn khoa học khác, đặc biệt là các bộ môn khoa học tự nhiên như Toán, Lý,