TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

TIN HỌC ĐẠI CƯƠNG
Bài 5. Một số thuật tốn thơng dụng

Đỗ Bá Lâm



Nội dung
5.1. Các cấu trúc cơ bản trong lập trình
5.2. Giả mã (pseudocode)
5.3. Thuật toán số học
5.4. Thuật toán về dãy
5.5. Thuật toán đệ quy

2


5.1. Các cấu trúc cơ bản trong lập trình
• Cấu trúc tuần tự
• Cấu trúc rẽ nhánh
• Cấu trúc lặp

3


5.1.1. Cấu trúc tuần tự
•

Các bước được thực hiện theo 1 trình tự tuyến
tính, hết bước này đến bước khác
Bước 1

Bước 2
…

Bước n
4


5.1.2. Cấu trúc rẽ nhánh
•
•

Việc thực hiện bước nào phụ thuộc vào điều
kiện xác định.
Ví dụ: Tìm max của 2 số a, b.
– Nếu a > b thì max là a, ngược lại max sẽ là b.
– Diễn giải:
•
•
•
•

B1:
B2:
B3:
B4:


Nhập 2 số a, b.
Nếu a > b thì Max = a và đi đến bước kết thúc (B4).
(a <= b) Max  b.
Đ
S
Kết thúc.
a>b

Max  a

Max  b

5


5.1.3. Cấu trúc lặp
•

•
•

Một thao tác/ cơng việc
có thể được thực hiện
lặp nhiều lần.
Lặp lại chừng nào điều
kiệu lặp còn đúng.
Số lần lặp có thể biết
trước hoặc khơng biết
trước.Tuy nhiên số lần
lặp phải hữu hạn.


S
Điều kiện
Đ

Thực hiện cơng việc
trong vịng lặp

Thực hiện cơng việc
khi thốt khỏi vịng lặp
6


5.1.3. Cấu trúc lặp (2)
Ví dụ: Tìm số lớn nhất của
một dãy có n số
◼

◼

◼

Lần lượt phải so sánh số Max
tạm thời (lúc đầu Max được
gán bằng phần tử thứ nhất,
a1) với ai, với i từ 2, 3,…, n.
Việc so sánh này được thực
hiện lặp nhiều lần giữa Max
và ai.
Khi kết thúc quá trình lặp, ta

sẽ thu được Max là số lớn
nhất của dãy n số.

Nhập N và
dãy số a1, a2,…,aN
Max  a1; i=2

i>N

Đ

Hiển thị
“Max là số lớn nhất”

Đ

Max  ai

S

ai > Max
S

ii+1
7


Nội dung
5.1. Các cấu trúc cơ bản trong lập trình
5.2. Giả mã (pseudocode)

5.3. Thuật toán số học
5.4. Thuật toán về dãy
5.5. Thuật toán đệ quy

8


5.2. Mã giả (pseudocode)
• Gán: ; :=
–ii+1
– a := b + c

• Cấu trúc chọn
if(điều kiện) then (hành động)
hoặc
if(điều kiện) then (hành động)
else (hành động)

• Cấu trúc nhảy goto:
– goto nhãn x;
9


5.2. Giả mã (2)
• Cấu trúc lặp:
while điều_kiện do hành_động
hoặc
repeat
hành_động
until điều_kiện

hoặc
for biến:= gtrị_đầu to gtrị_cuối do hành_động
hoặc
for biến:= gtrị_đầu downto gtrị_cuối do hành_động

10


Nội dung
5.1. Các cấu trúc cơ bản trong lập trình
5.2. Giả mã (pseudocode)
5.3. Thuật toán số học
5.4. Thuật toán về dãy
5.5. Thuật toán đệ quy

11


5.3. Thuật tốn số học
• Các bài tốn về số học
– Xác định một số nguyên có phải là số ngun
tố/hợp số hay khơng
– Tìm USCLN, BSCNN của 2 số nguyên
– ..

12


Bài tốn số ngun tố
• Cho một số ngun dương p. Làm thế nào để biết

được p có phải số nguyên tố hay không?
– Input: p nguyên dương
– Output: kết luận về tính ngun tố của p

• Ý tưởng?
– p = 1? → Không phải số nguyên tố
– p > 1?
• Kiểm tra từ 2 đến p-1 có phải là ước số của p khơng
• Nếu có thì kết luận p khơng là số ngun tố, ngược
lại khơng có số nào thì kết luận p là số nguyên tố

13


Bài toán số nguyên tố (2)
Nhập p
if p=1 then begin
Xuất: p khơng ngun tố;
Dừng thuật tốn;
end
flag := TRUE
for k:=2 to p-1 do
if (k là ước số của p) then begin
flag:=FALSE;
break; { ngắt vòng lặp FOR }
end
if flag=TRUE then
Xuất: p là số nguyên tố
else
Xuất: p không là số nguyên tố


14


Bài tốn USCLN, BSCNN
• Cho hai số ngun a, b. Tìm USCLN, BSCNN của hai số
này?
– Input: a, b nguyên
– Output: USCLN, BSCNN
• Ý tưởng?
– a = |a|, b =|b|
– a=0 && b=0 => khơng có USCLN
– a=0 || b=0 => USCLN là số khác cịn lại
– Ngược lại
• Trừ dần chừng nào a!=b => a=a-b hoặc b=b-a;
• Ơclit: c=a%b. Chừng nào c!=0=> a=b; b=c;
15


Bài toán USCLN, BSCNN
Nhập a, b
a : = |a|; b: = |b|;
if(a=0 and b=0) then begin
Xuất: khơng có USCLN
Dừng thuật toán
end
else if (a=0 or b=0) then begin
Xuất: USCLN là a+b
Dừng thuật toán;
end

while (a !=b) do
begin
if (a>b) a = a-b;
else
b = b-a;
end
Xuất: a là USCLN

16


Bài tập
• Bài tốn: Giải phương trình bậc II
– Đầu vào: Ba hệ số a, b, c
– Đầu ra: Nghiệm của phương trình
ax2 + bx + c = 0

• Ý tưởng:
– Lần lượt xét a = 0, b = 0 rồi xét c=0 để xét các
trường hợp của phương trình

17


Bài tập
• Bài tốn: Nhập vào ba số ngun dương
a, b, c. Cho biết đây có phải 3 cạnh của
một tam giác vuông hay không?
– Đầu vào: ba số a, b, c
– Đầu ra: Kết luận tam giác vuông hay khơng


• Ý tưởng:
– Đìều kiện tam giác vng
• Điều kiện vng: tổng bình phương 2 cạnh = bình
phương cạnh cịn lại
18


Nội dung
5.1. Các cấu trúc cơ bản trong lập trình
5.2. Giả mã (pseudocode)
5.3. Thuật toán số học
5.4. Thuật toán về dãy
5.5. Thuật toán đệ quy

19


5.4. Thuật tốn về dãy
• Làm việc với một dãy số
• Các bài tốn điển hình
– Tìm số lớn nhất, nhỏ nhất trong dãy
– Kiểm tra dãy có phải là dãy tăng hoặc dãy
giảm
– Sắp xếp dãy tăng dần hoặc giảm dần
– Tìm trong dãy có phần tử nào bằng một giá trị
cho trước
– Tính trung bình cộng của dãy
–…
20



Ví dụ - Tìm số lớn nhất trong dãy
• Input: dãy số a1, a2, a3,… an
• Output: max là giá trị lớn nhất trong dãy số
đã cho
• Thuật tốn:
max:=a1;
for i:=2 to n do
if max < ai then max:= ai
Xuất: max là giá trị lớn nhất trong dãy số

21


Bài tập
• Bài 1. Xây dựng thuật tốn tìm phần tử có giá trị truyệt
đối lớn nhất trong dãy gồm n phần tử.
• Bài 2. Xây dựng thuật tốn tìm tổng của các số chẵn và
tổng của các số lẻ trong dãy gồm n phần tử được nhập
vào từ bàn phím.
• Bài 3. Xây dựng thuật tốn kiểm tra xem một dãy số
gồm n phần tử được nhập vào từ bàn phím có phải là
dãy số tăng (hoặc giảm) khơng.
• Bài 4. Xây dựng thuật tốn tính trung bình cộng của các
số dương trong dãy gồm n số được nhập vào từ bàn
phím.

22



Nội dung
5.1. Các cấu trúc cơ bản trong lập trình
5.2. Giả mã (pseudocode)
5.3. Thuật toán số học
5.4. Thuật toán về dãy
5.5. Thuật toán đệ quy

23


5.5. Thuật tốn đệ quy
• Với bài tốn có thể được phân tích và đưa
tới việc giải một bài tốn cùng loại nhưng
cấp độ thấp hơn
– độ lớn dữ liệu nhập nhỏ hơn
– giá trị cần tính tốn nhỏ hơn

→ Tự thực hiện lại thuật tốn
• Ví dụ:
– Giai thừa: n! = (n-1)! * n
– Dãy số Fibonacci: 0, 1, 1, 2, 3, 5, 8...
• F(n) = F(n-1) + F(n-2)
24


5.5. Thuật tốn đệ quy (2)
• Để xây dựng thuật toán đệ quy, cần xác định:
– Trường hợp cơ bản: (Các) trường hợp khơng cần
thực hiện lại thuật tốn.

– Phần tổng qt: Có u cầu gọi đệ quy
• Cần xác định nguyên lý đưa trường hợp tổng quát
về trường hợp cơ bản
• Đảm bảo tính dừng của giải thuật đệ quy - chắc
chắn từ trường hợp tổng quát sẽ đến được trường
hợp cơ bản

25