Bài 4BÀI TOÁN VÀ THUẬT TOÁN (tt)

Chia sẻ: Lotus_0 Lotus_0 | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

98
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. Kĩ năng: – Biết xây dựng thuật toán của một số bài toán đơn giản. Thái độ: – Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài 4BÀI TOÁN VÀ THUẬT TOÁN (tt)

Bài 4 BÀI TOÁN VÀ THUẬT TOÁN (tt) I. MỤC TIÊU: Kiến thức: – 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. Kĩ năng: – Biết xây dựng thuật toán của một số bài toán đơn giản. Thái độ: – Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó. II. CHUẨN BỊ: Giáo viên: – Giáo án + bảng vẽ sơ đồ khối – Tổ chức hoạt động nhóm. Học sinh: SGK, vở ghi. Đọc bài trước. III. HOẠT ĐỘNG DẠY - HỌC: 1. Ổn định tổ chức: Kiểm tra sĩ số lớp. 2. Kiểm tra bài cũ: Hỏi: Nêu ý tưởng thuật toán sắp xếp bằng tráo đổi?
Đáp: Ý tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau thì ta đổi chỗ chúng cho nhau. Việc đó được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa 3. Bài mới Hoạt động 1: Hướng dẫn tim thuật toán giải bài toán Nội dung Hoạt động của Giáo viên Hoạt động của Học sinh Đặt vấn đề: Tìm kiếm là một III. Một số ví dụ: (tt) 3. Ví dụ 3: Bài toán tìm việc thường xảy ra trong cuộc sống. kiếm Cho dãy A gồm N số nguyên khác nhau: a1, a2, …, aN và Cho dãy A gồm: 5, 7, 1, 4, 2, 9,  i = 5 một số nguyên k. Cần biết có 8, 11, 25, 51. Tìm i với ai = 2 ? hay không chỉ số i ( 1 ≤ i ≤ N) mà ai = k. Nếu có hãy cho biết chỉ số đó. a) Thuật toán tìm kiếm tuần tự (sequential search)  Tổ chức các nhóm thảo luận  Các nhóm thảo luận,  Xác định bài toán
- Input: Dãy A gồm N số đưa ra ý kiến nguyên khác nhau a1, a2, …, H. Hãy xác định bài toán? aN và số nguyên k; Đ. + Input: N, a1, a2, - Output: Chỉ số i mà ai = k …, aN, k hoặc thông báo không có số + Output: i hoặc hạng nào của dãy A có giá trị thông báo không có i bằng k.  Ý tưởng: - Tìm kiếm tuần tự là lần lượt từ số hạng thứ nhất, ta  GV hướng dẫn HS tìm thuật so sánh giá trị số hạng đang toán giải bài toán.  Cho các nhóm trình xét với khoá cho đến khi hoặc gặp một số hạng bằng bày ý tưởng. khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá. Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá.  Thuật toán:
* Cách liệt kê: - B1: Nhập N, các số hạng  GV hướng dẫn HS trình bày a1, a2, …, aN và khoá k; thuật toán tìm kiếm bằng cách - B2: i  1;  Các nhóm thảo luận liệt kê. - B3: Nếu ai = k thì thông và đưa ra thuật toán. báo chỉ số i, kết thúc; - B4: i i + 1; - B5: Nếu i >N thì thông báo  i là biến chỉ số và nhận giá trị dãy A không có số hạng nào nguyên lần lượt từ 1 đến N+1. có giá trị bằng k, rồi kết thúc. - B6: Quay lại bước 3. Hoạt động 2: Diễn tả thuật toán tìm kiếm bằng sơ đồ khối * Sơ đồ khối:
Hoạt động 3: Mô phỏng việc thực hiện thuật toán Mô phỏng việc thực hiện thuật k = 2 vµ N = 10 toán với: A 5 7 1 4 2 9 8 11 25 51 + N = 10, k = 2 i12345-- - - - Víi i = 5 th× a5 = 2. Hoạt động 4: Hướng dẫn tìm thuật toán giải bài toán Nội dung Hoạt động của Giáo viên Hoạt động của Học sinh b) Thuật toán tìm kiếm nhị phân (Binary Search)  Nhấn mạnh dãy A là một dãy  Xác định bài toán - Input: Dãy A là dãy tăng gồm tăng. N số nguyên khác nhau a1, a2, H. So sánh 2 bài toán tìm kiếm Đ. Dãy A ở đây là dãy tăng …, aN và một số nguyên k trong 2 thuật toán? - Output: Chỉ số i mà ai = k
hoặc thông báo không có số  GV hướng dẫn HS tìm thuật hạng nào của dãy A có giá tr ị toán giải bài toán. bằng k.  Ý tưởng: Sử dụng tính chất dãy A là dãy tăng, ta tìm cách  Minh hoạ qua việc tra từ điển thu hẹp nhanh phạm vị tìm Cho các nhóm thảo luận việc  Các nhóm trình bày kiếm sau mỗi lần so sánh khoá tra từ điển. Từ đó rút ra thuật cách làm với số hạng được chọn, ta chọn toán. số hạng aGiữa ở " giữa dãy" để so sánh với k, trong đó Giưa =  N  1  2 . Khi đó:   - Nếu aGiưa = k thì Giưa là chỉ số cần tìm. - Nếu aGiưa> k thì do dãy A là dãy đã sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2, …, aGiưa-1 . - Nếu aGiưa < k thì thực hiện tìm kiếm trên dãy aGiưa+1,
aGiưa+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: * 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;    Dau  Cuoi  - B3: Giưa = ;  2   - B4: Nếu aGiưa = k thì thông báo chỉ số Giưa, rồi kết thúc; - B5: Nếu aGiưa > k thì đặt Cuoi = Giưa - 1, rồi chuyển đến bước 7; Giưa +1; - B6: Dau  - B7: Nếu Dau > cuoi 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; - B8: Quay lại bước 3. Hoạt động 5: Mô tả thuật toán bằng sơ đồ khối * Sơ đồ khối Hoạt động 6: Mô phỏng việc thực hiện thuật toán Mô phỏng việc thực hiện thuật toán với N = 10,k= 21 k = 21, N =10 i 1 2 3 4 5 6 7 8 9 1 0 A 2 4 5 6 9 2 2 3 3 3
1 2 0 1 3 Da 1 6 6 u Cu 1 1 7 oi 0 0 Giu 5 8 6 a aGiu 9 3 2 0 1 a Lư 1 2 3 ợt Lượt th ba thì aGiua = k. Vị trí cần tìm là i = Giua = 6. Hoạt động 7: Củng cố các kiến thức đã học  GV cho HS nhận xét điểm  Các nhóm thảo luận và khác biệt cơ bản của 2 thuật trình bày toán 4. BÀI TẬP VỀ NHÀ:
– Mô phỏng việc thực hiện thuật toán với dãy số khác. – Bài 3, 7 SGK. *Rút kinh nghiệm: