12 - BAI TOAN VA THUAT TOAN (Tiet 3)

Ngày soạn : Tiết :
Ngày dạy : Lớp :
§4. BÀI TOÁN VÀ THUẬT TOÁN
(Tiết 3)
MỤC TIÊU
1. Kiến thức
- Biết Input và Output của bài toán kiểm tra tính nguyên tố của một số nguyên; biết thuật toán của bài toán đó
2. Kỹ năng
- Hiểu và trình bày được thuật toán kiểm tra tính nguyên tố của một số nguyên theo 2 cách liệt kê và sơ đồ khối.
PHƯƠNG PHÁP, PHƯƠNG TIỆN DẠY HỌC
1. Chuẩn bị của giáo viên
- Đồ dùng: Giáo án, SGK, SGV, tài liệu tham khảo máy chiếu (nếu có)
- Phương pháp: Thuyết trình, vấn đáp.
2. Chuẩn bị của học sinh
- Đồ dùng học tập: SGK, vở ghi, bút,....
III. NỘI DUNG BÀI GIẢNG
1. Ổn định tổ chức lớp
- Ổn định lớp.
- Chỉnh đốn trang phục.
- Sĩ số:.........Vắng:......
2. Kiểm tra bài cũ
Câu 1: Hãy nêu các cách biểu diễn thuật toán? Các tính chất của thuật toán?
Câu 2: Hãy mô tả thuật toán tìm giá trị lớn nhất của một dãy số nguyên theo phương pháp liệt kê?
Câu 3: Hãy mô tả thuật toán tìm giá trị lớn nhất của một dãy số nguyên theo phương pháp sơ đồ khối?
3. Đặt vấn đề
4. Nội dung bài mới
Hoạt động của GV
Hoạt động của HS
Tg

3. Một số ví dụ về thuật toán.
Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương.

Hoạt động 1: Hướng dẫn học sinh tìm ý tưởng của bài toán kiểm tra tính nguyên tố của một số nguyên dương.
- Yêu cầu học sinh xác định Input và Output của bài toán.


- Nhắc lại định nghĩa số nguyên tố?
- Trong các số sau, những số nào là số nguyên tố? 1, 2, 3, 5, 7, 8, 9, 30, 53, 100
- Vậy N là số nguyên tố nếu N không có ước từ 2 đến N-1.
- Để giảm số phép toán, ta chỉ cần kiểm tra số N là số nguyên tố nếu N không có ước từ 2 đến

- Từ định nghĩa đó ta có thể suy ra như sau:



3. Một số ví dụ về thuật toán.
Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương.







- Input: N là một số nguyên dương.
- Output: “N là số nguyên tố” hoặc “N không là số nguyên tố” .

- HS trả lời.
- HS trả lời.




*) ý tưởng bài toán
- Nếu N = 1 thì N không là số nguyên tố
- Nếu 1- Nếu N
4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc hai của N thì N là số nguyên tố


Hoạt động 2: Diễn tả thuật toán của bài toán trên bằng cách liệt kê dãy các thao tác










Ghi chú:
+ Biến i nhận giá trị nguyên thay đổi trong phạm vi từ 2 đến [
] +1 và dùng để kiểm tra N có chia hết cho i hay không.
+ [x] kí hiệu phần nguyên của x, là số nguyên không lớn hơn x và gần x nhất.

B1: Nhập số nguyên dương N;
B2: Nếu N=1 thì thông báo N không là số nguyên tố rồi kết thúc
B3: Nếu N<4 thì thông báo n là nguyên tố rồi kết thúc
B4: i (2;
B5: Nếu i>
thì thông báo N nguyên tố rồi kết thúc.
B6: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc
B7: i(i+1 rồi quay lại B5



Hoạt động 3: Diễn tả thuật toán của bài toán trên bằng cách sử dụng sơ đồ khối.
- Đặt câu hỏi để cùng học sinh xây dựng sơ đồ khối?
+ B1: Muốn nhập số N ta sử dụng hình gì?
+ B2: Để thể hiện thao tác so sánh N=1 ta dùng hình gì?
+ B3: Ta cũng sử dụng hình thoi để thể hiện thao tác so sánh N<4.
+ B4: Với việc ta i(2 ta sử dụng sử dụng hình gì?
+ B5, B6 : Ta tiếp tục sử dụng hình thoi để thực hiện thao tác so sánh.
+ B7: Ta tiếp tục sử dụng