Bai toan va thuat toan tiet 2

Tiết 11§ 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)

I. MỤC TIÊU:
Kiến thức:
– Biết vận dụng kiến thức về bài toán và thuật toán trong Tin học và hai phương pháp liệt kê các bước và sơ đồ khối để diễn tả thuật toán Kiểm tra tính nguyên tố của một số nguyên dương.
– Hiểu một số thuật toán thông dụng.
Kĩ năng:
– Bước đầu xây dựng được thuật toán của một số bài toán đơn giản.
Thái độ:
– Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó.
II. CHUẨN BỊ:
Giáo viên: – Giáo án.
– Tổ chức hoạt động nhóm, bài tập trắc nghiệm, các dụng cụ trực quan như hình vẽ,…
Học sinh: - Sách giáo khoa, vở ghi lý thuyết, đọc bài trước.
Kiến thức về bài toán và thuật toán trong Tin học và các phương pháp liệt kê và sơ đồ khối.
Các kiến thức về toán học: Định nghĩa số nguyên tố, …
III. HOẠT ĐỘNG DẠY HỌC:
1. Ổn định tổ chức (2p).
- Ổn định lớp.
- Kiểm tra sĩ số lớp.
2. Kiểm tra bài cũ:(8p)
Hỏi: Nêu khái niệm thuật toán? Các phương pháp biểu diễn thuật toán?
Đáp: ( Thuật toán là:…..
( Có 2 cách diễn tả thuật toán
-Liệt kê: viết thuật toán theo từng bước.
-Sơ đồ khối với các kí hiệu….
3. Giảng bài mới:
TG
Nội dung
Hoạt động của GV và HS

Hoạt động 1: Hướng dẫn tìm thuật toán giải bài toán Kiểm tra tính nguyên tố của một số nguyên dương
























25

























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.













( Xác định bài toán:
-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ố”.




( Ý tưởng:
+ Nếu N=1 thì N không là số nguyên tố;
+ Nếu 1 < N < 4 thì N là số nguyên tố.
+ 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ố.


( Thuật toán:
a) Cách liệt kê:
B1: Nhập số ng.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 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 là 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





























* Ví dụ:
( Với N = 17 ([
] = 4)
i
2
3
4
5

N/i
17/2
17/3
17/4


Chia hết
Không?
Không
Không
Không


( Vậy 17 là số nguyên tố.
( Với N = 33 ([
] = 5)
i
2
3

N/i
33/2
33/3

Chia hết không?
Không
Có

( Vậy 33 không là số nguyên tố.


( GV: Ở tiết trước các em đã được học khái niệm về bài toán và thuật toán cũng như các phương pháp biểu diễn thuật toán, để giúp các em hiểu rõ hơn về những khái niệm náy chúng ta cùng tìm hiểu nội dung tiếp theo 3) Một số ví dụ.
( GV: Xét ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương.
( GV: Dựa vào các kiến thức đã học một em hãy nhắc lại định nghĩa về số nguyên tố?
( HS: Số nguyên tố là số chỉ có 2 ước là 1 và chính nó.
( GV: Em hãy cho biết trong các số sau số nào là số nguyên tố: 1, 2, 3, 5, 6, 9, 11?
( HS: Trả lời 2, 3