Ngày soạn 23/09/2008
Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 2)
A. MỤC TIÊU
1. Kiến thức:
Biết cách biểu diễn thuật toán bằng sơ đồ khối.
Biết các đặc trưng chính của thuật toán.
2. Kỹ năng:
Biểu diễn được thuật toán bằng sơ đồ khối.
B. PHƯƠNG PHÁP: Nêu và giải quyết vấn đề.
C. CHUẨN BỊ CỦA GIÁO VIÊN VÀ HỌC SINH:
1. Chuẩn bị của GV: SGK
2. Chuẩn bị của HS: SGK
D. TIẾN TRÌNH LÊN LỚP:
1. Ổn định lớp: Kiểm tra sĩ số.
2. Kiểm tra bài cũ:
Nêu khái niệm thuật toán? Xác định Input và Output của bài toán sau: Viết chương trình nhập vào 3 số nguyên dương, cho biết chúng có thể là độ dài 3 cạnh của một tam giác hay không?
Đáp án:
Khái niệm thuật toán: (SGK)
Input: 3 số nguyên dương.
Output: “3 số đó không thể là 3 cạnh một tam giác” hoặc “3 số đó có thể là 3 cạnh của tam giác”
3. Bài mới:
a, Đặt vấn đề:
Hôm trước chúng ta đã biết thế nào là bài toán trong tin học, khái niệm thuật toán, biết cách biểu diễn thuật toán bằng ngôn ngữ liệt kê. Ngoài cách liệt kê thuật toán còn có thể biểu diễn bằng sơ đồ khối, hôm nay chúng ta sẽ tìm hiểu cách biểu diễn thuật toán bằng sơ đồ khối.
b, Triển khai bài:
HOẠT ĐỘNG CỦA THẦY VÀ TRÒ
NỘI DUNG KIẾN THỨC




Hoạt động 1: Biểu diễn bài toán bằng sơ đồ khối.

HS: Nghiên cứu SGK
GV: Vẽ các hình lên bảng và HS nêu chức năng của mỗi hình.













GV: Gọi HS nhắc lại Input, Output của bài toán, ý tưởng bài toán, biểu diễn bài toán bằng ngôn ngữ liệt kê?
HS: Trả lời.





GV: Cho tất cả HS biểu diễn vào giấy nháp. Sau đó gọi 1 HS lên bảng biểu diễn thuật toán.
HS: Lên bảng.
GV: Nhận xét.













GV: Mô phỏng thuật toán với M = 12, N = 8
GV: Giải thích cho HS thuật toán không phải là duy nhất. Tuỳ vào đối tượng mà ta lựa chọn thuật toán thích hợp.
Hoạt động 2: Tính chất của thuật toán
GV: Gọi 1 HS nhắc lại khái niệm thuật toán.
HS: Nhắc lại khái niệm.
GV: Qua khái niệm đó ta thấy thuật toán có tính chất gì?
HS: Trên cơ sở SGK nêu các tính chất.
GV: Yêu cầu HS xác định tính dừng, tính xác định, tính đúng đắn của thuật toán tìm USCLN.
HS: Xác định và trả lời.

Hoạt động 3: Vận dụng để giải một bài toán cụ thể.
GV: Một số như thế nào được gọi là số nguyên tố?
HS: Trả lời.
GV: Cho HS xác định bài toán, ý tưởng và trình bày giải thuật trong vòng 5 phút. Sau đó gọi HS trình bày.
HS: 1 HS xác định bài toán



HS: 1 HS nêu ý tưởng của thuật toán.






HS: Một HS nêu thuật toán bằng cách liệt kê.
GV: Nhận xét và giải thích thêm.
HS: Lên bảng vẽ sơ đồ khối biểu diễn thuật toán.
GV: Nhận xét và giải thích sơ đồ hoạt động của thuật toán.
GV: Mô phỏng việc thực hiện thuật toán trên với N = 29.
2. Khái niệm thuật toán:
* Cách biểu diễn bài toán bằng sơ đồ khối:


Các ký hiệu dùng để biểu diễn thuật toán:
Hình ô van
thể hiện thao tác nhập, xuất dữ liệu.
Hình chữ nhật
thể hiện các phép tính toán.
Hình thoi
thể hiện thao tác so sánh.
Các mũi tên
quy định trình tự thực hiện các thao tác.

Ví dụ: Tìm USCLN của hai số nguyên dương M, N.
* Xác định bài toán:
Input: 2 số nguyên dương M, N
Output: USCLN của M và N.
* Ý tưởng: So sánh M và N
- Nếu M=N thì USCLN ← M
- Nếu M ≠ N:
M>N thì M ← M-N
MCho đến khi nào M = N thì kết thúc.
* Biểu diễn thuật toán bằng sơ đồ khối: