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

Tiết 13
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 2: Vào nội dung bài học
3. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN






8’






















15’



























15’


3. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN :
Ví dụ 3. Bài toán tìm kiếm
Cho dãy A gồm N số nguyên, đôi một 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 chỉ số đó.
Số nguyên k được gọi là khoá tìm kiếm (gọi tắt là khoá).
Ví dụ, cho dãy A gồm các số: 5, 7, 1, 4, 2, 9, 8, 11, 25, 51.
Với khoá k = 2, trong dãy trên có số hạng a5 có giá trị bằng k. Vậy chỉ số cần tìm là i = 5.
Với khoá k = 6 thì không có số hạng nào của dãy A có giá trị bằng k.






Thuật toán Tìm kiếm tuần tự (Sequential Search)
( Xác định bài toán
- Input: Dãy A gồm N số nguyên đôi một khác nhau a1, a2,..., aN và 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.



( Thuật toán
a) Cách liệt kê
Nhập N, các số hạng a1, a2,..., aN và khoá k;
i ( 1;
Nếu ai = k thì thông báo chỉ số i, rồi kết thúc;
i ( i + 1;
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, rồi kết thúc;
Quay lại bước 3.
Ghi chú: Trong thuật toán trên, i là biến chỉ số các số hạng của dãy và nhận giá trị nguyên lần lượt từ 1 đến N + 1.
b) Sơ đồ khối






† Tìm kiếm