Tin học 8 - Bài 4: Bài toán và thuật toán

Tuần 5,6	Ngày soạn: 04/09
Tiết 10,11,12	Ngày dạy:
§4. BÀI TOÁN VÀ THUẬT TOÁN 
I. Mục tiêu
1. Kiến thức
- Học sinh biết khái niệm về Bài toán và thuật toán, các tính chất của thuật toán
- Học sinh chỉ ra được Input và Output của mỗi bài toán đưa ra.
2. Kỹ năng
 - Hiểu và nhận biết được Input và Output trong mỗi bài toán. 
3. Thái độ
 - Chú ý nghe giảng, hăng hái phát biểu ý kiến.
 - Có thái độ học tập nghiêm túc. 
II. Chuẩn bị của giáo viên và học sinh
 1. Chuẩn bị của giáo viên: SGK, Giáo án, Tài liệu tham khảo.
 2. Chuẩn bị của học sinh: SGK, vở ghi
III. Phương pháp: 
 Hướng dẫn giảng giải, minh họa trực quan, nêu câu hỏi để học sinh thảo luận trả lời.
 Hoạt động nhóm, hoạt động cá nhân
IV. Hoạt động dạy - học
 1. Ổn định tổ chức
 2. Kiểm tra bài cũ: 
 3. Nội dung bài mới
Hoạt động của thầy và trò
Nội dung
GV: Đặt vấn đề: Để viết được chương trình cho máy tính thực hiện ta cần biết thế nào là thuật toán và bài toán. Đó chính là nội dung của bài học hôm nay.
GV: Trong toán học "Bài toán" được hiểu là những việc mà con người cần phải thực hiện sao cho từ những dữ liệu đã có phải tìm ra kết quả hay chứng minh một kết quả nào đó. Vậy khái niệm "Bài toán" trong Tin học có gì khác không ?
HS: Trả lời.
GV: Trong nhà trường có phần mềm quản lý học sinh : Nếu ta yêu cầu đưa ra những học sinh có điểm trung bình từ 7 trở lên, đó là bài toán. Hay đơn gian hơn yêu cầu máy tính cho ra kết quả của một phép tính nhân, chia,... Đó cũng là bài toán. Vậy bài toán là gì ?
HS: Suy nghĩ và trả lời.
GV: Để giải được một bài toán thì công việc đầu tiên ta cần làm là gì ?
HS: Cụng việc đầu tiên là đi xỏc định đâu là dữ kiện đó cho và đâu là cái cần tìm.
1. Bài toán
* Khái niệm: Bài toán là những việc mà con người muốn máy tính thực hiện.
* Các yếu tố: Khi máy tính giải bài toán cần quan tâm đến 2 yếu tố:
- Input (Thông tin đưa vào máy)
- Output (Thông tin muốn lấy ra từ máy)
GV: Ta cần đi xác định đầu vào (Input) và đầu ra (Output) của bài toán. Input là thông tin được đưa vào máy, Output là thông tin cần lấy ra khỏi máy.
nput của bài toàn là gì ?
Output của bài toàn là gì ?
HS: Đứng tại chỗ trả lời câu hỏi
GV: Cho học sinh lấy thêm ví dụ và phân tích đâu là Input và đâu là Output.
HS: Trả lời.
GV: Muốn máy tính đưa ra được Output từ Input đã cho thì cần phải có chương trình, mà muốn viết chương trình thì cần phải có thuật toán. Vậy thuật toán là gì ?
HS: Trả lời.
GV: Giải thích thêm về các khái niệm như: Dãy hữu hạn các lệnh, sắp xếp theo một trình tự nhất định.
HS: Lắng nghe và ghi nhớ.
GV: Đưa ra ví dụ tìm UCLN của 2 số M và N. Xác định Input và Output của bài toán.
HS: Đứng tại chỗ xác định Input và Output
GV: Ghi thuật toán lên bảng 
GV: Lấy ví dụ cụ thể với 2 số (12,8) và giải thích thuật toán qua từng bước:
B1: Nhập M=12, N=8 --> M>N
B2: M=12-8=4, N=8-->N>M
B3: M=4, N=8-4=4 --> M=N
 => UCLN(M,N)=4
GV: Cách viết thuật toán theo từng bước như trên gọi là cách liệt kê, còn có cách làm khác đó là dùng Sơ đồ khối.
HS: Lắng nghe.
GV: Lấy lại ví dụ tìm UCLN của 2 số M,N
GV: Vẽ sơ đồ thuật toán lên bảng. Chỉ cho học sinh thấy các bước của thuật toán được mô tả trong sơ đồ.
HS: Ghi lại sơ đồ thuật toán và hình dung ra các bước giải của thuật toán.
GV: Xoá các ghi chú Đ và S trên sơ đồ, yêu cầu 1 học sinh viết lại và giải thích vì sao ?
HS: Lên bảng điền lại các ghi chú và giải thích vì sao lại điền như thế.
2. Thuật toán
- Khái niệm 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 đó, từ Input của bài toán này ta nhận được Output cần tìm.
- Tác dụng của thuật toán: Dùng để giải một bài toán.
- Ví dụ: 
Thuật toán tìm UCLN của 2 số M, N.
* Xác định bài toán
 + Input: M, N
 + Ontput: UCLN(M, N)
* ý tượng: - Nếu M = N thì gán UCLN=M
 - Nếu M > N thì gán M = M - N
 - Nếu M < N thì gán N = N - M
* Thuât toán: (Theo cách liệt kê từng bước)
-B1: Nhập M, N
-B2: Nếu M = N thì UCLN = M
-B3: Nếu M > N thì thay M= M - N, 
 rồi quay lại B2.
-B4: Nếu M<N thì thay N = N - M 
 rồi quay lại B2
-B5: Gán UCLN là M và kết thúc.
Ngoài ra thuật toán còn được diễn tả bằng sơ đồ khối với các qui định:
- Hình elip: Các thao tác nhập, xuất dữ liệu
- Hình thoi: Các thao tác so sánh
- Hình chữ nhật: Các phép toán
- Mũi tên: Qui định trình tự các thao tác
* Thuật toán được mô tả bằng sơ đồ khối:
GV: Giới thiệu các tính chất của thuật toán.
HS: Lắng nghe và ghi nhớ.
Nhập M và N
M=N ?
M>N ?
Đưa raUCNN là M
 và Kết thúc
N <= N - M
M <= M - N
Đúng
Đúng
Sai
Sai
 Các tính chất của thuật toán:
+ Tính dừng:
+ Tính xác định:
 + Tính đúng đắn
4. Củng cố:
- Khái niệm bài toán trong tin học
- Các yếu tố cần xác định trong việc giải bài toán
- Thuật toán: Cách giải bài toán
- Diễn tả thuật toán
5. Bài về nhà
 - Nêu thêm 5 ví dụ về bài toán trong tin học
 - Làm lại bài tập ví dụ đã chữa, lấy thêm một số ví dụ khác tương tự.
 - Đọc trước các mục còn lại để giờ sau học tiếp bài : Bài toán và thuật toán.
Rút kinh nghiệm: