Giáo án môn Tin học khối 10 - Tiết 11, 12 - Bài 4: Bài toán và thuật toán

Tiết dạy :	11 Chương I: MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA TIN HỌC
Ngày soạn: 	07/2009	 Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)
Ngày dạy : 	07/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 Phương Pháp dạy học
Thuyết trình, hỏi đáp, đặt vấn đề, so sánh
IV. HOẠT ĐỘNG DẠY HỌC:
	1. Ổn định tổ chức: Kiểm tra sĩ số lớp.
	2. Kiểm tra bài cũ:
	 Hỏi: Để 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ụ.
	Đáp: Input, Output.
	3. Giảng bài mới:
TL
Nội dung
Hoạt động của Giáo viên
Hoạt động của Học sinh
Hoạt động 1: Hướng dẫn tìm thuật toán giải bài toán: "Tìm GTLN của một dãy số nguyên"
15
II. Khái niệm thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên cho trước.
· Xác định bài toán:
+ Input: 
	– số nguyên dương N.
	– N số a1, a2, , aN.
+ Output: giá trị Max.
· Thuật toán: (Liệt kê)
B1: Nhập N 
	và dãy a1, , 	aN
B2: Max ¬ a1; i ¬2
B3: Nếu i > N thì đưa ra giá 	trị Max và kết thúc.
B4: Nếu ai > max 
	thì Max ¬ ai 
B5: i ¬ i+1, quay lại B3.
· Tổ chức các nhóm thảo luận
H. Hãy xác định Input và Output của bài toán?
· Hướng dẫn HS tìm thuật toán (có thể lấy VD thực tế để minh hoạ: tìm quả cam lớn nhất trong N quả cam)
· Ý tưởng: 
– Khởi tạo giá trị Max = a1.
– Lần lượt với 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.
· GV giải thích các kí hiệu
· Các nhóm đưa ra kết quả
Đ. 
Input: – số nguyên dương N.
	– N số a1, a2, , aN.
Output: giá trị Max.
· Các nhóm thảo luận và trình bày ý tưởng.
Hoạt động 2: Hướng dẫn diễn tả thuật toán bằng sơ đồ khối
10
· Sơ đồ khối:
 thể hiện thao 	tác so sánh.
 thể hiện các phép 	tính toán.
 thể hiện thao tác 	nhập, xuất dữ liệu.
 qui định trình tự thực hiện các thao tác.
Hoạt động 3: Mô phỏng việc thực hiện thuật toán
10
Mô phỏng các bước thực hiện thuật toán trên với 
N = 11 và dãy A: 5, 1, 4, 7, 6, 3, 15, 8, 4, 9, 12.
· GV minh hoạ việc thực hiện thuật toán với một dãy số cụ thể.
· HS theo dõi, tham gia nhận xét kết quả.
Dãy số
5
1
4
7
6
3
15
8
4
9
12
i
2
3
4
5
6
7
8
9
10
11
12
Max
5
5
5
7
7
7
15
15
15
15
15
Hoạt động 4: Củng cố các kiến thức đã học
7
· Tính chất thuật toán: 
– Tính dừng: thuật toán phải kết thúc sau 1 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 1 thao tác thì hoặc là kết thúc hoặc thực hiện 1 thao tác kế tiếp.
– Tính đúng đắn: sau khi kết thúc phải nhận được Output.
· Hướng dẫn HS nhận xét các tính chất của thuật toán.
· Cho HS nêu lại các cách diễn tả thuật toán
· HS nhận xét qua VD trên
· HS nhắc lại
4. BÀI TẬP VỀ NHÀ:
	– Mô phỏng việc thực hiện thuật toán tìm GTLN với N và dãy số khác.
	– Bài 2, 4, 5 SGK.
	– Đọc tiếp bài "Bài toán và thuật toán"
V. RÚT KINH NGHIỆM, BỔ SUNG:
Tiết dạy:	12 	 Chương I: MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA TIN HỌC
Ngày soạn:	 Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)
Ngày dạy:
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 Phương Pháp dạy học
Thuyết trình, hỏi đáp, đặt vấn đề, so sánh
IV. HOẠT ĐỘNG DẠY HỌC:
	1. Ổn định tổ chức: Kiểm tra sĩ số lớp.
	2. Kiểm tra bài cũ:
	 Hỏi: Nêu các cách diễn tả thuật toán?
	Đáp: Liệt kê, Sơ đồ khối.
	3. Giảng bài mới:
TL
Nội dung
Hoạt động của Giáo viên
Hoạt động của Học sinh
Hoạt động 1: 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
20
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. 
· Ý 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
H. Nhắc lại định nghĩa số nguyên tố?
H. Hãy xác định Input và Output của bài toán này?
· 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ố"
· Từng nhóm trình bày thuật toán
Hoạt động 2: Hướng dẫn mô tả thuật toán bằng sơ đồ khối
10
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 ht 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
Hoạt động 3: Mô phỏng việc thực hiện thuật toán – Củng cố
10
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"
V. RÚT KINH NGHIỆM, BỔ SUNG: