Tin 10 tuan 07

Giaùo aùn Tin 10

Tuần: 07

Tiết: 13

Ngày soạn:24/09/2012

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



I. Mục tiêu

Học sinh cần nắm:

1. Kiến thức :

- Biết khái niệm bài toán và thuật toán, các tính chất của thuật toán.

- Hiểu cách biễu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước;

- Hiểu một số thuật toán thông dụng.

2.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ê các bước.

3. Thái độ: Học sinh cần nhận thức được tầm quan trọng của môn học, vị trí của môn học

trong hệ thống kiến thức phổ thông và những yêu cầu về mặt đạo đức trong xã hội tin học

hóa.

II. Phương pháp

-Phương pháp của thầy: Gợi mở, vấn đáp, thảo luận.

-Phương pháp của trò: Trả lời vấn đáp, nghe, ghi chép.

III. Phương tiện dạy học

-Chuẩn bị của giáo viên: SGK, SGV, Computer và projector (nếu có).

-Chuẩn bị của học sinh: Sách giáo khoa, đọc trước bài ở nhà.

III. Tiến trình bài học:

1. Ổn định lớp:Kiểm tra sĩ số.

2. Kiểm tra bài cũ: không có

3.Trình bày bài mới:

HOẠT ĐỘNG CỦA GV HOẠT ĐỘNG CỦA HS NỘI DUNG

- Trong cuộc sống chúng

ta, thường xảy ra việc tìm

kiếm. Chảng hạn: tìm

kiếm tên của 1 học sinh

trong 1 lớp, tìm 1 quyển

sách trong thư viện. Điều

quan tâm ở đây là tìm

kiếm như thế nào?

- Ví dụ: 5 7 1 4 2

+ k = 2  I = ?

+ k = 6  I = ?

- Nêu các bước giải bài

toán?

- Ghi bài.

- Cho ví dụ tìm kiếm 1

đối tượng nào đó.

- Suy nghỉ

+ I = 5

+ Không có i

* Xác định bài toán:

Input:

Output:

* Ý tưởng.

* Thuật toán.

* Thuật toán tìm kiếm tuần tự

(Sequential sort)

Bài toán: Cho dãy A gồm N số nguyên

khác nhau: a1,a2,…,aN và mpptk số nguyên

k. Cần biết hay không chỉ số I (1≤ i ≤ N )

mà ai = k. Nếu có hãy cho biết chỉ số đó.

Các bước giải bài toán: có 3 bước.

* Xác định bài toán:

Input: Dãy A gồm N số nguyên a1,a2,

…,aN và khóa k.

Output: chỉ số I mà ai = k.hoặc không có

số hạng nào.

* Ý tưởng. Tìm kiếm tuần tự một cách tự

nhiên. Lần lượt từ số hạng thứ 1, so sánh

các số hạng đến khi gặp số hạng bằng

khóa, hoặc không có giá trị nào bằng

Trang 32