Bài giảng Tin Học 7 CTST - Chủ đề 5: Giải quyết vấn đề với sự trợ giúp của máy tính - Bài 13: Thuật toán tìm kiếm

Nội dung text: Bài giảng Tin Học 7 CTST - Chủ đề 5: Giải quyết vấn đề với sự trợ giúp của máy tính - Bài 13: Thuật toán tìm kiếm

1. KHỞI ĐỘNG Có 9 thẻ số, mỗi thẻ được ghi số ở một mặt và mặt còn lại không ghi gì. Dãy thẻ số 26 14 24 18 25 21 19 25 12 Thứ tự 1 2 3 4 5 6 7 8 9 Hình 1. Các thẻ được ghi số ở mặt úp Nêu cách tìm một số bất kì có trong dãy số ghi trên các thẻ.
2. CHỦ ĐỀ 5. GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH BÀI 13. THUẬT TOÁN TÌM KIẾM
3. BÀI 13. THUẬT TOÁN TÌM KIẾM 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ ❖ Bài toán tìm kiếm  Tìm kiếm là việc con người thường xuyên phải thực hiện trong đời sống thực tiễn. Ví dụ: ▪ Tìm số điện thoại trong danh bạ để biết người đã gọi đến. ▪ Tìm bạn sinh cùng tháng với em trong danh sách lớp. ▪ Tìm một bạn trong bức ảnh chụp tập thể lớp.
4. BÀI 13. THUẬT TOÁN TÌM KIẾM 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ ❖ Bài toán tìm kiếm Ví dụ: Hãy tìm một số bất kì có trong dãy số ghi trên các thẻ (các thẻ được ghi số ở mặt úp) Dãy thẻ số 26 14 24 18 25 21 19 25 12 Thứ tự 1 2 3 4 5 6 7 8 9 Em hãy tìm đầu vào, đầu ra của bài toán tìm kiếm trên. Đầu vào: Dãy . số (được ghi trên các thẻ) và số cần cần tìm. Đầu ra: Thông báo vị trí tìm thấy hoặc thông báo không tìm thấy số cần tìm.
5. BÀI 13. THUẬT TOÁN TÌM KIẾM 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ ❖ Bài toán tìm kiếm Ví dụ: Hãy tìm một số bất kì có trong dãy số ghi trên các thẻ (các thẻ được ghi số ở mặt úp) Dãy thẻ số 26 14 24 18 25 21 19 25 12 Thứ tự 1 2 3 4 5 6 7 8 9 Em hãy cho biết cách tìm một số bất kì có trong dãy số ghi trên các thẻ của bài toán trên. ▪ Duyệt (lật) lần lượt từng số và so sánh số cần tìm trong dãy số từ đầu đến cuối. Đó là cách tìm kiếm tuần tự hay còn gọi là thuật toán tìm kiếm tuần tự.
6. BÀI 13. THUẬT TOÁN TÌM KIẾM 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ ❖ Thuật toán tìm kiếm tuần tự
7. BÀI 13. THUẬT TOÁN TÌM KIẾM 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ ❖ Thuật toán tìm kiếm tuần tự Cho các số ghi trên mỗi thẻ. Tìm số 21 trong dãy số bằng thuật toán tìm kiếm tuần tự. Dãy thẻ số 26 14 24 18 15 21 19 25 12 Số 21 được tìm thấy tại vị trí 6. Thứ tự 1 2 3 4 5 6 7 8 9 Lần lặp Số ghi trên thẻ Đúng số cần tìm? Đã hết dãy số? 1 26 Sai Sai 2 14 Sai Sai 3 24 Sai Sai 4 18 Sai Sai 5 15 Sai Sai 6 21 Đúng
8. BÀI 13. THUẬT TOÁN TÌM KIẾM 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ ❖ Thuật toán tìm kiếm tuần tự  Thuật toán tìm kiếm tuần tự thực hiện so sánh lần lượt từ phần tử đầu tiên của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.
9. BÀI 13. THUẬT TOÁN TÌM KIẾM 1. THUẬT TOÁN TÌM KIẾM TUẦN TỰ ❖ Thuật toán tìm kiếm tuần tự Hãy chọn phương án đúng. Tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự. A. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm. B. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm. C. Sắp xếp dãy số theo thứ tự tăng dần. D. So sánh số cần tìm với số ở giữa dãy số.
10. BÀI 13. THUẬT TOÁN TÌM KIẾM 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN Các số được sắp xếp theo thứ tự không giảm Vị trí phần tử ở giữa dãy bằng phần nguyên của (vị trí đầu + vị trí cuối) / 2
11. BÀI 13. THUẬT TOÁN TÌM KIẾM 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN  Việc tìm kiếm áp dụng trên dãy giá trị đã được sắp xếp theo thứ tự. Thuật toán thực hiện so sánh giá trị của phần tử ở giữa dãy với giá trị cần tìm, tiếp tục tìm kiếm trên một nửa dãy có khoảng giá trị mà giá trị cần tìm thuộc vào đến khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.  Vị trí phần tử ở giữa dãy bằng phần nguyên của (vị trí đầu + vị trí cuối) / 2
12. BÀI 13. THUẬT TOÁN TÌM KIẾM 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN  Thuật toán tìm kiếm nhị phân: Bước 1. So sánh giá trị cần tìm với giá trị của phần tử giữa dãy đang xét. Bước 2. Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc. Bước 3. Nếu nhỏ hơn thì xét dãy ở nửa trước, nếu lớn hơn thì xét dãy ở nửa sau. Bước 4. Nếu dãy rỗng thì thông báo không tìm thấy và kết thúc tìm kiếm, không thì qua lại Bước 1.
13. BÀI 13. THUẬT TOÁN TÌM KIẾM 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN Thứ tự 1 2 3 4 55 6 7 8 9 Dãy thẻ số 12 14 15 18 19 21 24 25 26 Lần lặp 1 Lật thẻ ở vị trí giữa dãy ▪ So sánh số cần tìm là 21 với số ghi trên thẻ vừa lật là 19. ▪ Do 21 > 19 nên chỉ cần tìm ở nửa sau của dãy Vị trí ở giữa = (1 + 9) / 2 = 5 Vị trí phần tử ở giữa dãy 10 2 bằng phần nguyên của 0 5 (vị trí đầu + vị trí cuối) / 2 Phần dư Phần nguyên
14. BÀI 13. THUẬT TOÁN TÌM KIẾM 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN Thứ tự 1 2 3 4 5 6 77 8 9 Dãy thẻ số 19 21 24 25 26 Lần lặp 2 Đã bỏ sau lần lặp 1 Lật thẻ ở vị trí giữa dãy ▪ So sánh số cần tìm là 21 với số ghi trên thẻ vừa lật là 24. ▪ Do 21<24 nên chỉ cần tìm ở nửa trước của dãy (là thẻ thứ 6). Vị trí ở giữa = (6 + 9) / 2 = 7 Vị trí phần tử ở giữa dãy 15 2 bằng phần nguyên của 1 7 (vị trí đầu + vị trí cuối) / 2 Phần dư Phần nguyên
15. BÀI 13. THUẬT TOÁN TÌM KIẾM 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN Thứ tự 1 2 3 4 5 66 7 8 9 Dãy thẻ số 19 21 24 25 26 Lần lặp 3 Đã bỏ sau lần lặp 1 Đã bỏ sau lần lặp 2 Lật thẻ lần 3 ▪ Giá trị ghi trên thẻ thứ 6 là 21, bằng với số cần tìm ▪ Kết quả: tìm thấy số 21 trong dãy ở vị trí thứ 6 và kết thúc tìm kiếm.  Khi dãy chỉ còn một thẻ số thì nửa trước (hoặc nửa sau) là dãy rỗng (dãy không có thẻ số nào)
16. BÀI 13. THUẬT TOÁN TÌM KIẾM 2. THUẬT TOÁN TÌM KIẾM NHỊ PHÂN  Dãy sắp xếp theo thứ tự (tăng dần / giảm dần / không giảm / không tăng) giúp việc tìm kiếm nhanh hơn, hiệu quả hơn nhờ sử dụng thuật toán tìm kiếm nhị phân.
17. Thảo luận nhóm Bài tập 1 SGK 75. Hãy sử dụng thuật toán tìm kiếm tuần tự để tìm trong lớp em có bạn cùng tháng sinh theo bảng 2. Lần Tháng sinh của Cùng tháng sinh Đã hết danh sách lặp bạn với em lớp 1 2 3 4 5 6
18. Bài tập 2 SGK 75. Cho bảng danh sách hai số đầu biển số xe của một số tỉnh. Tên tỉnh Hai số đầu của biển số An Giang 67 Bà Rịa – Vũng Tàu 72 Bình Định 77 Cà Mau 69 Điện Biên 27 Gia Lai 81 Khánh Hòa 79 Lai Châu 25 Nam Định 18 Yên Bái 21
19. Bài tập 2 SGK 75. Cho bảng danh sách hai số đầu biển số xe của một số tỉnh. a) Áp dụng thuật toán tìm kiếm tuần tự để tìm tỉnh có 2 số đầu biển số xe 25. Dãy thẻ số 67 72 77 69 27 81 79 25 18 21 Số 25 được tìm thấy tại vị trí 8. Thứ tự 1 2 3 4 5 6 7 8 9 10 Lần lặp Số ghi trên thẻ Đúng số cần tìm? Đã hết dãy số? 1 67 Sai Sai 2 72 Sai Sai 3 77 Sai Sai 4 69 Sai Sai 5 27 Sai Sai 6 81 Sai Sai 7 79 Sai Sai 8 25 Đúng
20. Bài tập 2 SGK 75. Cho bảng danh sách hai số đầu biển số xe của một số tỉnh. b) Áp dụng thuật toán tìm kiếm nhị phân để tìm hai Lần lặp 1 số đầu tiên của biển số xe tỉnh Lai Châu. Thứ tự 1 2 3 4 5 6 7 8 9 10 An Bình Cà Điện Gia Khánh Lai Nam Yên Dãy thẻ BRVT tỉnh Giang Định Mau Biên Lai Hòa Châu Định Bái Lật thẻ ở vị trí giữa dãy ▪ So sánh tên tỉnh cần tìm là Lai Vị trí ở giữa = (1 + 10) / 2 = 5 Châu với tên ghi trên thẻ vừa 11 2 lật là Điện Biên. 1 5 ▪ Vì “L” đứng sau “Đ” trong bảng Phần dư Phần nguyên chữ cái nên tìm ở nửa sau.