: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 4)
A. MỤC TIÊU
1. Kiến thức:
Hiểu được thuật toán tìm kiếm tuần tự.
2. Kỹ năng:
Vận dụng thuật toán để giải quyết các bài toán khác.
3. Thái độ:
Rèn luyện cho HS tư duy logic, làm việc có khoa học.
B. PHƯƠNG PHÁP:
Nêu và giải quyết vấn đề + thuyết trình.
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ũ: Kiểm tra 15 phút.
Hãy mô tả thuật toán giải phương trình bậc 2: ax2+bx+c=0 (a≠0) bằng sơ đồ khối.
Đáp án:


















3. Bài mới:
a, Đặt vấn đề: Tìm kiếm là việc thường xảy ra trong cuộc sống, chẳng hạn cần tìm cuốn sách giáo khoa Tin học 10 trên giá sách, cần tìm một học sinh trong một danh sách lớp học… Nói một cách tổng quát là cần tìm một đối tượng cụ thể nào đó trong tập hợp các đối tượng cho trước thì ta làm như thế nào. Để làm được điều đó chúng ta sẽ tìm hiểu về thuật toán tìm kiếm.
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: Tìm hiểu thuật toán tìm kiếm tuần tự.




HS: Nghiên cứu SGK.
GV: Gọi HS xác định bài toán
HS: Xác định bài toán

GV: Cho ví dụ cụ thể để giải thích cho HS hiểu bài toán.

GV: Gọi HS nêu ý tưởng
HS: Nêu ý tưởng




GV: Gọi 1 HS viết thuật toán bằng cách liệt kê.
HS: Viết thuật toán.
GV: Nhận xét và giải thích thêm.






GV: Gọi 1 HS lên bảng vẽ sơ đồ khối biểu diễn thuật toán.
HS: Vẽ sơ đồ khối.
GV: Nhận xét.

















GV: Mô phỏng thuật toán với dãy số và khoá k cụ thể.

Hoạt động 2: Ứng dụng thuật toán tìm kiếm tuần tự để giải quyết các bài toán khác.

GV: Gọi HS xác định bài toán.
HS: Xác định bài toán.

GV: Gọi HS nêu ý tưởng.
HS: Nêu ý tưởng.
GV: Giải thích cụ thể về ý tưởng.




GV: Gọi 1 HS trình bày thuật toán bằng cách liệt kê.
HS: Trình bày thuật toán bằng cách liệt kê.
GV: Nhận xét.




GV: Gọi 1 HS trình bày thuật toán bằng sơ đồ khối.
HS: Lên bảng vẽ sơ đồ khối.
GV: Nhận xét.



















GV: Mô phỏng thuật toán bằng một dãy số cụ thể.

3. Một số ví dụ về thuật toán:
Ví dụ 4 : Bài toán tìm kiếm.
Bài toán: Cho dãy A gồm N số nguyên khác nhau: a1, a2, .. an và một số nguyên k. Cần biết có hay không chỉ số I (1≤i≤n) mà ai=k. Nếu có hãy cho biết số đó.
* Thuật toán tìm kiếm tuần tự:
- Xác định bài toán:
+ Input: Số nguyên n,k và dãy số a1,a2, ..an
+ Output: Chỉ số i mà ai=k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k.

- Ý tưởng:
Lần lượt so sánh k với các số trong dãy, bắt đầu từ a1 cho đến khi gặp một số hạng bằng k thì kết thúc hoặc đến cuối dãy thì kết thúc.
- Thuật toán:
+ Cách liệt kê:
B1: Nhập n, k và các số hạng a1,a2..an
B2: i←1
B3: Nếu ai=k thì thông báo chỉ số i rồi kết thúc.
B4: i←i+1
B5: Nếu i>n thì thông báo dãy A không có số hạng nào có giá trị bằng k, kết thúc.
B6: Quay lại bước 3.

+ Sơ đồ khối:



















Ví dụ 5: Cho dãy số gồm n phần tử a1,a2..an hãy cho biết trong dãy có bao