Chương II
CÁC KIẾN THỨC CƠ BẢN.
I. Thuật toán:
1. Khái niệm thuật toán và đặc trưng của nó:
Giả sử nhằm đảm bảo vệ sinh an toàn thực phẩm chúng ta muốn đóng
gói kẹo dừa trên một dây chuyền tự động thay cho gói kẹo bằng tay như hiện
nay. Để giải quyết bài toán này, chúng ta phải thiết kế và chế tạo ra một thiết
bò cơ - điện tử thực hiện các công đoạn từ khâu chiết khối kẹo còn nóng sang
thiết bò đóng gói cho đến khâu đưa hộp kẹo ra khỏi băng chuyền. Thiết bò này
được điều khiển tự động bằng máy tính và gồm các thao tác:
Bước 0: Khởi động việc đếm số viên kẹo (sovienkeo:=0). Qua bước 1.
Bước 1: Nhận khối kẹo còn nóng từ chảo nấu. Nếu khối kẹo vừa nhận có trọng lượng khác 0
thì qua bước 2, bằng không qua bước 11.
Bước 2: Trọng lượng của khối kẹo khác 0? Đúng: Qua bước 3 – Sai: Qua bước 1.
Bước 3: Đùn ép và chia cắt khối kẹo thành viên thích hợp. Qua bước 4
Bước 4: Đưa viên kẹo lên khuôn ép đònh hình. Qua bước 5
Bước 5: Lấy viên kẹo ra khỏi khuôn ép và đặt lên băng giấy đúng vò trí qui đònh. Qua bước
6.
Bước 6: Cắt băng giấy vừa viên kẹo và ép gói theo dạng qui đònh. Qua bước 7.
Bước 7: Đẩy ép viên kẹo vào hộp. Qua bước 8.
Bước 8: Đếm số viên kẹo đã đặt vào hộp (sovienkeo:=sovienkeo+1). Nếu số viên kẹo còn
nhỏ hơn 100 thì trở về bước 2, ngược lại qua bước 9.
Bước 9: Đưa hộp kẹo ra khỏi băng chuyền. Qua bước 10:
Bước 10: Đặt hộp kẹo rổng vào vò trí cũ. Khởi động lại việc đếm số viên kẹo đã đặt vào
hộp. Trở về bước 2.
Bước 11: Dừng máy.
Qui trình trên cho phép ta/máy thực hiện chính xác, đúng từng bước một công
việc đã giao – từ lúc bắt đầu (nhận khối kẹo nóng/khởi tạo biến đếm) đến lúc
kết thúc công việc (dừng máy). Một số công đoạn có thể sẽ phải lập đi lập lại
nhiều lần. Với mỗi khối kẹo đã nhận qui trình cho ra kết quả rõ ràng là các
hộp kẹo. Qui trình trên có qui đònh thứ tự bắt buộc đối với các thao tác. Thứ tự

bò nhập chuẩn nào đó.
Thao tác xuất output(x) Thao tác này cho phép xuất giá trò hiện
tại của x ra một thiết bò xuất chuẩn nào
đó.
Thao tác gán trò
x:=y
Thao tác này được thực hiện từ vế phải
qua vế trái nhằm gán giá trò hiện tại của
y cho x.
Thao tác trả về
một giá trò
Return x Thao tác này cho phép trả về giá trò hiện
tại của x cho một thiết bò nào đó.
Các thao tác số
học cơ bản hoặc
các tác vụ căn bản
+ - * div. ...
Các cấu trúc điều khiển:
Để biểu diễn quá trình thực hiện một thuật toán, người ta có thể chỉ mô tả tuần
tự các tác vụ của thuật toán kèm theo các chỉ thò so sánh và các lệnh nhảy (jump hoặc
2
goto) là đủ. Chẳng hạn như trong ví dụ trên, ở bước 8 ta có một chỉ thò so sánh
(sovienkeo<100 ?) và một lệnh nhảy (Trở về bước 2 | Qua bước 9). Đó là cách mà các ngôn
ngữ lập trình cấp thấp như ASSEMBLY (hoặc thậm chí 1985 ANS BASIC –American
National Basic) vẫn dùng. Tuy nhiên mô tả thuật toán trong một cấu trúc như vậy làm
cho thuật toán trở nên khó đọc, khó hiểu và rất dễ trở nên rối rắm, nhiều nhầm lẫn một
khi có quá nhiều lệnh nhảy tới lui trong các bước thực hiện. Để làm cho việc mô tả
thuật toán trở nên trong sáng hơn người ta thấy rằng trong mọi trường hợp hoàn toàn có
thể thay lệnh nhảy (jmp hoặc goto) bằng (và chỉ cần như vậy là đủ) ba cấu trúc điều
khiển sau đây:

sau một số lần lặp nào đó.
3
Ví dụ:
I:=2
WHILE (I
≤
5) DO
Begin
Output (i
2
)
i:=i+1
End
Vòng lặp WHILE trong ví dụ này thực hiện khối chỉ thò được bao trong cặp
Begin ... End bốn lần (đưa ra thiết bò xuất chuẩn các số chính phương 4, 9, 16, 25).
o Các hình thức biểu diễn thuật toán.
o Lưu đồ thuật toán (flow chart) : Dùng các sơ đồ dòng chảy trong đó kết
hợp các đầu nối, các kí hiệu khối tác vụ và các mũi tên để biểu diễn quá
trình thực hiện của thuật toán.
Các kí hiệu khối tác vụ được qui đònh trong bảng sau:
Hình dạng Dùng để Ví dụ
Biểu diễn tác vụ xử lí
của máy tính.
Một xử lí được đònh
nghóa trước
Gọi thường
trình xử lí màn
hình
Input; Output
input (N)

FOR i:=giá trò đầu TO giá trò cuối DO Công Việc
Lập lại Công Việc mỗi lần i thay đổi giá trò (từ giá trò
đầu đến Giá Trò cuối), mỗi lần thực hiện xong Công
Việc giá trò i tự động tăng lên một đơn vò.
Ví dụ 1: Sau đây là đoạn mã giả tương ứng với lưu đồ giải phương trình dạng
ax+b=0 nói trên.
Procedure GiaiPhuongTrinhBacNhat
input(a)
input(b)
IF (a
≠
0) THEN
Output (x= -b/a)
ELSE
IF (b=0) THEN
Output(Phuong trinh co vo so nghiem)
ELSE
Output(Phuong trinh vo nghiem)
1
Chú ý rằng mã giả độc lập đối với mọi ngôn ngữ lập trình, do đó không cần tuân thủ cú pháp
nghiêm ngặt như của một ngôn ngữ lập trình nào. Mọi chỉ thò nếu cần thiết đều có thể dùng được trong
mã giả miễn là mô tả được bản chất thuật toán của bài toán cần giải.
5