BAI TOAN VA THUAT TOAN (Tiet 3)
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (560.86 KB, 10 trang )
TiÕt 3
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
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
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
Input và Output bài
toán trên là gì?
toán trên là gì?
Lời giải:
Lời giải:
Input:
Input: N là một số d ơng.
Output:
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:
ý 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:
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.
iΝM
Ν
b) BiÓu diÔn thuËt to¸n b»ng s¬ ®å khèi.
NhËp N
N=1?
N<4?
i 2
i> ?
Ν
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ΝM
i i + 1
§óng
Sai
§óng
§óng
Sai
Sai
§óng
Sai
* VÝ dô:
i
2 3 4 5
N/i
19/2 19/3 19/4
Chia hÕt
kh«ng?
kh«ng kh«ng kh«ng
N = 19
19 4
=
i
2 3 4 5 6
N/i
27/2 27/3 27/4 27/5
Chia hÕt
kh«ng?
kh«ng Chia hÕt kh«ng Kh«ng
N = 27
27 5
=
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.
