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

Tiết 10:	 Ngày soạn: 24/09/2008
Bài 4: Bài toán và thuật toán
I- Mục tiêu:
	1. Về kiến thức:
- Biết cách diễn tả thuật toán bằng một trong hai phương pháp: Liệt kê và sơ đồ khối.
- Nắm dược các tính chất cơ bản của thuật toán.
	2. Về kĩ năng:
- Diễn tả được thuật toán theo cách liệt kê hoặc bước đầu thể hiện được thuật toán bằng sơ đồ khối.
- Hiểu và diễn tả được một số bài toán cơ bản.
	3. Về thái độ:
Rèn luyện lòng say mê nghiên cứu tìm hiểu và tư duy khoa học. 
Tác phong làm việc độc lập sáng tạo, nâng cao lòng say mê học tập bộ môn.
II- Chuẩn bị:
	1. Giáo viên:
- Chuẩn bị tranh vẽ, máy tính và một số bài toán áp dụng để rèn luyện kỹ năng biểu diễn thuật toán.
	2. Học sinh:
- Sách giáo khoa và các ví dụ trong sách giáo khoa.
III- Hoạt động dạy học:
Hoạt động của giáo viên
Hoạt động của học sinh
ổn định lớp:
Bài cũ:
? Thuật toán là gì? Nêu khái niệm bài toán trong tin học cho ví dụ và xác định Input và output của bài toán?
Bài mới:
Hoạt động 1
Tìm hiểu cách biểu diễn thuật toán bằng cách liệt kê:
- Giáo viên đưa ra ví dụ trong sách giáo khoa, yêu cầu học sinh nghiên cứu kỹ và trả lời các câu hỏi sau:
? Hãy xác định bài toán?
? Từ Input và output của bài toán, hãy trình bày ý tưởng của thuật toán để tìm output từ input đã cho?
? Từ ý tưởng của thuật toán em hãy xây dựng thuật toán dưới dạng liệt kê?
@ Ghi chú:
- Trong thuật toán trên, i là biến chỉ số và có giá trị nguyên dương từ 2 đến N + 1.
- !: Trong thuật toán trên được hiểu là gán giá trị của biểu thức bên phải cho biến ở bên trái mũi tên.
Ví dụ: i ! i + 1 hiểu là tăng i lên một giá trị trước đó.
Cách xây dựng thuật toán như trên gọi là cách liệt kê.
Thuyết trình: Ngoài cách diễn tả thuật toán bằng liệt kê, còn có cách khác để diễn tả thuật toán bằng trực quan đó là sử dụng sơ đồ khối.
Hoạt động 2: 
Tìm hiểu cách diễn tả thuật toán bằng sơ đồ khối:
F Một số quy ước dùng một số khối để diễn tả thuật toán:
Hình thoi: : Thể hiẹn thao tác so sánh
Hình chữ nhật: Thể hiện các phép tính toán
Hình Oval: thể hiện thao tác xuất, nhập dữ liệu.
Các mũi tên: quy định trình tự thực hiện các thao tác.
F Yêu cầu học sinh nghiên cứu sách giáo khoa và trả lời các câu hỏi sau:
? Dựa vào thuật toán liệt kê trên em hãy trình bày lại dưới dạng sơ đồ khối?
* Dựa vào sơ đồ khối giáo viên mô phỏng thuật toán trên với dãy số: N = 6
Ai
3
8
9
7
1
10
i
2
3
4
5
6
7
Max
3
8
9
9
9
10
? Hãy mô phỏng thuật toán bằng dãy số:
N = 11 và dãy số: 8, 5, 6 , 9, 3, 7, 6, 1, 4, 2, 11, 6
Gọi học sinh lên bảng trình bày.
? Qua ví dụ trên và định nghĩa của thuật toán, hãy cho biết các tính chất của thuật toán là gì?
Trên cơ sở đó giáo viên chốt lại kiến thức:
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 để 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.
J Thuyết trình: Với thuật toán tìm số lớn nhất của dãy số đã xét:
G Tính dừng: Vì giá trị i mỗi lần tăng lên một đơn vị nên sau N lần thì i > N khi đó kết quả so sánh ở bước 3 xác định việc đưa ra giá trị Max rồi kết thúc.
Yêu cầu học sinh xác định hai tính chất còn lại? 
C Giáo viên nhận xét và chốt lại kiến thức bài học
HS báo cáo sĩ số,
K Suy nghĩ và trả lời
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên.
K Nghiên cứu sách giáo khoa và thảo luận, suy nghĩ và trả lời:
a) 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: Giá trị lớn nhất Max của dãy số.
@ Thảo luận và trả lời:
b) ý tưởng bài toán:
- Khởi tạo giá trị Max = a1;
- Lầ 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.
@ Thảo luận và trả lời:
c) Thuật toán dạng liệt kê:
Bước 1: Nhập N và dãy số a1, a2,, aN;
Bước 2: Max ! a1; i ! 2;
Bước 3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc;
Bước 4:
 Bước 4.1: nếu ai > Max thì max ! ai;
 Bước 4.2: i ! i + 1 rồi quay lại bước 3
K Nghe giảng và ghi bài
K Nghe giảng và ghi bài
K Nghiên cứu sách giáo khoa và thảo luận, suy nghĩ và lên bảng trình bày:
Nhập N, dãy a1,., an
Max ! a1, i ! 2
i > N ?
đưa ra max rồi kt
ai >max?
Max ! ai
i ! i +1
Đ
S
Đ
S
Suy nghĩ và lên bảng trình bày.
@ Thảo luận và trả lời:
Tính xác định
Tính đúng đắn
Tính dừng sau hữu hạn thao tác.
Nghe giảng và ghi bài.
Nghe giảng và ghi bài.
@ Thảo luận và trả lời:
A Tính xác định: Thứ tự thực hiện các bước của thuật toán mặc định là tuần tự nên sau bước 1 sẽ là bước 2, sau bước 2 sẽ là bước 3. Kết quả so sánh ở bước 3 và bước 4 đều xác định duy nhất bước tiếp theo cần thực hiện
B Tính đúng đắn: Vì thuật toán so sánh Max với từng số hạng của dãy số và thực hiện Max ! ai nếu ai > Max nên sau khi so sánh hết N số hạng của dãy số thì Max là giá trị lớn nhất.
IV- Đánh giá cuối bài:
Nhắc lại những nội dung đã học:
Khái niệm thuật toán và các tính chất của thuật toán.
Cách biểu diễn thuật toán bằng liệt kê và bằng sơ đồ khối.
Biết cách mô phỏng thuật toán thông qua ví dụ cụ thể.
Bài tập áp dụng:
Câu 1: Tìm giá trị nhỏ nhất của dãy số nguyên N số, biểu diễn bằng sơ đồ khối và bằng cách liệt kê. Mô phỏng thuật toán với N = 10.
IV- Rút kinh nghiệm: