$4b. Trình bày Thuật tốn
(Tóm tắt các cách trình bày)
Trong tin học, bài toán là một việc mà ta muốn máy tính thực hiện. Cho một bài tốn là mơ tả đầu vào
(Input) và yêu cầu của đầu ra (Output)
Ví dụ đơn giản:
Giải phương trình ax2 + bx + c = 0. Nếu mình muốn giao cho máy tính làm thì phải nhập các hệ số a, b,
c cho máy, rổi máy đưa kết quả ra ngay, ta không cần phải tự tay tính tốn gì hết. Tuy nhiên ta phải
“dạy” cho máy cách làm “tổng quát” để khi ta đưa a, b, c thế nào cho nó thì cũng phải ra kết quả!
Việc chỉ ra một cách tường minh lời giải của một bài toán gọi là thuật toán (Algorithm) giải bài tốn
đó. SGK đã nêu một định nghĩa chính thức như sau:
Thuật tốn đẻ giải một bài tốn là một dãy hữu hạn các tháo tác, được sắp xếp theo một trình tự xác
định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài tốn, ta nhận được Output cần tìm!
Chú ý:
Chương trình có khác với thuật tốn ở chỗ:
Chương trình thì nêu lên các bước giải, có thể khơng tường minh. Trả lời câu hỏi lần lượt làm những
gì?
Thuật tốn nêu bật phương pháp (mưu mẹo) qua các bước tường minh, và trả lời câu hỏi làm thế nào?
Thuật tốn có thể chỉ nêu một phần của chương trình! Cùng một bài tốn có thể có nhiều thuật tốn
khác nhau! Thuật tốn tối ưu là thuật tốn giúp máy tính thực hiện nhanh nhất, tốn ít bộ nhớ nhất.
Có 3 cách trình bày một thuật toán:
 Diễn giải thành từng bước: Các bước được thực hiện tuần tự hoặc nhảy đến bước trước hay
sau nhưng xa hơn sau khi gặp một điều kiện nào đó.
 Vẽ sơ đồ khố (lưu đồ): Khoanh hình trịn hay elíp để bắt đầu hay kết thúc, hình thoi để chứa
điều kiện, hình chữ nhật chứa cơng việc, và đoạn thẳng hay véo tơ chỉ đường đi.
 Giả lập trình: Dùng các cấu trúc của ngơn ngữ lập trình bậc cao, các kí hiệu tốn học và ngơn
ngữ tự nhiên. Cách này gọn gàng hơn.
Nhà quản lý, nhà doanh nghiệp hay nhà khoa học, nên nắm chắc được ít nhất một trong các cách trình
bày thuật tốn nêu trên.
Sau đây là một ví dụ đơn giản về chương trình và so sánh 2 thuật tốn khác nhau:
Ví dụ: Tính trung bình cộng của n số tự nhiên đầu tiên, n>1 nhập từ bàn phím.
Chương trình:

Bước 1. Nhập n từ bàn phím.
Bước 2. Tính tổng s = 1+2+…+n.
Bước 3. Tính kết quả = s/n.
Bước 4. Đáp số: kq.
Chú ý:
Ta có thể dùng kí hiệu mũi tên ngược để mơ ta phép gán giá trị của một biểu thức cho một đại lượng
có đặt tên (cịn gọi là biến).
Ví dụ:
Tăng k thêm 1 đơn vị, ta có thể viết: k  k+1.
Trong ngơn ngữ lập trình C/C++, ta viết ln k=k+1. Trong Pascal, ta viết k:=k+1.
Sau đây, ta đề cập các một phần chương trình trên, ở bước 2: Tính tổng s = 1+2+..+n.
Có các thuật tốn sau:
Thuật tốn 1. (Cơ bắp – cộng dồn):
Bước 1.
S  0, k  1. (Tức là cho S = 0 và cho k = 1).
Bước 2.
S  S+k. (Tức là cho S mới = S cũ + k).
Bước 3.
k  k+1. (Tức là tăng k lên 1 đơn vị).
Bước 4.
Nều k > n thì thu lấy giá tị của S và kết thúc!
Trái lại thì quay về thực hiện bước 2.
Cách làm trên, phải mất n-1 phép cộng, vô cùng vất vả khi n rất lớn! Chẳng hạn n = 1 triệu, phải
mất gần 1 triệu phép cộng!


Thuật toán 2. (Carl_Friedrich_Gauss)
Bước 1.
S  (1+n)*n/2.
Chỉ cần một bước!

Trên đây là thuật tốn tính tổng của một dãy số có quy luật, thì mới sử dụng cơng thức tốn học được. Chỉ
trừ khơng giỏi tốn thì mới phải làm theo thuật toán “cơ bắp”. Cho nên, việc kết hợp tốn học và tin học là
rất có lợi! Một người rất giỏi tin, nhưng lại khơng giỏi tốn thì vẫn tạo ra các thuật toán để giải bài toán tin
học, nhưng thường dài dòng và làm cho máy chạy lâu hơn, tốn nhiều bộ nhớ hơn, không tối ưu!
3.- Một số ví dụ
Ngồi các ví dụ trong SGK, từ trang 33 đến trang 44). Mình xin nêu một số ví dụ khác để giúp bạn biết
cách trình bày thuật tốn.

Ví dụ 1. Nhập dãy số a1, …, an, với n > 1. Nêu thuật tốn đếm các số hạng có giá trị bằng 0.
Cách1.
Bước 1.
Nhập n và dãy số an, …, an.
Bước 2.
k  1, d  0. (d sẽ là số lượng các số hạng = 0).
Bước 3.
Nếu ak = 0 thì d  d+1.
Bước 4.
k  k+1.
Bước 5.
Nếu k > n thì đáp số là d và kết thúc.
Trái lại quay về Bước 3.
Cách 2. (Lưu đồ. Chú ý; dấu + là cho trường hợp điều kiện đúng, - nếu sai).
Nhập n và
dãy số an,
…, an
k  1, d  0
0

+


ak=
0

d  d+1
k  k+1

k>n
+
Đáp số có
d sh = 0


Cách 3. (Giả lập trình)
Bước 1.
Nhập n và dãy số an, …, an.
Bước 2.
d  0. (d sẽ là số lượng các số hạng = 0).
Bước 3.
Cho k chạy từ 1 đến n. (Duyệt từ đầu dãy đến cuối dãy).
Với mỗi k đó xét ak: Nếu ak = 0 thì d  d+1.
Bước 4.
Đáp số: Có d số hạng bằng 0.
Các bài tập tương tự:
Nhập dãy số a1, …, an, với n > 1.
Nêu thuật tốn tính tổng tất cả các số hạng.
Nêu thuật tốn tính tổng tất cả các số hạng âm.
Nêu thuật tốn tính tổng tất cả các số hạng dương.
Nêu thuật tốn tính tổng nghịch đảo các số hạng khác khơng.
Nêu thuật tốn tính tổng các căn bậc 2 của các số hạng dương
Nêu thuật tốn tính tổng các bình phương các số hạng âm.

Bạn có thể tự nghĩ ra thêm!
Ví dụ 2. Nhập dãy số a1, …, an, với n>1. Nêu thuật tốn xét xem có số hạng nào bằng 0. (Chỉ cần có
hay khơng, khơng cần biết nhiều hay ít).
Cách1.
Bước 1.
Nhập n và dãy số an, …, an.
Bước 2.
k  1.
Bước 3.
Nếu ak = 0 thì đáp số là có và kết thúc.
Bước 4.
k  k+1.
Bước 5.
Nếu k  n thì về Bước 3.
Trái lại đáp số là khơng có.
Cách 2. (Lưu đồ).
Nhập n và dãy
số an, …, an

k1

0

+
ak=0

k  k+1

0


k>n
+
Đáp số khơng
có. Hết.

Cách 3. (Giả lập trình)
Bước 1.
Nhập n và dãy số an, …, an. (Nhớ giả thiết sẵn n > 1).

Đáp số có.
Kết thúc.


Bước 2.
Bước 3.
Bước 4.

k  1.
Chừng nào (ak  0) và (k  n) thì k  k+1. (Lặp lại khi điều kiện vẫn cịn thỏa nãn).
(Giống như cịn “đói” và “khát” thì cịn làm việc xác định đó).
Bước 3 kết thúc (hết lặp) là lúc mà (ak = 0) hoặc (k > n). Khi đó, suy ra ngay:
Nếu k>n thì trả lời khơng có
Trái lại trả lời có phần tử ak (với k nhận được phút cuối) là bằng 0..

Ví dụ 3. Nhập dãy số a1, …, an, với n > 1. Nêu thuật tốn tìm số hạng bằng 0 cuối cùng. Tức là trong
các số hạng bằng 0 thì tìm số hạng bằng 0 cuối cùng, k =?.
Cách1.
Bước 1.
Bước 2.
Bước 3.

Bước 4.
Bước 5.

Nhập n và dãy số an, …, an. (Nhớ giả thiết sẵn n > 1).
k  n.
Nếu ak = 0 thì đáp số là có số hạng thứ k đó bằng 0 và kết thúc.
k  k-1. (Tức là k giảm đi 1 đơn vị)
Nếu k > 0 thì về Bước 3.
Trái lại đáp số là khơng có.

Cách 2. (Lưu đồ).
Nhập n và dãy
số an, …, an

kn

0

+
ak=0

Đáp số
ak=0. Hết

k  k-1

0

k=0
+

Đáp số ko
có. Hết.

Cách 3. (Giả lập trình)
Bước 1.
Nhập n và dãy số an, …, an.
Bước 2.
k  n.
Bước 3.
Chừng nào (ak  0) và (k > 0) thì k  k-1. (While (ak  0) and (k > 0) do k:=k-1)
Bước 4.
Bước 3 kết thúc là lúc mà (ak = 0) hoặc (k = 0).
Nếu k = 0 thì trả lời khơng có, trái lại trả lời có số hạng thứ k đó bằng 0.


Các bài tập tương tự:
Nhập dãy số a1, …, an, với n>1, và một số b.
Nêu thuật tốn tính tìm số hạng đầu tiên bằng b.
Nêu thuật tốn tính tìm số hạng cuối cùng bằng b.
Nêu thuật tốn tính tìm số hạng nào mà bình phương lên sẽ bằng b.
Nêu thuật tốn tính tìm số hạng nào mà căn bậc 2 của nó bằng b.
Nêu thuật tốn tính tìm số hạng nào mà ngịch đảo sẽ bằng b.
Bạn có thể tự nghĩ ra thêm!
Ví dụ 4. Nhập dãy số a1, …, an, với n > 1. Nêu thuật toán xem đây có phải là dãy số tăng dần khơng?
Cách1.
Bước 1.
Bước 2.
Bước 3.
tăng).
Bước 4.

Bước 5.

Nhập n và dãy số an, …, an.
k  1.
Nếu ak  ak+1 thì trả lời là không tăng và kết thúc. (Gặp trường hợp đầu tiên khơng
k  k+1.
Nếu k < n thì về Bước 3.
Trái lại trả lời đây là dãy tăng, vì khơng gặp trường hợp nào ak  ak+1.

Cách 2. Mình nghĩ là bạn đã vẽ được lưu đồ. Từ giờ, bạn tự vẽ lấy!
Cách 3. (Giả lập trình)
Bước 1.
Nhập n và dãy số an, …, an.
Bước 2.
k  1.
Bước 3.
Chừng nào (ak < ak+1) và (k < n) thì k  k+1.
Bước 4.
Bước 3 kết thúc là lúc mà (ak  ak+1) hoặc (k = n).
Nếu k = n thì trả lời đây là dãy tăng, vì khơng gặp trường hợp nào ak  ak+1.
Trái lại trả lời không phải dãy tăng, vì gặp trường hợp nào ak  ak+1.
Các bài tập tương tự:
Nhập dãy số a1, …, an, với n>1.
Nêu thuật tốn tính xét xem dãy này có giảm khơng (a1 > a2 > a3 >…> an).
Nêu thuật tốn tính xét xem dãy này có là cấp số cộng khơng.
Nêu thuật tốn tính xét xem dãy này có là dãy khơng không đổi không. (a1 = a2 = a3 =…= an).
Nêu thuật tốn tính xét xem dãy này có là cấp số nhân khơng.
Nêu thuật tốn tính xét xem dãy này có số hạng nào gấp đơi số hạng tiếp theo khơng.
Nêu thuật tốn tính xét xem dãy này có số hạng nào bằng bình phương số hạng tiếp theo khơng.
Nêu thuật tốn tính xét xem dãy này có số hạng nào bằng căn bậc 2 của số hạng tiếp theo khơng.

Nêu thuật tốn tính xét xem dãy này có số hạng nào gấp đơi số hạng trước nó khơng.
Nêu thuật tốn tính xét xem dãy này có số hạng nào bằng bình phương số hạng trước nó khơng.
Nêu thuật tốn tính xét xem dãy này có số hạng nào bằng căn bậc 2 của số hạng trước nó khơng.
Bạn có thể tự nghĩ ra thêm!
Ví dụ 5. Nhập dãy số a1, …, an, với n > 1. Nêu thuật toán tìm min của các số hạng âm nếu có?
Cách1.
Bước 1.
Nhập n và dãy số an, …, an.
Bước 2.
k  1.
Bước 3.
Nếu ak  0 thì làm 2 việc:
k  k+1 và xét k:
nếu k > n thì trả lời là không số hạng nào âm và kết thúc,
trái lại về Bước 3.
Bước 4.
min  ak.
Bước 5.
k  k+1. Khi đó: nếu k > n thì đáp số min ra và kết thúc.
Bước 6.
Nếu ak < 0 thì về Bước 4, trái lại thì về Bước 5.
Cách 2. Bạn tự vẽ lấy!
Cách 3. (Giả lập trình)


Bước 1.
Bước 2.
Bước 3.
Bước 4.
Bước 5.

Bước 6.
Bước 7.

Nhập n và dãy số an, …, an.
k  1.
Chừng nào (ak  0) và (k  n) thì k  k+1. (Để tìm ak âm đầu tiên hoặc khơng có).
Bước 3 kết thúc chính là lúc mà có (ak < 0) hoặc (k > n).
Nếu k > n thì trả lời dãy khơng có số hạng âm nào và kết thúc.
min  ak.
Duyệt từ k+1 đến n: nếu gặp ak < min thì về Bước 5.
Sau khi duyệt thì đáp số min.

Các bài tập tương tự:
Nhập dãy số a1, …, an, với n>1.
Nêu thuật tốn tìm max của các số hạng dương.
Nêu thuật tốn tìm max của các số hạng âm.
Nêu thuật tốn tìm min của các số hạng dương.
Nêu thuật tốn tìm max của các số hạng lớn hơn 1.
Nêu thuật tốn tìm min của các số hạng lớn hơn 1.
Nêu thuật tốn tìm max của các số hạng nhỏ hơn 1.
Nêu thuật tốn tìm min của các số hạng nhỏ hơn 1.
Bạn có thể tự nghĩ ra thêm!
Ví dụ 6. Nhập dãy số a1, …, an, với n > 1. Thiết kế thuật tốn xét xem dãy có 2 số hạng nào bằng nhau
không? (Không cần liên tiếp!)
Cách1.
Bước 1.
Nhập n và dãy số an, …, an.
Bước 2.
i  1.
Bước 3.

j  i+1.
Bước 4.
Nếu ai = aj thì trả lời là có và kết thúc,
Bước 5.
j  j+1..
Bước 6.
Nếu j  n thì về Bước 4
Trái lại thì xét i:
Nếu i = n-1 thì trả lời là khơng có và kết thúc,
Trái lại: i  i+1 và về Bước 3.
Cách3 (Giả lập trình).
Bước 1.
Nhập n và dãy số an, …, an.
Bước 2.
Duyệt i từ 1 đến n-1: (For i:=1 to n-1 do)
Với mỗi i đó: Duyệt j từ i+1 đến n: (For j:=i+1 to n do)
Với mỗi j đó: Nếu ai = aj thì trả lời là có và kết thúc.
Bước 3.
Duyệt xong mà khơng bị kết thúc thì rõ ràng là khơng có.
Chú ý: Việc duyệt 2 vịng lồng nhau như trên có thể gặp ở một số bài tốn như:
Nhập dãy số a1, …, an, với n>1.
Nêu thuật toán xét xem dãy có 2 số hạng nào nghịch đảo của nhau khơng.
Nêu thuật tốn xét xem dãy có 2 số hạng nào đối nhau khơng.
Thậm chí có thể Duyệt 3 vịng lồng nhau như:
Tìm bộ 3 số tự nhiên x,y,z (0 < x < y < z < 100) là bộ số Pitago, tức là x2 + y2 = z2.
Cách3 (Giả lập trình). Có thể viết phối hợp ngơn ngữ tự nhiên, toán học và tiếng Anh:
For x = 1 to 98 do (Ta hiểu là với mỗi giá trị của x từ 1 đên 98, hãy làm việc sau:)
For y = x+1 to 99 do (Ta hiểu là với mỗi giá trị của y từ 1 đên 99, hãy làm việc sau:)
For z = y+1 to 100 do (Ta hiểu là với mỗi giá trị của z từ 1 đên 100, hãy làm việc sau:)
Xét bộ (x,y,z) đó: Nếu x2 + y2 = z2 thì thơng báo bộ số (x,y,z) đó ra.

www.lightsmok.wordpress.com