BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)

Bài: 4 - tiết: 11
Tuần dạy: Ngày dạy:




Mục tiêu:
Kiến thức:
HS biết: Biết khái niệm bài toán và thuật toán, các đặc trưng chính của thuật toán.
HS hiểu:
Hiểu 1 số thuật toán thông dụng.
Hiểu cách biểu diễn thuật toán bằng ngôn ngữ liệt kê (dùng ngôn ngữ tự nhiên).
Mô tả được thuật toán giải một số bài toán đơn giản bằng ngôn ngữ liệt kê.
Kỹ năng:
Xây dựng được thuật toán giải một số bài toán đơn giản bằng sơ đồ khối hoặc liệt kê.
Thái độ: Có ý thức sử dụng các kiến thức trên góp phần phát triển tư duy khi giải quyết các vấn đề trong khoa học cũng như trong đời sống.
Trọng tâm:
Xây dựng được thuật toán giải một số bài toán đơn giản .
Chuẩn bị :
Giáo viên: Bảng
3.2 Học sinh:
Xem trước của bài 4 : “ Bài toán và thuật toán”
Sách giáo khoa.
Tiến trình:
Ổn định tổ chức và kiểm diện:
Kiểm tra miệng:
Câu 1: Hãy xây dựng thuật toán tìm UCLN của hai số M, N.
Trả lời:
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.
Bài mới:

HOẠT ĐỘNG CỦA GV VÀ HS
NỘI DUNG BÀI HỌC

Hoạt động 1: Vào bài


GV: Hãy xác định I/O của bài toán?
HS: Lên bảng viết.

HS: Có 5 phút nghiên cứu SGK, sau đó lên bảng trình bày thuật toán bằng phương pháp liệt kê.
Hướng dẫn HS hoàn thành thuật toán.











HS: Một HS khác lên bảng dựa vào thuật toán băng phương pháp liệt kê vẽ sơ đồ khối và trình bày trước lớp.















GV: Qua định nghĩa trên, ta thấy thuật toán có các tính chất sau:





1. Bài toán:
2. Thuật toán:
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên.
* Xác định bài toán:
- Input: Số nguyên dương N và dãy N số nguyên a1,...,aN.
- Output: Giá trị lớn nhất Max của dãy số.
* Ý tưởng: - Khởi tạo giá trị Max = a1.
- Lần lượt 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.
* Thuật toán:
- Liệt kê:
B1: Nhập N và dãy a1,...,aN;
B2: Max
a1, i
2;
B3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc;
B4:
4.1. Nếu ai>Max thì Max
ai;
4.2. i
i + 1 rồi quay lại bước 3;
- Sơ đồ khối:

















* Các tính chất của thuật toán:
- Tính dừng: Thuật toán phải kết thúc sau 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à xác định đúng một thao tác cần 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ủng cố:
Câu 1: Tính xác định của thuật toán có nghĩa là gì?
Đáp án câu 1: 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à xác định đúng một thao tác cần thực hiện tiếp theo.
Hướng dẫn học sinh tự học:
Đối với bài học ở tiết này: Làm các bài tập trong SGK
Đối với bài học ở tiết học tiếp theo: Xem phần còn lại của bài 4.
Rút kinh nghiệm :
Cần rút kinh nghiệm về :