Giáo án Tin học 10 tiết 11: Bài toán và thuật toán

Ngày soạn : 11/10/2006	Tiết thứ : 11 
Ngày giảng: 12/10/2006	Tên bài giảng: Đ4. Bài toán và thuật toán 
I. Mục đích, yêu cầu
1. Kiến thức.
- Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước. 
- Hiểu một số thuật toán thông dụng : Kiểm tra tính nguyên tố của một số nguyên dương
2. Kỹ năng.
-Xây dựng được thuật toán giải một số bài toán đơn giản : Kiểm tra tính nguyên tố của một số nguyên dương bằng sơ đồ khối hoặc liệt kê các bước.
3. Thái độ.
- Thông qua thuật toán để rèn luyện tư duy cho HS. 
- Có thể nói rằng các kiến thức này không chỉ giúp ích cho HS tiếp tục học Tin học về sau mà quan trọng hơn là góp phần phát triển trí tuệ, khả năng tư duy để giải quyết vấn đề cho HS trong học tập cũng như trong công việc phục vụ xã hội.
II. Phương pháp, phương tiện giảng bài
Phương pháp: thuyết trình, vấn đáp.
Phương tiện: SGK, SGV, bảng phụ (đèn chiếu).
III. Tiến trình bài giảng
Kiểm tra bài cũ :
Nêu thuật toán tìm Max bằng cách liệt kê, 
Nếu sử dụng sơ đồ khối người ta dùng những khối nào? Nêu chức năng của từng khối
Vào bài mới(3’) : 
Nội dung bài : 
Nội dung bài giảng
Họat động của giỏo viờn và học sinh
TG
- Thuật toán có các tính chất chính sau:
+ 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.
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) Thuật toán diễn tả bằng cách liệt kê
Nhập số nguyên dương N;
Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc;
Nếu N < 4 thì thông báo N là nguyên tố rồi kết thúc;
i ơ 2;
Nếu i > [] thì thông báo N là nguyên tố rồi kết thúc;
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;
i ơ i + 1 rồi quay lại bước 5.
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.
b) Sơ đồ khối
Ví dụ mô phỏng thuật toán: 
(Với N = 29 ()
i
2
3
4
5
6
N/i
29/2
29/3
29/4
29/5
Có chia hết hay không?
Ko
Ko
Ko
Ko
=> 29 là số nguyên tố.
(Với N = 45 (()
i
2
3
4
5
6
N/i
45/2
45/3
Có chia hết hay không?
Ko
Có
=> 45 không là số nguyên tố.
Giáo viên giảng giải và vấn đáp 
+ Yêu cầu học sinh đọc lại định nghĩa Thuật toán ( SGK Tr 33) và cho biết thuật toán có những tính chất nào?
+ HS: Trả lời 
+ Gọi HS khác bổ sung và chốt lại
+ Từ đó em hãy phân tích các tính chất của thuật toán Tìm Max 
Giáo viên giảng giải và vấn đáp
GV: Cho bài toán và xác định IO, ý tưởng, xây dựng thuật toán.
Giảng giải kết hợp vấn đáp 
HS : Đưa ra IO của bài toán 
GV: 
+ Nhắc lại lại định nghĩa: Một số nguyên dương N là số nguyên tố nếu nó có đúng hai ước số khác nhau là 1 và chính nó. 
+ Đưa ra ý tưởng của thuật toán 
- HS dựa trên ý tưởng hãy đưa ra thuật toán 
- GV chốt lại thuật toán bằng PP liệt kê 
- GV: ngoài cách liệt kê để biểu diễn thuật toán người ta sử dụng pp sơ đồ khối
- GV giảithích rõ chức năng của các khối 
- Giáo viên cho HS quan sát SGK hoặc mô hình. 
- Học sinh quan sỏt SGK, cho biết cú bao nhiờu khối? 
GV: Sau đó mô phỏng thuật toán bằng một ví dụ cụ thể
+ Lấy ví dụ minh hoạ Với N = 29 và N= 45
IV. Củng cố, bài tập: 
1. Củng cố: 
Các tính chất của thuật toán.