Bài giảng Môn Tin học lớp 10 - tiết 10 - Bài toán và thuật toán (tiết 3)

Ngày soạn: 20/09/2014
Tiết
10
Tên bài dạy
BÀI TOÁN VÀ THUẬT TOÁN (tiết 3)
I. MỤC TIÊU
1. Kiến thức:
Biết các đặc trưng chính của thuật toán.
Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và liệt kê.
Hiểu một số thuật toán thông dụng.
2. Kỹ năng:
Đọc hiểu SGK.
Trình bày, giải quyết vấn đề.
3. Thái độ:	
Nghiêm túc, tập trung, tích cực chủ động. 
II. PHƯƠNG PHÁP VÀ KỸ THUẬT DẠY HỌC
Phương pháp vấn đáp gợi mở, thảo luận.
III. CHUẨN BỊ
1. Chuẩn bị của giáo viên: SGK, giáo án, mô phỏng bằng PowerPoint. 
2. Chuẩn bị của học sinh: Học bài cũ, đọc trước SGK. 
IV. TIẾN TRÌNH DẠY HỌC
1. Kiểm tra bài cũ: Không
2. Bài mới:
Hôm nay chúng ta cùng tìm hiểu một số tính chất của thuật toán và tìm hiểu về ví dụ tìm giá trị lớn nhất của một dãy số nguyên.
Nội dung kiến thức
Hoạt động của giáo viên và học sinh 
Hoạt động 1: Một số tính chất của thuật toán
e. Tính chất của thuật toán
- Tính dừng
- Tính xác định
- Tính đúng đắn
GV: Yêu cầu HS đọc SGK và nêu câu hỏi:
Nêu các tính chất của thuật toán. 
Chứng minh thuật toán giải phương trình ax + b = 0 có 3 tính chất đó.
HS: Suy nghĩ trả lời:
- Tính dừng: Thuật toán kết thúc sau 1 lần thực hiện (4 bước).
- Tính xác định: Thứ tự các bước được mặc định là tuần tự. Kết quả phép so sánh ở bước 2, 3, 4 xác định duy nhất bước tiếp theo cần thực hiện.
- Tính đúng đắn: Sau khi thuật toán kết thúc, ta tìm được nghiệm của phương trình (Output).
Hoạt động 2: Tìm hiểu thuật toán Tìm giá trị lớn nhất của một dãy số nguyên
3. Một số thuật toán thông dụng
a. Tìm giá trị lớn nhất của một dãy số nguyên
Xác định bài toán:
Input: số nguyên dương N và dãy N số nguyên a1, a2, …, aN.
Output: max{ a1, a2, …, aN}.
Thuật toán viết bằng ngôn ngữ tựa Pascal:
B1: Nhập N và dãy a1, a2, …, aN;
B2: Max := a1;
B3: Cho i chạy từ 2 đến N; với mỗi ai, nếu ai > Max thì gán lại giá trị Max := ai;
B4: Đưa ra giá trị Max rồi kết thúc.
Mô phỏng thuật toán:
N = 5.
I
1
2
3
4
5
Dãy số
3
5
4
8
7
Max
3
5
5
8
8
GV: Giới thiệu bài toán: Tìm cân nặng quả cam nặng nhất trong rổ.
HS: Hoạt động cá nhân trong 3 phút. 
Bài toán cho gì? Bài toán cần gì?
Nêu cách tìm cân nặng quả cam nặng nhất.
Khi nào thì việc chọn cam kết thúc?
GV: Minh họa bài toán Chọn cam trên PP.
GV: Nêu bài toán Tìm giá trị lớn nhất của một dãy số nguyên.
HS: Làm việc cá nhân trong vòng 3 phút. 
Input, Ouput của bài toán. 
Ý tưởng giải bài toán. 
Liên hệ với bài toán Chọn cam.
GV: Giải thích thêm về ý tưởng giải bài toán.
HS: Làm việc cá nhân trong vòng 5 phút (có thể thảo luận với HS bên cạnh). Viết các bước giải bài toán theo cách hiểu của mình.
GV: Gọi 1HS lên bảng viết thuật toán. Các HS khác tiếp tục làm vào vở nháp. Nếu HS không làm được, GV chiếu thuật toán lên và nêu yêu cầu:
Max và i là gì? 
Nêu ý nghĩa của bước 3.
Chứng minh tính dừng của thuật toán.
HS : Suy nghĩ trong vòng 3 phút.
GV : Gợi ý, giúp đỡ HS giải quyết các vấn đề.
GV : Mô phỏng thuật toán bằng PP.
HS : 1-2 HS lên bảng mô phỏng thuật toán với số N và các số ai tự cho.
HS : Về xem thêm thuật toán trong SGK (liệt kê, SĐK).
3. Củng cố:
HS nắm 3 tính chất của thuật toán.
HS nắm bài toán Tìm giá trị lớn nhất của một dãy số nguyên:
- Xác định bài toán.
- Ý tưởng giải bài toán.
- Thuật toán.
- Mô phỏng thuật toán.
4. Dặn dò, hướng dẫn học sinh học tập ở nhà:
HS học bài cũ, đọc Bài toán tìm kiếm và Thuật toán tìm kiếm tuần tự (trang 40 SGK), soạn:
Xác định bài toán.
Ý tưởng của thuật toán tìm kiếm tuần tự.
Khóa k trong thuật toán là gì?
Khi nào thì thuật toán dừng?
Bài tập về nhà: biểu diễn thuật toán của các bài toán sau:
- Tìm giá trị bé nhất của một dãy số nguyên.
V. RÚT KINH NGHIỆM TIẾT DẠY