Giáo án DMPP_Tin 10

Ngày soạn: 03 /10/2009
Ngày dạy
Lớp dạy



10A1



10A2



10A3



10A4

Tiết 13: BÀI TOÁN VÀ THUẬT TOÁN (Tiếp)
1. MỤC TIÊU
a. Kiến thức.
- Hiểu và thực hiện được việc xây dựng thuật toán của bài toán cụ thể : Bài toán tìm kiếm
b. Kĩ năng:
- Nắm vững cách xây dựng được thuật toán giải bài toán đơn giản bằng sơ đồ khối hoặc liệt kê các bước.
c. Thái độ
- Qua bài giảng, học sinh có hứng thú, say mê với môn học, chú ý nghe giảng, hăng hái phát biểu xây dựng bài
2. PHẦN CHUẨN BỊ CỦA GV và HS
a.Giáo viên.
- Giáo án + đọc tài liệu liên quan + SGK, Máy chiếu (bảng phụ)
b.Học sinh.
- Vở, nháp, SGK, học tìm hiểu bài ở nhà trước khi lên lớp.
3. TIẾN TRÌNH BÀI DẠY
a. Kiểm tra bài cũ (Kiểm tra trong khi thực hiện bài học)
b. Dạy bài mới
*. Đặt vấn đề (1’)
Tìm kiếm là việc thường xảy ra trong cuộc sống, chẳng hạn tìm một cuốn sách nào đó trên giá sách, tìm 01 học sinh trong danh sách lớp. Nói một cách tổng quát là cần tìm một đối tượng cụ thể trong tập các đối tượng cho trước. Vậy với bài toán cần có sự tìm kiếm ta phải có thuật toán như thế nào?
*. Bài mới
Nội dung ghi bảng
Hoạt động của giáo viên
Hoạt động của học sinh

3. Một số ví dụ về thuật toán:
Ví dụ 3: Bài toán tìm kiếm
Bài toán: Cho dãy A gồm n số nguyên a1, a2, …, an và một số nguyên k. Cho 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ố đó.
* Thuật toán tìm kiếm tuần tự:
* Xác định bài toán
+ Input: Dãy A gồm n số nguyên 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.
* ý tưởng :
Tìm kiếm tuần tự được thực hiện một cách tự nhiên, lần lượt từ số hạng thứ nhất, ta so sánh số hạng đang xét với khoá k cho đến khi gặp số hạng trùng với khoá hoặc dãy xét hết không có giá trị nào trùng với k.
* Thuật toán:
a. Cách liệt kê:
- B1: nhập N,các số hạng a1, a2 …a và khoá k.
- B2: i( 1;
- B3: nếu a =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 không có số hạng nào có giá trị bằng k rồi kết thúc ;
- B6: Quay lại bước 3.

b. Sơ đồ khối




Ví dụ mô phỏng:

* Thuật toán tìm kiếm nhị phân:
* Xác định bài toán:
- Input: Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2,..aN và số nguyên k.
- Output: Chỉ số I mà a1 = 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:




* Thuật toán:
a. Cách liệt kê:
- B1. Nhập N, các số hạng a1, a2,..,aN và khoá k;
- B2. Dau (1; Cuoi (N;
- B3. Giua (
;
- B4. Nếu aGiua = k thì thông báo chỉ số Giua, rồi kết thúc;
- B5. Nếu aGiua > k thì đặt Cuoi = Giua -1, rồi chuyển đến bước 7;
- B6. Dau ( Giua + 1;
- B7. Nếu Dau > Cuoi thì thông báo dãy A có