Thuật toán

Trang chủ Nhập môn lập trình Thuật toán

Thuật toán

Nguyễn Dương 06-06-2024

I. KHÁI NIỆM

- Thuật toán là một dãy các thao tác được máy tính thực hiện theo một trình tự nhất định nhằm để giải quyết một bài toán nào đó.

- Mỗi thao tác trong thuật toán mà máy tính thực hiện được thì được gọi là thao tác khả thi. Thao tác mà máy tính không hiểu được thì được gọi là thao tác không khả thi.

II. CÁCH TRÌNH BÀY THUẬT TOÁN

- Bắt đầu

Bước 1: Thao tác 1

Bước 2: Thao tác 2

...............................

Bước N: Thao tác N

- Kết thúc

- Tất cả các thao tác phải là thao tác khả thi.

- Các thao tác được thực hiện từ trên xuống dưới, từ trái sang phải.

- Thuật toán sau khi viết xong sẽ được chuyển sang một ngôn ngữ mà máy tính thực hiện được. Ngôn ngữ như vậy được gọi là ngôn ngữ lập trình.
- Các ngôn ngữ lập trình thông dụng hiện nay gồm có: C++, C#, Java, Java script, Python, PHP, Rust ...........

III. BIỂU THỨC TRONG THUẬT TOÁN

Một biểu thức đại số được xây dựng từ:

- Các số nguyên, số hữu tỷ, số thực ........ gọi là hằng số

- Các biến (x,y,z......), có thể lấy giá trị là các hằng số

- Các phép toán cộng, trừ, nhân, chia, căn, log ........... được thao tác trên các hằng số và các biến theo một trình tự nhất định.
Khi thay thế các biến bằng một hằng số thì ta được kết quả của biểu thức là một hằng số, kết quả đó gọi là giá trị của biểu thức.

1. Thao tác gán trong thuật toán

x ← a: Gán giá trị a cho x

a là một hằng số hoặc biểu thức đại số

Ví dụ:

Bắt đầu

B1: x ← 5

B2: y ← 2*x + 5

Kết thúc

- 5 được gán cho biến x.

- Kết quả của biểu thức 2*x + 5 sẽ được gán cho biến y. Vậy y = 2*5 + 5 = 15

2. Mô tả biến

Các biến được mô tả trong một giải thuật được mô tả như sau

STT	TÊN BIẾN	KIỂU GIÁ TRỊ GÁN CHO BIẾN	Ý NGHĨA GIÁ TRỊ GÁN CHO BIẾN
1	x	Kiểu giá trị 1	Ý nghĩa 1
2	y	Kiểu giá trị 2	Ý nghĩa 2
3	z	Kiểu giá trị 3	Ý nghĩa 3

…...	……	…………….	………….

Ví dụ viết thuật toán tính diện tích hình chữ nhật có chiều dài là 7 cm và chiều rộng là 5 cm

- Lập bảng mô tả biến

STT	TÊN BIẾN	KIỂU GIÁ TRỊ GÁN CHO BIẾN	Ý NGHĨA GIÁ TRỊ GÁN CHO BIẾN
1	a	Số thực	Chiều dài
2	b	Số thực	Chiều rộng
3	dt	Số thực	Diện tích

- Viết thuật toán

Bắt đầu

Bước 1: a ← 7

Bước 2: b ← 5

Bước 3: dt ← a*b

Kết thúc

3. Thao tác gán giá trị cho biến

- Các giá trị được gán cho biến thương được nhập từ bàn phím. Các biến đang đề cập đến phải là biến kiểu số.

4. Thao tác viết giá trị biểu thức

- Viết biểu thức 1, biểu thức 2, biểu thức 3, ........., biểu thức N. Với biểu thức là biểu thức đại số hoặc câu thông báo có dạng "thông báo".

- Ý nghĩa: Hiện giá trị của biểu thức ra màn hình.

Ví dụ:

Bắt đầu

Bước 1: Nhập a,b

Bước 2: dt ← a*b

Bước 3: Viết dt

Kết thúc

- Một thuật toán thường có 3 bước: Input => Process => Output

5. Xây dựng một thuật toán

Bước 1: Xác định kết quả cần hiện ra màn hình. Xác định các biến chứa kết quả.
Bước 2: Xác định các giá trị cần nhập. Xác định các biến chứa giá trị nhập.
Bước 3: Lập bảng mô tả biến
Bước 4: Viết thuật toán

Ví dụ: Viết thuật toán tính diện tích hình chữ nhật
Bước 1: Kết quả hiện ra màn hình ra diện tích hình chữ nhật. Giá trị được gán cho biến dt
Bước 2: Giá trị cần nhập là chiều dài và chiều rộng. Giá trị được gán cho biến a và b
Bước 3: Lập bảng mô tả biến
Bước 4: Viết thuật toán

6. Biểu thức luận lý

Biểu thức luận lý được xây dựng từ:

- Giá trị hằng luận lý: Đúng hoặc Sai. Ta dùng True thay cho Đúng và False thay cho Sai

- Các biến lấy giá trị thuộc True, False

- Các biểu thức luận lý đã cho

- Các phép toán luận lý ( <, ≤, >, ≥, ≠, AND, OR, NOT) thao tác trên các hằng, các biến, các biểu thức luận lý đã cho theo một trình tự nhất định. Ta dùng "và" để xác định thứ tự.

Khi thay thế các biến trong biểu thức luận lý bởi các hằng luận lý thì kết quả thực hiện các phép toán trong biểu thức sẽ là một hằng luận lý.

6.1: Phép toán <, ≤, >, ≥, ≠

X và Y là 2 biểu thức đại số. Giá trị của biểu thức X > Y là True nếu X > Y. Ngược lại nếu X < Y thì giá trị của biểu thức là False.

Ví dụ:

5 > 4: Giá trị của biểu thức là True.

6 > 8: Giá trị của biểu thức là False

6.2: Phép toán AND, OR, NOT

X	Y	X AND Y
True	True	True
True	False	False
False	True	False
False	False	False

X	Y	X OR Y
True	True	True
True	False	True
False	True	True
False	False	False

X	NOT X
True	False
False	True

Lưu ý: Trong 1 phép toán có cả phép AND và OR thì phép AND được ưu tiên tính trước.

Ví dụ:

True or False and False = True or (False and False) = True or True = True

6.3: Phép gán

A ← Biểu thức luận lý

Với A là biến luận lý

Ví dụ 1:

Biểu thức luận lý trong toán là 0 ≤ x ≤ 100. => Biểu thức luận lý trong thuật toán là (0 ≤ x) AND (x ≤ 100)

Ví dụ 2:

C AND (0 ≤ x). Với C là biến luận lý, x là biến số nguyên.

Nếu thay C là True, thay x = 1 thì giá trị của biểu thức là True. Vì 0 ≤ 1 là True (Đúng), biểu thức C AND (0 ≤ x) sẽ thành True AND True, kết quả là True.

Ví dụ 3:

B ← NOT (C AND (0 ≤ x)). Dựa vào kết quả ở ví dụ 2 ta được giá trị của biểu thức C AND (0 ≤ x) là True. Vậy NOT (C AND (0 ≤ x)) sẽ là False.

=> Giá trị False được gán cho B.

7. Thao tác rẽ nhánh

Dạng 1: Nếu giá trị của biểu thức luận lý là True thì thực hiện
B1: Thao tác 1
B2: Thao tác 2
.......................
Bn: Thao tác n

- Nếu giá trị của biểu thức luận lý là True thì lần lượt thực hiện cac thao tác từ thao tác 1 đến thao tác n. Nếu giá trị của biểu thức luận lý là False thì không thực hiện các thao tác.

- Ví dụ: Tìm giá trị lớn nhất của 2 số thực a và b.

Bước 1: Kết quả cần hiện ra màn hình là a nếu a > b, ngược lại nếu a ≤ b thì kết quả sẽ là b. Kết quả được gán vào biến Max
Bước 2: Các giá trị cần nhập là 2 số thực a và b.
Bước 3: Bảng mô tả biến

STT	TÊN BIẾN	KIỂU GIÁ TRỊ GÁN CHO BIẾN	Ý NGHĨA GIÁ TRỊ GÁN CHO BIẾN
1	a	Số thực	Số thực a
2	b	Số thực	Số thực b
3	Max	Số thực	Số thực lớn nhất

Bước 4: Viết thuật toán

Cách 1:
B1: Nhập a, b
B2: Max ← a
B3: Nếu Max < b thì thực hiện Max ← b
B4: Viết Max

Cách 2:
B1: Nhập a, b
B2: Nếu a > b thì thực hiện Max ← a
B3: Nếu a ≤ b thì thực hiện Max ← b.
B4: Viết Max

Dạng 2: Nếu giá trị của biểu thức luận lý là True thì thực hiện

B1: Thao tác 1
B2: Thao tác 2
.......................
Bn: Thao tác n
Ngược lại thì thực hiện
B1': Thao tác 1'
B2': Thao tác 2'
.......................
Bn': Thao tác n'

- Nếu giá trị của biểu thức luận lý là True thì lần lược thực hiện các thao tác từ thao tác 1 đến thao tác n. Nếu giá trị của biểu thức luận lý là False thì thực hiện các thao tác từ thao tác 1' đến thao tác n'.

Ví dụ: Viết thuật toán tìm giá trị lớn nhất của 2 số thực a và b

B1: Nhập a, b
B2: Nếu a > b thì thực hiện Max ← a
Ngược lại thì thực hiện
Max ← b

B3: Viết Max

8. Thao tác lặp

- Nếu giá trị của biểu thức luận lý là True thì thực hiện

B1: Thao tác 1

B2: Thao tác 2
.......................
Bn: Thao tác n
Quay lại kiểm tra, nếu giá trị của biểu thức luận lý vẫn là True thì tiếp tục thực hiện lại từ thao tác 1 đến thao tác n. Sau đó lại quay lại kiểm tra giá trị biểu thức.

- Ví dụ: Viết thuật toán tính tổng của của một dãy các số nguyên có thứ tự liên tiếp nhau bắt đầu từ số 1. T = 1 + 2 + 3 + 4 + 5 + ...... + n. Với n ≥ 1

Bước 1: Kết quả cần hiện ra màn hình là tổng của 1 + ........ + n. Kết quả được gán vào biến T
Bước 2: Nhập giá trị cho biến n
Bước 3: Bảng mô tả

STT	TÊN BIẾN	KIỂU GIÁ TRỊ GÁN CHO BIẾN	Ý NGHĨA GIÁ TRỊ GÁN CHO BIẾN
1	i	Số nguyên	Số hiện tại
2	n	Số nguyên	Số lớn nhất trong dãy
3	T	Số nguyên	Tổng