CHƯƠNG I: MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA TIN HỌC

Tiết 14
Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)

I). Mục tiêu bài học:

Về kiến thức:
Học sinh sau tiết học sẽ nắm được các vấn đề sau:
Biết khái niệm về bài toán và thuật toán. Đây là 2 khái niệm then chốt để hiểu được các khái niệm khác như chương trình và ngôn ngữ lập trình. Qua đó học sinh hình dung rõ hơn về cách thức hoạt động của máy tính.
Chỉ ra được Input và Output của mỗi bài toán đưa ra.
ví 1 toán.


Về thái độ:
Học sinh sẽ tò mò, thắc mắc về sự kỳ diệu của máy tính điện tử, từ đó gợi niềm say mê môn Tin học.
Hiểu được vai trò quan trọng của Tin học trong cuộc sống xã hội hiện đại.
Ý thức được nếu không có hiểu biết về Tin học thì khó có thể hoà nhập vào cuộc sống hiện đại.

II). Các phương pháp- phương tiện dạy học:

Phương pháp:
Phương pháp chủ yếu là thuyết trình, vấn đáp gợi mở, để học sinh tham gia tích cực vào bài học.

Phương tiện:
1. Chuẩn bị của giáo viên: Sách tin học 10, giáo án, chuẩn bị vài ví dụ cụ thể hơn để hướng dẫn rõ hơn về thuật toán.
2. Chuẩn bị của học sinh : Soạn bài, nghe giảng, đọc tài liệu, chuẩn bị trả lời các câu hỏi phía sau bài học.

III)- Tiến Trình Dạy Học:

+ Ổn định lớp
+ Điểm danh







TG
NỘI DUNG
GIÁO VIÊN
HỌC SINH


Hoạt động : Vào nội dung bài học
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN






8’
























15’
































15’


4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN :
Thuật toán Tìm kiếm nhị phân (Binary Search)
( Xác định bài toán
- Input: Dãy A là dãy tăng gồm N số nguyên đôi một khác nhau a1, a2,..., aN và một số nguyên k;
- 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.
Khi đó, chỉ xảy ra một trong ba trường hợp sau:
Nếu aGiua = k thì Giua là chỉ số cần tìm. Việc tìm kiếm kết thúc.
Nếu aGiua > k thì do dãy A là dãy đã được sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2,..., aGiua–1 (phạm vi tìm kiếm mới bằng khoảng một nửa phạm vi tìm kiếm trước đó).
Nếu aGiua < k thì thực hiện tìm kiếm trên dãy aGiua+1, aGiua+2,..., aN.
Quá trình trên sẽ được lặp lại một số lần cho đến khi hoặc đã tìm thấy khoá k trong dãy A hoặc phạm vi tìm kiếm bằng rỗng.
( Thuật toán
a) Cách liệt kê
Nhập N, các số hạng a1, a2,..., aN và khoá k;
Dau  1, Cuoi  N;
Giua 
;
Nếu aGiua = k thì thông báo chỉ số Giua, rồi kết thúc;
Nếu aGiua > k thì đặt Cuoi = Giua – 1 rồi chuyển đến bước 7;
Dau  Giua + 1;
Nếu Dau > Cuoi thì thông báo dãy A không có số hạng có giá trị bằng k, rồi kết thúc;
Quay lại bước 3.
Ghi chú: Tuỳ thuộc aGiua > k hoặc aGiua < k mà chỉ số đầu hoặc chỉ số cuối của dãy ở bước tìm kiếm tiếp theo sẽ thay đổi. Để thực hiện điều đó, trong thuật toán chỉ sử dụng các biến nguyên tương ứng Dau và Cuoi có giá trị khởi