BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)

Bài: 4- tiết: 12
Tuần dạy: Ngày dạy:



Mục tiêu:
Kiến thức:
HS biết: Biết khái niệm bài toán và thuật toán, các đặc trưng chính của thuật toán.
HS hiểu:
Hiểu 1 số thuật toán thông dụng.
Hiểu cách biểu diễn thuật toán bằng ngôn ngữ liệt kê (dùng ngôn ngữ tự nhiên).
Mô tả được thuật toán giải một số bài toán đơn giản bằng ngôn ngữ liệt kê.
Kỹ năng:
Xây dựng được thuật toán giải một số bài toán đơn giản bằng sơ đồ khối hoặc liệt kê.
Thái độ: Có ý thức sử dụng các kiến thức trên góp phần phát triển tư duy khi giải quyết các vấn đề trong khoa học cũng như trong đời sống.
Trọng tâm:
Xây dựng được thuật toán giải một số bài toán đơn giản.
Chuẩn bị :
Giáo viên: Bảng
3.2 Học sinh:
Xem trước của bài 4 : “ Bài toán và thuật toán”
Sách giáo khoa.
Tiến trình:
Ổn định tổ chức và kiểm diện:
Kiểm tra miệng:
Câu 1: Xác định bài toán tìm giá trị lớn nhất của một dãy số nguyên?
Câu 2: Nêu ý tưởng giải bài toán tìm giá trị lớn nhất của một dãy số nguyên?
Trả lời:
Câu 1: Xác định bài toán:
- Input: Số nguyên dương N và dãy N số nguyên a1,...,aN.
- Output: Giá trị lớn nhất Max của dãy số.
Câu 2: Ý tưởng: - Khởi tạo giá trị Max = a1.
- Lần lượt i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Max, nếu ai>Max thì Max nhận giá trị mới là ai.
Bài mới:

HOẠT ĐỘNG CỦA GV VÀ HS
NỘI DUNG BÀI HỌC

 Hoạt động 1:

GV: Hãy xác định I/O của bài toán?
HS: Lên bảng viết.

HS: Có 5 phút nghiên cứu SGK, sau đó lên bảng trình bày thuật toán bằng phương pháp liệt kê.
Hoạt động 2:
GV: Hướng dẫn HS hoàn thành thuật toán.







HS: Một HS khác lên bảng dựa vào thuật toán bằng phương pháp liệt kê vẽ sơ đồ khối và trình bày trước lớp.

1. Bài toán:
2. Thuật toán:
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à 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ố 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 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à số 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 bước 5.
b) Sơ đồ khối: ( SGK trang 37)
Mô phỏng việc thực hiện thuật toán trên với N = 29 ( [
] = 5)


Củng cố:
Nêu ý 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.
Đáp án:
- Nếu N=1 thì N không là số nguyên tố;
- Nếu 1 < N < 4 thì N là 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ố.
Hướng dẫn học sinh tự học:
Đối với bài học ở tiết này: Làm các bài tập trong SGK
Đối với bài học ở tiết học tiếp theo: Đọc kỹ ví dụ 2 “Bài toán sắp xếp ”.
Rút kinh nghiệm :
Cần rút kinh nghiệm về :