Bài giảng Tin học đại cương - Bài 5: Một số thuật toán thông dụng - Đỗ Bá Lâm

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 toán thông dụng
Đỗ Bá Lâm
lamdb@soict.hut.edu.vn
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
35.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
45.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
55.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: Nhập 2 số a, b.
• B2: Nếu a > b thì Max = a và đi đến bước kết thúc (B4).
• B3: (a <= b) Max  b.
• B4: Kết thúc. 
Max  a
a>b
Max  b
Đ S
65.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.
Đ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 thoát khỏi vòng lặp
Đ
S
5.1.3. Cấu trúc lặp (2)
7
Nhập N và
dãy số a1, a2,,aN
i > N
Hiển thị 
“Max là số lớn nhất”
Max  a1; i=2
ai > Max
i i + 1
S
S
Đ
Max  ai
Đ
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ố.
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 toán số học
• Các bài toán về số học
– Xác định một số nguyên có phải là số nguyên 
tố/hợp số hay không
– Tìm USCLN, BSCNN của 2 số nguyên 
– ..
12
Bài toán số nguyên tố
• Cho một số nguyên 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 nguyên 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ố nguyên 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 nguyên tố;
Dừng thuật toá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 toán USCLN, BSCNN
• Cho hai số nguyên 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
17
Bài tập
• Bài toá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
18
Bài tập
• Bài toán: Nhập vào ba số nguyên 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 vuông
• Điều kiện vuông: tổng bình phương 2 cạnh = bình 
phương cạnh còn lại
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 toán về dãy
• Làm việc với một dãy số
• Các bài toá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 toá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 toá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 toá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 toá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 toá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 toán đệ quy
• Với bài toán có thể được phân tích và đưa 
tới việc giải một bài toá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 toán nhỏ hơn
→ Tự thực hiện lại thuật toá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 toá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 toán.
– Phần tổng quát: Có yê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
Ví dụ
• Tính giai thừa của n:
– Trường hợp cơ bản: 0! = 1
– Trường hợp tổng quát: n! = (n-1)! * n
• Xây dựng dãy Fibonacci
– Trường hợp cơ bản: F(0) = 0; F(1) = 1
– Trường hợp tổng quát: F(n) = F(n-1) + F(n-2)
26
Tính giai thừa - Thuật toán đệ quy
• Input: số tự nhiên n
• Output: GT(n)=n!
• Thuật giải:
Nhập n
if(n=0) then GT:=1;
else
GT := GT(n-1)*n;
Xuất GT
27
Bài tập
• Xây dựng thuật toán cho bài toán tìm số 
Fibonacci F(n)
28
Thuật giải heuristic
• Dùng “mẹo”
• Áp dụng với những bài toán
– Chưa tìm được thuật toán và không biết có 
tồn tại thuật toán không
– Có thuật toán nhưng thời gian tính toán quá 
lâu hoặc điều kiện của thuật toán khó đáp 
ứng
29