Sử dụng ngôn ngữ lập trình Pascal để xây dựng chương trình minh họa cho các thuật toán trong sách giáo khoa Tin học 10 - Pdf 31

Sáng kiến – Kinh nghiệm

Người thực hiện: Nguyễn Thị Khuyên

Phần 1: ĐẶT VẤN ĐỀ
Kính thưa quý thầy cô giáo!
Nếu quý thầy cô đã và đang dạy bộ môn Tin học 10 thì hẳn thầy cô sẽ có
nhận xét ngay rằng: Trong học kỳ I, bài số 4 – Bài toán và thuật toán là một
bài khó dạy và học sinh khó có thể hiểu được các ví dụ mà sách giáo khoa
(SGK) đã đưa ra.
Với thời lượng là 6 tiết (5 tiết lý thuyết + 1 tiết bài tập), giáo viên rất khó
để truyền tải được toàn bộ các thuật toán ở trong SGK. Vậy thì có thể bỏ bớt
một vài thuật toán hay không? Tất nhiên là có thể, bởi vì bản thân người viết
sách cũng không yêu cầu phải truyền đạt hết tất cả những gì có trong sách.
Tuy nhiên, theo nhận định của cá nhân tác giả thì những thuật toán mà những
người viết sách đưa ra là rất hay, vấn đề còn lại là làm thế nào để học sinh có
thể hiểu được các thuật toán này? Có lẽ là quý thầy cô sẽ có cùng ý kiến với
tác giả là: Hãy minh họa thuật toán với thật nhiều bộ Test. Và ở trong SGK
cũng đã thực hiện theo cách này, nhưng chỉ với một vài bộ Test. Còn nếu thầy
cô minh họa trên bảng thì sẽ rất tốn thời gian. Ví dụ như ở thuật toán sắp xếp
bằng tráo đổi, ở mỗi bước, nếu có sự tráo đổi các phần tử thì ta cần phải viết
lại dãy số để thấy được sự tráo đổi này. Vậy thì đâu là giải pháp?
Xuất phát từ thực tế giảng dạy và từ trong nội dung chương trình Tin học
phổ thông: Toàn bộ chương trình Tin học 11 đều nghiên cứu về lập trình, là
kiến thức có liên quan mật thiết với các thuật toán, và sử dụng ngôn ngữ lập
trình (NNLT) Pascal để minh họa, bản thân tác giả nhận thấy rằng: chúng ta
hoàn toàn có thể sử dụng NNLT Pascal để xây dựng những chương trình minh
họa cho các thuật toán này. Đó cũng chính là lý do để tác giả viết đề tài “Sử
dụng ngôn ngữ lập trình Pascal để xây dựng chương trình minh họa cho
các thuật toán trong sách giáo khoa Tin học 10”.

Với hướng giải quyết này, tác giả đã xây dựng các chương trình minh
họa cho các thuật toán. Mỗi bài toán, tác giả trình bày qua 5 bước:
1. Xác định bài toán.
2. Mô tả thuật toán (bằng sơ đồ khối).
3. Viết chương trình chuẩn minh họa thuật toán. Với chương trình này,
khi chạy, ta chỉ có thể thấy được Output của bài toán mà không thấy được
từng bước của thuật toán.
Sử dụng ngôn ngữ lập trình Pascal …

Trang 2 / 27

Sáng kiến – Kinh nghiệm

Người thực hiện: Nguyễn Thị Khuyên

4. Giới thiệu chương trình minh họa chi tiết cho thuật toán. Đây chính là
chương trình tác giả sẽ dùng để minh họa, khi chạy, ta sẽ thấy từng bước của
thuật toán.
5. Minh họa chương trình khi chạy bằng một vài hình ảnh. Qua đây,
chúng ta có thể biết chương trình sẽ minh họa thuật toán như thế nào.
Trong thuật toán Tìm giá trị lớn nhất của một dãy số nguyên, tác giả đưa
thêm một cách mô phỏng thuật toán trên sơ đồ khối.
* Một số vấn đề cần lưu ý khi xây dựng chương trình minh họa:
1. Để minh họa thuật toán với nhiều bộ Test khác nhau, tác giả đã sử
dụng vòng lặp Repeat–Until để lặp lại quá trình sử dụng chương trình. Chỉ khi
nào người dùng nhấn phím ESC (sau mỗi lần minh họa với 1 bộ Test) thì
chương trình mới đóng lại (thể hiện ở điều kiện Readkey = #27).
2. Trong các chương trình minh họa chi tiết, bắt đầu chương trình luôn là
lệnh Textmode(C40); đây là lệnh chuyển chế độ hiển thị văn bản trên

Đưa ra Max
rồi kết thúc

Sai
ai > Max?

Sai

Đúng
Max ← ai
i←i+1

3. Chương trình chuẩn tương ứng với thuật toán
Với sơ đồ khối trên, chương trình chuẩn cài đặt thuật toán trên ngôn ngữ
lập trình Pascal sẽ là:
Program Tim_Max;
Const NMax = 200;
Var a: Array[1..NMax] of Integer;
N, i: Byte;
Max: Integer;
Begin
Write(' Nhap so nguyen duong N: '); Readln(N);
For i:=1 to N do
Begin
Write('
Nhap so hang thu ',i,': ');
Readln(a[i]);
End;
Max:=a[1];

For j:=1 to N do
Begin
If j=i then Textcolor(Yellow)
Else Textcolor(White);
Write(a[j]:4);
Textcolor(White);
End;
Readln;
End;
Begin
Textmode(C40);
Repeat
TextColor(White); Clrscr;
Write(' Nhap so nguyen duong N: '); Readln(N);
For i:=1 to N do
Begin
Write('
Nhap so hang thu ',i,': ');
Readln(a[i]);
End;
i:=N+1; Writeln(' Day so vua nhap:'); Xuat;
Max:=a[1];
TextColor(LightGreen);
Writeln(' Khoi tao: Max = a[1] = ',Max);
For i:= 2 to N do
Begin
TextColor(White); Writeln;
Writeln(' i = ',i,':');
Xuat;
Write(' a[',i,'] = ',a[i]);

5. Minh họa chương trình khi chạy
Dưới đây là hình ảnh minh họa chương trình khi chạy:

6. Mô phỏng thuật toán trên sơ đồ khối

Sử dụng ngôn ngữ lập trình Pascal …

Trang 6 / 27

Sáng kiến – Kinh nghiệm

Sử dụng ngôn ngữ lập trình Pascal …

Người thực hiện: Nguyễn Thị Khuyên

Trang 7 / 27

Sáng kiến – Kinh nghiệm

Sử dụng ngôn ngữ lập trình Pascal …

Người thực hiện: Nguyễn Thị Khuyên

Trang 8 / 27

Sáng kiến – Kinh nghiệm

Thông báo N
là số nguyên tố
rồi kết thúc

Sai

N chia hết
cho i?
Đúng

3. Chương trình chuẩn tương ứng với thuật toán
Program Nguyen_To;
Var N, i: Word;
TL: Boolean;
Begin
Write(' Nhap so nguyen duong N = ');
Readln(N);
If N = 1 then TL:= False
Else
If N < 4 then TL:= True
Else
Begin

Sử dụng ngôn ngữ lập trình Pascal …

Trang 9 / 27

Sáng kiến – Kinh nghiệm

If N < 4 then
TL:= True
Else
Begin
Write('[√',N,']=',Trunc(Sqrt(N)));
Readln;
i:= 2;
While i

III. BÀI TOÁN THỨ BA: SẮP XẾP DÃY SỐ BẰNG THUẬT TOÁN
TRÁO ĐỔI
1. Xác định bài toán
- Input: Số nguyên dương N và dãy A gồm N số nguyên a1, a2, …, aN.
- Output: Dãy A đã được sắp xếp thành một dãy không giảm.

Sử dụng ngôn ngữ lập trình Pascal …

Trang 11 / 27

Sáng kiến – Kinh nghiệm

Người thực hiện: Nguyễn Thị Khuyên

2. Sơ đồ khối mô tả thuật toán
Nhập N và dãy a1, a2, ..., aN
M←N

M
Nhap phan tu thu ',i,': ');
Readln(a[i]);
End;
Writeln(' Day vua nhap:'); Xuat;
M:= N;
While M>=2 do

Sử dụng ngôn ngữ lập trình Pascal …

Trang 12 / 27

Sáng kiến – Kinh nghiệm

Người thực hiện: Nguyễn Thị Khuyên

Begin
M:=M-1;
For i:= 1 to M do
If a[i]>a[i+1] then
Begin
Tam:=a[i];
a[i]:=a[i+1];
a[i+1]:=Tam;
End;
End;
Writeln(' Day sau khi xep:'); Xuat;

For i:=1 to N do
Begin
Write('
Nhap phan tu thu ',i,': ');
Readln(a[i]);
End;
Dau:=N+1;
M:= N;
Writeln(' Day vua nhap:'); Xuat;
Textcolor(LightGreen);
Write(' Gia tri khoi tao: M = ',M);

Sử dụng ngôn ngữ lập trình Pascal …

Trang 13 / 27

Sáng kiến – Kinh nghiệm

Người thực hiện: Nguyễn Thị Khuyên

If M=2 do
Begin
Textcolor(Yellow);
Writeln(' M = ',M);
M:=M-1;
For i:= 1 to M do
Begin

Trong quá trình sắp xếp, thủ tục Xuat chỉ được gọi khi tại bước lặp trong
vòng For–do có sự tráo đổi. Do đó, tùy thuộc vào dữ liệu nhập vào, có thể
Sử dụng ngôn ngữ lập trình Pascal …

Trang 14 / 27

Sáng kiến – Kinh nghiệm

Người thực hiện: Nguyễn Thị Khuyên

ứng với 1 hay nhiều giá trị của M (ở những bước lặp cuối), thủ tục này không
được gọi đến.
5. Minh họa chương trình khi chạy

IV. BÀI TOÁN THỨ TƯ: THUẬT TOÁN TÌM KIẾM TUẦN TỰ
1. Xác định bài toán
- Input: Số nguyên dương N, dãy N số nguyên khác nhau a 1, a2, …, aN và
số nguyên k.
- Output: Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của
dãy A có giá trị bằng k.

Sử dụng ngôn ngữ lập trình Pascal …

Trang 15 / 27

Sáng kiến – Kinh nghiệm

Người thực hiện: Nguyễn Thị Khuyên

For i:=1 to N do Write(a[i]:4); Readln;
End;
Begin
Clrscr;
Write(' Nhap so phan tu cua day, N = ');
Readln(N);
For i:=1 to N do
Begin
Write(' Nhap phan tu thu ',i,': '); Readln(a[i]);
End;
i:=N+1; Writeln(' Day so vua nhap:'); Xuat;
Write(' Nhap so can tim, k = '); Readln(k);
i:=1;
While (i
End;
i:=N+1; Writeln(' Day so vua nhap:'); Xuat;
Write(' Nhap so can tim, k = '); Readln(k);
i:=1;
While i

2. Sơ đồ khối mô tả thuật toán
Nhập N, a1, a2, ..., aN và k
Dau ← 1; Cuoi ← N
Giua ← [(Dau + Cuoi )/2]

aGiua = k?

Đúng

Sai
Đúng

aGiua > k?

Cuoi ← Giua – 1

Sai

Sai

Dau ← Giua + 1
Đưa ra Giua
rồi kết thúc

aGiua = k?
Đúng

Thông báo dãy A không có số hạng
nào có giá trị bằng k rồi kết thúc

Trang 19 / 27

Sáng kiến – Kinh nghiệm

Người thực hiện: Nguyễn Thị Khuyên

End;
If a[Giua]=k then
Write(' Tim thay ',k,' tai vi tri thu ',Giua)
Else Write(' Khong tim thay ',k,' trong day vua nhap');
Readln
End.

4. Chương trình minh họa chi tiết
Program Tim_Kiem_Nhi_Phan;
Uses Dos, Crt;
Const Max = 50;
Type M1C = Array[1..Max] of Integer;
Var a: M1C;
N, i, j, Dau, Cuoi, Giua: Byte;
k: Integer;
Procedure Xuat;
Begin
For j:=1 to N do
Begin
If (j>=Dau) and (j
Write(' Nhap so can tim, k = '); Readln(k);
Dau:=1; Cuoi:=N; Giua:=(Dau+Cuoi) div 2;
i:=1;
If a[Giua]=k then
Begin

Sử dụng ngôn ngữ lập trình Pascal …

Trang 20 / 27

Sáng kiến – Kinh nghiệm

Người thực hiện: Nguyễn Thị Khuyên
Textcolor(LightBlue);Writeln('Lan thu ',i);
Textcolor(White);
Writeln(' Dau = ',Dau,' ; Cuoi = ',Cuoi,' ;
Giua = ',Giua);
Xuat;
Writeln(' a[Giua] = ',a[Giua],' = k');

End
Else
While (Dauk then Write(' > ',k)
Else
If a[Giua]k then Cuoi:=Giua-1
Else Dau:=Giua+1;
i:=i+1;
End;
If a[Giua]=k then
Begin
Textcolor(LightGreen);
Writeln(' Ket luan:');
Writeln('

Tim thay ',k,' tai vi tri thu ',Giua);

End
Else
Begin

Textcolor(LightCyan);

khi nhập dữ liệu, do đó, tác giả đưa thêm vào thủ tục này để giảm bớt gánh
nặng khi nhập dữ liệu và coi như dữ liệu vào là dãy số sau khi đã sắp xếp.
Chúng ta hoàn toàn có thể bỏ thủ tục này đi và yêu cầu khi nhập dữ liệu phải
đúng như yêu cầu của bài toán.
Điều cần quan tâm thứ hai trong chương trình là: Trong thủ tục Xuat, ta
có thể thấy rằng các phần tử ở trong phạm vi tìm kiếm (từ Dau tới Cuoi) sẽ
được tô màu xanh lá cây, phần tử thứ Giua sẽ được tô màu vàng để dễ nhận
biết, còn các phần tử khác sẽ được tô màu trắng. Việc tô màu này là rất cần
thiết khi chạy chương trình để minh họa cho học sinh. Cũng chính vì việc tô
màu này mà ở 2 lần xuất dãy số đầu tiên, ta thấy có dãy lệnh gán:
Dau:=N; Cuoi:=1; Giua:= N+1;

Thực chất dãy lệnh này chỉ để “đánh lừa” máy tính, coi tất cả các phần
tử đều là các “phần tử khác” (như trên đã nói) và tất cả đều được tô màu
trắng.
Một vấn đề nữa là, ở trong chương trình này, ta thấy có một số câu lệnh
bị lặp lại, cụ thể là các câu lệnh
Writeln(' Lan thu ',i);
…
Write(' Dau = ',Dau,', Cuoi = ',Cuoi);
…

Vậy liệu việc lặp lại này có phải là thừa không? Có thể chương trình
minh họa này chưa được thiết kế một cách tối ưu, nhưng theo ý tác giả thì các
câu lệnh này được đưa vào để xét các trường hợp riêng như ở phần minh họa,
đó là các trường hợp: Tìm thấy sau lần duyệt đầu tiên; Tìm thấy sau nhiều lần
duyệt; Không tìm thấy.

Sử dụng ngôn ngữ lập trình Pascal …

Trang 24 / 27

Sáng kiến – Kinh nghiệm

Người thực hiện: Nguyễn Thị Khuyên

Phần 3: KẾT QUẢ VÀ VIỆC PHỔ BIẾN ỨNG DỤNG
NỘI DUNG VÀO THỰC TIỄN
Với việc xây dựng các chương trình minh họa như trên, trong quá trình
giảng dạy Tin học 10, bản thân tác giả thấy rằng các tiết học về bài toán và
thuật toán không còn nhàm chán, khô cứng nữa mà trở nên sôi nổi hơn và học
sinh cũng có thể hiểu các thuật toán một cách dễ dàng hơn.
Hơn nữa, với mỗi thuật toán, giáo viên có thể minh họa bằng rất nhiều
bộ Test khác nhau mà không mất nhiều công sức, có thể nói đây là đặc điểm
nổi bật mà máy tính có thể trợ giúp cho con người.
…
Đề tài này ra đời từ kinh nghiệm của bản thân tác giả trong quá trình
giảng dạy và từ những kiến thức mà tác giả có được nên trong khi thiết kế
chương trình, có thể chương trình của tác giả còn chưa đạt tối ưu. Tác giả rất
mong sự góp ý chân thành của quý thầy cô để những chương trình minh họa
này có thể trợ giúp cho chúng ta một cách hiệu quả hơn.
Tác giả xin chân thành cảm ơn!
Ayun Pa, tháng 01 năm 2011
Tác giả

Nguyễn Thị Khuyên

Sử dụng ngôn ngữ lập trình Pascal …

Nhờ tải bản gốc

Tài liệu, ebook tham khảo khác

Sử dụng ngôn ngữ lập trình Pascal để xây dựng chương trình minh họa cho các thuật toán trong sách giáo khoa Tin học 10 - Pdf 31

Tài liệu, ebook tham khảo khác

Học thêm