Tuần :………………………
Ngày soạn: ……………………
Ngày dạy: ……………………..
Tiết :…………………………….
§ 4: BÀI TOÁN VÀ THUẬT TOÁN
I. MỤC TIÊU:
1. Kiến thức:
- Biết khái niệm bài toán và thuật toán, các tính chất của thuật toán.
- Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước.
2. Kỉ năng:
Xây dựng thuật toán giải 1 số bài toán đơn giản bằng sđk hoặc liệt kê các bước.
3. Thái độ:
II. ĐỒ DÙNG DẠY HỌC:
Chuẩn bị của giáo viên: Giáo án, Sgk
Chuẩn bị của học sinh: Sách giáo khoa, vở ghi
III. HOẠT ĐỘNG DẠY HỌC:
Ổn định tổ chức:Ổn định lớp, kiểm tra sỉ số.
Kiểm tra bài cũ: Không
Nội dung bài mới:
Nội dung
Hoạt động của GV và HS









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.
Vi dụ: Giải phương trình, quản lý thông tin về HS,... là bài toán.
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 từ máy)
Ví dụ 1: Tìm UCLN của hai số M, N.
Input: M, N là 2 số nguyên dương.
Output: UCLN(M, N).
Ví dụ 2: Bài toán giải phương trình bặc hai ax2+bx+c=0
Input: a, b, c là các số thực.
Output: nghiệm x của phương trình.
Ví dụ 3:
Ví dụ 4:
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 xắ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 hai số M, N.
Input: M, N
Output: UCLN(M, N)
. B1: Nhập M, N.
. B2: Nếu M=N thì UCLN=M
. B3: Nếu M>N thì thay M=M-N quay lài bước 2.
. B4: Thay N=N-M quay lại B2.
. B5: Gán UCLN là M. 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 quy định.
Elip: Các thao tác nhập xuất dữ liệu.
Hình thoi: Thao tác so sánh.
Hình chữ nhật: Các phép toán
Mũi tên: quy đình trình tự các thao tác.



Đ


S

Đ
S


 Trong toán học ta nhắc nhiều đến khái niệm “ bài toán” và 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ữ kiện ban đầu phải tìm 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ó khác gì không?
Đứng trước bài toán công việc đầu tiên là gì?
HS: Trả lời câu hỏi.




Ta cần đi xác định Input và Output của bài toán.
Lớp mở SGK trang 30
( với mỗi ví dụ)
Ghi ví dụ lên bảng
Input?
Output?
HS: Đứng tại chỗ trả lời câu hỏi
Ghi câu trả lời lên bảng và giải thích thêm.

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 được chương trình thì cần phải có thuật toán.
Vậy thuật toán là gì?

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.

Đưa ra bài toán UCLN
Ghi thuật toán lên bảng
Lấy ví dụ cụ thể với 2 số(12, 8). Giải thích thuật toán theo từng bước.

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.
Lấy ví dụ tìm UCLN của hai số M, N.
Vẽ sơ đồ thuật toán lên bảng. Chỉ cho HS thấy các bước thực hiện thuật toán được mô tả trong sơ đồ.

Xoá các ghi chú Đ và S trên sơ đồ, yêu cầu 1 HS viết lại và giải thích vì sao?
HS: 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
Lên bảng điền lại các ghi chú và giải thích vì sao lại điền thế?



IV. CỦNG