Bài giảng Kiến trúc máy tính - Phần 1 - Chương 3: Thuật toán
1
3.1 Khái niệm
Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy
tắc nhằm xác định một dãy các thao tác trên những dữ liệu vào
sao cho sau một số hữu hạn bước thực hiện các thao tác đó ta
thu được kết quả của bài toán.
Dữ liệu vào (Input)
Kết quả đầu ra (Output)
Thuật toán
2
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
2
Ví dụ
Thuật toán Euclid là thuật toán tìm ước số chung lớn nhất (USCLN)
của hai số nguyên dương a và b.
Input: a, b là số nguyên dương
Output: USCLN của a và b
Thuật toán tìm Euclid có thể được mô tả như sau:
Bước 1: Nếu a < b thì hoán vị hai số a, b cho nhau
Bước 2: Nếu b = 0 thì USCLN là a
Bước 3: Ngược lại a > b, thì thực hiện :
• Tìm số dư r của phép chia a cho b;
• Gán a= b, b= r, rồi quay trở lại bước 2.
3
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
3
3.2 Tính chất của thuật toán
Tính đúng: Thuật toán phải cho ra kết quả chính xác;
Tính tổng quát: thuật toán phải áp dụng để giải một lớp bài
toán có dạng tương tự, chứ không phải chỉ áp dụng những bài
toán cụ thể riêng lẻ ;
Tính xác định: Các bước trong thuật toán phải rõ ràng, trật
tự thực hiện phải xác định và là duy nhất ;
Tính dừng: thuật toán phải cho ra kết quả sau một số hữu
hạn các bước ;
Tính hiệu quả: một thuật toán được gọi là hiệu quả nếu nó
đơn giản, dễ hiểu, thời gian thực hiện nhanh và chiếm ít bộ
nhớ ;
.....
4
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
4
3.3 Biểu diễn thuật toán
Người ta thường biểu diễn thuật toán theo các cách sau :
Dùng ngôn ngữ tự nhiên
(Liệt kê các bước)
Vẽ lưu đồ (Flowchart)
Mã gia
̉
5
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
5
Biểu diễn thuật toán bằng ngôn ngữ tự nhiên
Ta sử dụng ngôn ngữ con người để liệt kê từng bước thực hiện
của thuật toán.
Ví dụ: Thuật toán tính tổng hai số a và b:
Bước 1 : Nhập vào các số a và b;
Bước 2 : Tính tổng a+b;
Bước 3 : Xuất kết quả của tổng a+b.
6
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
6
Lưu đồ thuật toán (sơ đồ khối)
Ta sử dụng các hình sau để vẽ lưu đồ thuật toán :
7
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
7
Lưu đồ thuật toán (sơ đồ khối)
Ví dụ : Lưu đồ thuật toán tính tổng của hai số a và b :
8
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
8
Mã giả
Mã giả là một ngôn ngữ gần giống với ngôn ngữ lập trình. Nó
sử dụng kết hợp ngôn ngữ tự nhiên, các ký hiệu toán học, và
vay mượn một số cấu trúc của một ngôn ngữ lập trình nào đó
để thể hiện thuật toán
Mã giả không thể thực thi được trên máy tính
Mỗi tác giả viết có mỗi phong cách khác nhau, miễn là trình
bày rõ ràng và thể hiện được cách giải quyết bài toán
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
9
Mã giả
Ví dụ: Tìm số lớn nhất trong hai số a và b:
Nhập giá trị a,b;
if (a ≥ b) then
Xuất kết quả: Số lớn nhất là a;
else
Xuất kết quả: Số lớn nhất là b;
10
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
10
3.4 Các cấu trúc thuật toán cơ bản
3.4.1 Cấu trúc tuần tự (Sequential)
Trong cấu trúc này, các công việc được thự hiện tuần tự nối
tiếp nhau.
Ví dụ: Chẳng hạn như lưu đồ thuật toán
tính tổng của hai số a và b ở phần trước:
11
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
11
3.4.2 Cấu trúc lựa chọn (Selection)
Lựa chọn một công việc để thực hiện căn cứ vào một điều
kiện nào đó. Điều kiện ở đây là một biểu thức logic có hai giá trị
là đúng (T hoặc 1) và sai (F hoặc 0).
Đúng
Sai
Điều
kiện
Điều
kiện
0
1
Cách biểu diễn của cấu trúc lựa chọn trong lưu đồ thuật toán.
12
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
12
3.4.2 Cấu trúc lựa chọn (Selection)
Ví dụ : Lưu đồ thuật toán kiểm tra số nguyên a là số chẵn hay số lẻ.
Bắt đầu
Nhập a
Số dư = a mod 2
F
T
Số dư = 0
a là số chẵn
a là số lẻ
Kết thúc
13
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
13
3.4.3 Cấu trúc lặp (Repeating)
Thực hiện lặp lại một công việc nhiều lần căn cứ vào một
điều kiện nào đó. Có hai dạng như sau:
- Lặp xác định: là loại lặp mà khi viết chương trình, người lập
trình đã xác định được công việc sẽ lặp bao nhiêu lần.
- Lặp không xác định: là loại lặp mà khi viết chương trình người
lập trình chưa xác định được công việc sẽ lặp bao nhiêu lần. Số
lần lặp sẽ được xác định khi chương trình thực thi.
14
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
14
3.4.3 Cấu trúc lặp (Repeating)
Cấu trúc lặp có thể được biểu diễn bằng sơ đồ khối như sau:
Điều kiện
lặp
0
Các công việc
1
Điều kiện
lặp
1
Các công việc
0
15
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
15
3.4.3 Cấu trúc lặp (Repeating)
Ví dụ: Lưu đồ thuật toán tính tổng: S = 1 + 2 + ... + N.
Bắt đầu
Nhập N
0
N > 0
1
S = 0
i = 1
Đúng
i <= N
S = S + i
i = i + 1
Sai
Xuất S
Kết thúc
16
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
16
Bài tập
Vẽ lưu đồ thuật toán giải các bài toán sau đây:
Bài 1: Tính P(n) = 1*3*5*...*(2n+1), với n ≥ 0.
Bài 2: Cho n là số nguyên dương, x là số thực. Tính tổng:
Bài 3: Cho một năm bất kỳ nào đó. Kiểm tra xem năm này có
phải là năm nhuận hay không? Biết rằng, năm nhuận là năm chia
hết cho 4 nhưng không chia hết cho 100 hoặc là chia hết cho
400.
17
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
17
Bài tập
Bài 4: Cho 3 cạnh a, b, c. Kiểm tra xem có tồn tại tam giác được
tạo thành từ 3 cạnh này không? Nếu có, hãy tính diện tích của
tam giác.
Bài 5: Tìm tất cả các số lẻ nằm trong đoạn từ 0 đến 1000.
Bài 6: Cho một dãy số nguyên a0, a1, a2,..., an-1. Tính trung bình
cộng của các số chia hết cho 3.
Bài 7: Cho số nguyên n. Tính trị tuyệt đối của n
Bài 8: Trong trang trại của một nông dân có nuôi một số gà và
dê. Biết rằng, có tất cả 43 đầu và 108 chân. Hỏi trang trại có bao
nhiêu con gà và bao nhiêu con dê ?
18
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
18
Bài tập
Bài 9: Tính lương của nhân viên dựa vào lương_theo_ngày và
số_ngày_công như sau:
lương = (lu
Nếu (số_ngày_công) > 25, thì số ngày làm dư sẽ được
tính lương gấp đôi.
̛ơng_ theo_ngày) * (số_ngày_công)
Bài 10: Nhân viên của một siêu thị thực hiện sắp xếp N quả
trứng (N > 0) vào trong từng hộp, mỗi hộp có 12 quả trứng. Hỏi
có bao nhiêu hộp trứng và bao nhiêu trứng còn dư ?
Ví dụ: với 43 quả trứng, nhân viên sẽ sắp xếp được 3 hộp
trứng và còn thừa lại 7 quả trứng.
19
Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật
19
19 trang
09/04/2022
6840
Bạn đang xem tài liệu "Bài giảng Kiến trúc máy tính - Phần 1 - Chương 3: Thuật toán", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_kien_truc_may_tinh_phan_1_chuong_3_thuat_toan.pdf
