Giáo án Tin học 10 - Đoàn Phan Kim Lài - Tiết 11, Bài 4: Bài toán và thuật toán (Tiết 2)

Tiết PPCT: 11
Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (t2)
Ngày soạn: 19/9/2014	 Ngày dạy : 22/09/2014 Tuần : 6 
I. MỤC TIÊU: 
	1. Kiến thức: 	
 - HS cần biết cả hai cách biểu diễn thuật toán là sơ đồ khối và ngôn ngữ liệt kê;
	2. Kĩ năng: 
HS chỉ cần sử dụng được một trong hai cách (sơ đồ khối hoặc ngôn ngữ liệt kê) để mô tả thuật toán..
	3. 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Ị:
	1. Giáo viên: – Giáo án + bảng vẽ các sơ đồ khối.
Tổ chức hoạt động nhóm.
	2. Học sinh: Sách giáo khoa, vở ghi. Đọc bài trước.
III. HOẠT ĐỘNG DẠY-HỌC:
	1. Ổn định tổ chức: Kiểm tra sĩ số lớp. (3’)
	2. Kiểm tra bài cũ: (7’)
Bài toán là gì? Để xác định một bài toán ta cần quan tâm đến các yếu tố nào? 
Xác định Input, Output của bài toán sau : Tinh Chu vi và Diện tích hình vuông cạnh a.	
	3. Bài mới
Nội dung
Hoạt động của Giáo viên
Hoạt động của HS
TG
II. Khái niệm thuật toán:
Thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm.
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,a2,…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.
· Trong toán học, việc giải một bài toán theo qui trình nào?
· HD HS tìm hiểu khái niệm thuật toán là gì?
· GV nhận xét bổ sung và đưa ra khái niệm.
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ưở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.
· HS trả lời:
· Suy nghĩ và đưa ra câu trả lời.
– Là một dãy thao tác
– Sau khi thực hiện dãy thao tác với bộ Input thì cho ra Output.
Input: số nguyên dương N và N số a1, a2, …, aN.
Output: giá trị Max.
- Lắng nghe. Ghi chép
5’
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.
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	
· 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
5’
4. Củng cố: (3’)
	– Nắm được 2 cách biễu diễn Thuật toán liệt kê và sơ đồ khối
5. Dặn dò: (2’)
 	 - Học bài theo bài ghi và sách giáo khoa
- Xem trước 3.Một số ví dụ