Bài 4. Bài toán và thuật toán

Tiết PPCT: 10
Tuần dạy …… Ngày dạy: …../ …/ …….
§4: BÀI TOÁN VÀ THUẬT TOÁN
MỤC TIÊU: Như tiết 9
NỘI DUNG HỌC TẬP
Khái niệm bài toán, thuật toán, biểu diễn thuật toán
CHUẨN BỊ:
3.1 Giáo viên: Giáo án điện tử, máy chiếu
3.2 Học sinh: SGK, xem bài trước ở nhà.
TIẾN TRÌNH DẠY HỌC:
4.1 Ổn định tổ chức và kiểm diện:
4.2 Kiểm tra miệng:
Câu 1: Hãy nêu khái niệm bài toán trong tin học là gì?
Đáp án: Bài toán là một việc nào đó mà ta muốn máy tính thực hiện
Câu 2: Nêu các yếu tố cần quan tâm khi giải 1 bài toán? Cho ví dụ một bài toán và nêu Input, Output?
Đáp án: Input và Output
Câu 3: Nêu khái niệm thuật toán? Các tính chất của thuật toán?
Đáp án: Như sgk
4.3 Bài mới:
Hoạt động của giáo viên, học sinh
Nội dung bài học
(phần học sinh ghi chép)

Hoạt động 1: Chúng ta đã biết thế nào là thuật toán trong tin học. Bây giờ để hiểu rõ hơn cách diễn tả thuật toán trong tin học như thế nào? Chúng ta sẽ tiếp tục tìm hiểu các cách biểu diễn của thuật toán.
Mục tiêu: giới thiệu cho học sinh biết có hai cách biểu diễn thuật toán : liệt kê và sơ đồ khối.

HS: Nhắc lại thuật toán giải phương trình bậc nhất









( Giới thiệu cách biểu diển dùng sơ đồ khối:
LIỆT KÊ :
Bước 1: Nhập a, b.
Bước 2: Nếu a = 0 thì quay lại bước 1, ngược lại thì qua bước 3.
Bước 3: Gán cho x giá trị -b/a, rồi qua bước 4
Bước 4: Đưa ra kết quả x và kết thúc.



Lưu ý:
Ta cần diễn tả thuật toán bằng một ngôn ngữ sao cho máy tính có thể hiểu và thực hiện được, ngôn ngữ đó gọi là ngôn ngữ lập trình. Kết quả diễn tả thuật toán như vậy gọi là chương trình.


Một số tính chất khác:
Tính hiệu quả: Dựa vào khối lượng tính toán, không gian và thời gian khi thuật toán được thi hành.
Tính tổng quát: Áp dụng được cho mọi trường hợp của bài toán.
Đầu vào/ đầu ra: Mọi thuật toán đều nhận dữ liệu đầu vào, xử lý nó và cho ra kết quả cuối cùng.


- GV: Nêu ra các bước xây dựng một thuật toán
- HS: Ghi chép

- GV: Cho ví dụ: cho 1 dãy số cụ thể: 4 1 2 7 6.
- GV: Với dãy số như vậy ta có thể tìm ra được số lớn nhất là 1, nhưng với dãy số lớn hơn ta cần phải nhờ sự trợ giúp của máy tính
( Nêu thuật toán và chạy từng bước theo thuật toán để kiểm tra tính đúng đắn của thuật toán.
- HS: Nghe giảng













- GV cùng học sinh chạy mô phỏng các bước thực hiện thuật toán.
Biểu diễn thuật toán:
Thể hiện một thuật toán:
Cách 2: Dùng sơ đồ khối quy ước cách biểu diển trên sơ đồ khối:

Qui ước cách biểu diễn trên sơ đồ khối:


Ví dụ:


3.2 Tính chất thuật toán:
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 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 để được 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.


Các bước xây dựng một thuật toán:
Xác định bài toán
Input
Output
Hình thành ý tưởng chính để giải quyết bài toán, lưu ý điểm dừng của bài toán.
Xây dựng thuật toán bằng 1 trong 2 cách:
Liệt kê
Sơ đồ khối
Mô phỏng để kiểm tra tính đúng đắn.


Một số ví dụ về thuật toán:
4.1 Ví dụ bài toán tìm số bé nhất
( 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: Số bé nhất (Min) của dãy số.



( Ý tưởng:
Gọi Min là giá trị nhỏ nhất cần tìm.
Gán Min bằng giá trị đầu tiên của dãy.
Lần lượt so sánh Min với các phần tử tiếp theo trong dãy. Tại mỗi vị trí so sánh:
Nếu Min lớn