Tiết 3
? Các tính chất của thuật toán:
- Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác.
- Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để được thực hiện tiếp theo.
- Tính đúng đắn: Sau khi thuật toán kết thúc ta phải nhận được Output cần tìm.
2. Thuật Toán
+ Ví dụ: Xét bài toán tìm ƯCLN (M, N).
- Tính dừng: Khi giá trị M=N => in ra ƯCLN(M, N).
- Tính xác định:
+ Nếu M=N thì thực hiện 1 Thao tác => Kết thúc công việc.
+ Nếu M ? N thì thực hiện 1 dãy hữu hạn các bước B1 ? B2 ? B3 ? B4.
- Tính đúng đắn: Thông qua thuật toán trên => Output tìm được phải đúng. ƯCLN(12, 8) = 4.
3. Một số ví dụ thuật toán
+ Ví dụ1: Xét bài toán kiểm tra tính nguyên tố của 1 số nguyên dương.
Input và Output bài toán trên là gì?
Lời giải:
Input: N là một số dương.
Output: "N là một số nguyên tố hoặc N không là một số nguyên tố".
ý tưởng thuật toán:
- Nếu N =1 ? N không là số nguyên tố.
- Nếu 1 < N < 4 ?N là số nguyên tố.
- Nếu N ? 4 và không có ước trong phạm vi từ 2 ? phần nguyên căn bậc 2 của N thì N là số nguyên.

Thuật toán:
a) Biểu diễn thuật toán bằng cách liệt kê:
B1: Nhập số nguyên dương N.
B2: Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc.
B3: Nếu N < 4 ? N là số nguyên tố ? Kết thúc.
B4: i ? 2
B5: Nếu i > thì thông báo N là số nguyên tố ? Kết thúc.
B6: Nếu thì thông báo N không là số nguyên tố ? Kết thúc.
B7: i ? i + 1 rồi quay lại B5.
b) Biểu diễn thuật toán bằng sơ đồ khối.
Nhập N
N=1?
N<4?
i ? 2
Thông báo N là
số nguyên tố
rồi kết thúc
Thông báo N
không là số nguyên
tố rồi kết thúc
i ? i + 1
Đúng
Sai
Đúng
Đúng
Sai
Sai
Đúng
Sai
* Ví dụ:
N = 19 =>
N = 27 =>
N=19 Là số nguyên tố
N=27 không Là số nguyên tố
? Thông qua bài học hôm nay các em cần nắm được những kiến thức sau:
- Tính chất của thuật toán.
- Xem lại ví dụ thuật toán tìm số nguyên tố.
? Bài tập về nhà:
- Dựa vào thuật toán kiểm tra số nguyên tố hãy kiểm tra các số N=(37, 61, 49) có phải là số nguyên tố hay không?
- Đọc trước ví dụ 2 mục 3.