Giáo án môn Tin học 10 - Bài 4: Bài toán và thuật toán

Giáo viên soạn: Trần Thị Vui Ngày soạn:22/9/2009 	 
I. MỤC TIÊU:
	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.
	Kĩ năng: 
	– Biết xây dựng thuật toán của một số bài toán thông dụng.
	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 + bảng vẽ các sơ đồ khối.
	– Tổ chức hoạt động nhóm.
	Học sinh: Sách giáo khoa, vở ghi. Đọc bài trước.
III. TIẾN TRÌNH BÀI DẠY:
	1. Ổn định tổ chức: Kiểm tra sĩ số lớp.
	2. Kiểm tra bài cũ:
	H. Để xác định một bài toán ta cần quan tâm đến các yếu tố nào? Cho ví dụ.
	Đ. Input, Output.
	3. Giảng bài mới:
Nội dung
Hoạt động của Giáo viên
Hoạt động của Học sinh
III. Một số ví dụ về thuật toán.
1. Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương.
+ Input: N Ỵ Z+
+ 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: ii + 1 rồi quay lại B5
· Tổ chức các nhóm thảo luận
- Nhắc lại định nghĩa số nguyên tố?
- Hãy xác định Input và Output của bài toán này?
- Hãy trình bày ý tưởng
· Hướng dẫn HS tìm thuật toán
· Cho các nhóm tiến hành xây dựng thuật toán bằng phương pháp liệt kê.
· 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.
· Các nhóm thảo luận, trình bày ý kiến.
 N là số nguyên tố, nếu:
	+ N ≥ 2
	+ N không chia hết cho các số từ 2 ® N – 1
hoặc	+ N không chia hết cho các số từ 2 ® 
 + Input: N Ỵ Z+
+ Output: " N là số nguyên tố " hoặc "N không là số nguyên tố"
- Thảo luận trình bày ý tưởng
- Trình bày ý tưởng
· Từng nhóm trình bày thuật toán
b) Sơ đồ khối:
§ĩng
NhËp N
N = 1 
Th«ng b¸o N lµ sè nguyªn tè råi kÕt thĩc
i ¬ 2 
i>
i ¬ i + 1 
N chia hÕt cho i 
N < 4 
Th«ng b¸o N kh«ng lµ sè nguyªn tè råi kÕt thĩc
§ĩng
Sai
Sai
§ĩng
Sai
§ĩng
Sai
Mô phỏng các bước thực hiện thuật toán trên với:
N = 31
· Xét với N = 29 có phải là số nguyên tố không? [] = 5
i
2
3
4
5
6
N/i
29/2
29/3
29/4
29/5
Chia hết?
Không
Không
Không
Không
· Tương tự như trên xét với 
N = 45 có phải là số nguyên tố không?
· Các nhóm thảo luận rồi đưa ra câu trả lời.
 29 là số nguyên tố.
45 không phải là số nguyên tố
4. BÀI TẬP VỀ NHÀ:
	– Mô phỏng việc thực hiện thuật toán xét tính nguyên tố của các số sau: 41; 55
	– Đọc tiếp bài "Bài toán và thuật toán"
IV. RÚT KINH NGHIỆM, BỔ SUNG: