NHIỆT LIỆT CHÀO MỪNG �CÁC EM ĐẾN VỚI TIẾT HỌC MỚI!
Tin học định hướng khoa học máy tính 11
TRÒ CHƠI LẬT THẺ
Giả sử có một bộ thẻ, trên mỗi thẻ in một số bất kì. Các thẻ được xếp úp mặt xuống bàn theo thứ tự tăng dần của các số ghi trên thẻ. Người chơi mỗi lần chỉ được lật một thẻ để xem giá trị số in trên đó. Nếu giá trị số in trên thẻ lật lên bằng số K cho trước thì trò chơi kết thúc. Bạn An đã chơi bằng cách lật lần lượt từng thẻ từ đầu đến cuối.
TRÒ CHƠI LẬT THẺ
Theo em, An có chắc chắn xác định được thẻ nào in số K không? Em có cách nào xác định được thẻ in số K nhanh hơn An không?
BÀI 19: BÀI TOÁN TÌM KIẾM
NỘI DUNG BÀI HỌC
1. Bài toán tìm kiếm trên thực tế
2. Tìm kiếm tuần tự
3. Tìm kiếm nhị phân
BÀI TOÁN TÌM KIẾM TRÊN THỰC TẾ
01
Chia lớp thành 6 nhóm, thực hiện Hoạt động 1
Với các bài toán tìm kiếm sau, hãy thảo luận về miền dữ liệu và khả năng các kết quả có thể tìm được của bài toán:
Nhóm 1, 4
Tìm hiểu Bài toán 1. Em cần tìm hình ảnh các cây hoa hồng đẹp trên Internet để đưa vào bài trình bày về cách trồng hoa.
Nhóm 2, 5
Tìm hiểu Bài toán 2. Em cần tìm một tệp văn bản có tên bai-hoc-1.docx trên máy tính của em những đã lâu rồi chưa sử dụng lại.
Nhóm 3, 6
Tìm hiểu Bài toán 3. Em cần tìm 5 bạn học sinh có điểm trung bình các bài thi cao nhất trong kì thi Olympic Tin học năm 2020 của thành phố Hà Nội.
Câu hỏi gợi ý tìm hiểu:
Em cần tìm hình ảnh các cây hoa hồng đẹp trên Internet để đưa vào bài trình bày về cách trồng hoa.
Miền dữ liệu:
Là tất cả các ảnh có trên máy tính kết nối mạng Internet
Kết quả:
Là các ảnh có hình hoa hồng
Bài toán 1
Em cần tìm một tệp văn bản có tên bai-hoc-1.docx trên máy tính của em những đã lâu rồi chưa sử dụng lại.
Miền dữ liệu:
Là các tệp văn bản có trên đĩa cứng máy tính của em.
Kết quả:
Là tệp có tên bai-hoc-1.docx
Bài toán 2
Em cần tìm 5 bạn học sinh có điểm trung bình các bài thi cao nhất trong kì thi Olympic Tin học năm 2020 của thành phố Hà Nội.
Miền dữ liệu:
Là danh sách học sinh và điểm các bài thi của kì thi Olympic Tin học thành phố.
Kết quả:
Danh sách 5 bạn có thành tích cao nhất tính theo điểm trung điểm.
Bài toán 3
Câu hỏi củng cố kiến thức:
Em hãy xác định miền dữ liệu và nghiệm có thể của các bài toán tìm kiếm sau.
ĐÁP ÁN
Bài toán 1
Miền dữ liệu là tập hợp các vị trí và đường phố, hay nói cách khác là dữ liệu bản đồ số của địa phương nơi em đang sống.
Nghiệm có thể là một đường đi từ nhà em đến trường. Thể hiện nghiệm có thể hiện trên bản đồ hoặc dãy các bước đi cụ thể từ nhà em đến trường.
ĐÁP ÁN
Bài toán 2
Miền dữ liệu là danh sách tất cả các trường học (thuộc các cấp khác nhau), có thể cả các cơ quan, công ti, văn phòng tại địa phương em đang sống.
Nghiệm sẽ là một danh sách các trường Trung học phổ thông trên địa bàn, hoặc có thể là các vị trí được đánh dấu trên bản đồ.
GHI NHỚ
Có thể nói tìm kiếm là một trong những bài toán quan trọng nhất của Tin học. Việc thiết kế thuật toán tìm kiếm sẽ phụ thuộc vào cấu trúc của miền dữ liệu cần tìm kiếm và tiêu chí cụ thể của bài toán tìm kiếm.
TÌM KIẾM TUẦN TỰ
02
Cách An lần lượt lật các thẻ từ đầu đến cuối trong phần khởi động chính là việc thực hiện tìm kiếm tuần tự trong các thẻ bài.
Quan sát cách thực hiện thuật toán tìm kiếm tuần tự trên ví dụ cụ thể sau. Hãy trao đổi, thảo luận để hiểu và mô tả được thuật toán trong trường hợp tổng quát.
Hoạt động 2:
Trường hợp tổng quát:
Ví dụ cụ thể:
Cho dãy số A = [1, 4, 7, 8, 3, 9, 10] và cần tìm kiếm phần tử có giá trị bằng 9.
Có thể thực hiện tìm kiếm tuần tự như sau:
Miền dữ liệu tìm kiếm phải có
cấu trúc là một dãy tuyến tính các số được đánh số theo chỉ số, ví dụ đánh chỉ số từ 0, 1, 2,…, n – 1.
Lưu ý
GHI NHỚ
Thuật toán tìm kiếm tuần tự được thực hiện bằng cách duyệt lần lượt các phần tử của dãy từ đầu đến cuối để tìm phần tử có giá trị bằng giá trị cần tìm.
Thuật toán tìm kiếm tuần tự có thể viết như sau:
1 deaf LinearSearch(A,K):
2 for i in range(len(A)):
3 if A[i] == K:
4 return i
5 return -1
Câu hỏi củng cố kiến thức:
Câu 1: Cho dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86].
Thuật toán tìm kiếm tuần tự cần thực hiện bao nhiêu lần duyệt để tìm ra phần tử có giá trị bằng 47 trong dãy?
Cần duyệt 8 bước sẽ tìm thấy số 47.
Câu 2: Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần ít bước nhất?
Khi giá trị cần tìm trùng với số đầu tiên của dãy.
Câu 3: Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho ví dụ.
Khi số cần tìm không có trong dãy hoặc trùng với số cuối cùng của dãy.
TÌM KIẾM NHỊ PHÂN
03
Hoạt động 3:
Làm việc nhóm
Cho trước một dãy số đã được sắp xếp theo thứ tự tăng dần. Hãy đọc, quan sát và thảo luận cách làm sau đây để hiểu được thuật toán tìm kiếm nhị phân, biết được tính ưu việt của thuật toán này so với thuật toán tìm kiếm tuần tự trên một dãy các phần tử đã sắp xếp.
Hướng dẫn tìm hiểu:
a) Phân tích bài toán
Khi duyệt một phần tử bất kì của dãy số, em có thể xác định được phần tử cần tìm sẽ nằm ở bên trái hay bên phải phần tử đang duyệt, từ đó quyết định tìm tiếp theo hướng nào mà không cần duyệt tất cả các phần tử của dãy số.
b) Thuật toán tìm kiếm nhị phân
Được áp dụng cho các dãy được sắp xếp theo thứ tự xác định. Sau mỗi bước lặp của thuật toán, phạm vi tìm kiếm được thu hẹp dần.
Theo dõi video với bài toán cụ thể:
c) Minh họa các bước của thuật toán tìm kiếm nhị phân
Giả sử dãy số đã sắp xếp là A = [1, 3, 4, 7, 8, 9, 10]. Giá trị cần tìm là K = 9
Câu hỏi củng cố kiến thức:
Cho dãy A = [0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67].
11
phần tử
3
phần tử
3. Thay vì lần lượt các thẻ từ đầu đến cuối, bạn Minh đã chơi như sau: Đầu tiên Minh lật thẻ ở giữa, sau đó tùy theo số ghi trên thẻ là lớn hơn hay nhỏ hơn số K mà lật tiếp thẻ ở ngay bên trái, hoặc ngay bên phải thẻ ở giữa. Trong trường hợp này, số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là bao nhiêu?
Minh phải lật nhiều nhất là thẻ với n là số thẻ ban đầu.
D. Tìm kiếm dữ liệu cho trước trong một danh sách đã cho.
A. Lưu trữ dữ liệu
B. Sắp xếp dữ liệu theo chiều tăng dần
C. Xử lí dữ liệu
Câu 1: Thuật toán tìm kiếm tuần tự thực hiện công việc gì?
B. Xem xét từ mục dữ liệu đầu tiên cho đến khi tìm thấy mục dữ liệu được yêu cầu hoặc đến khi hết danh sách.
A. Sắp xếp lại dữ liệu theo thứ tự bảng chữ cái.
C. Chia nhỏ dữ liệu thành từng phần để tìm kiếm
D. Bắt đầu tìm từ vị trí bất kì trong danh sách.
Câu 2: Thuật toán tìm kiếm tuần tự thực hiện công việc
như thế nào?
C. Thông báo “Tìm thấy”, giá trị cần tìm tại vị trí thứ 5 của danh sách
A. Thông báo “Không tìm thấy”
B. Thông báo “Tìm thấy”
D. Thông báo “Tìm thấy”, giá trị cần tìm tại vị trí thứ 20 của danh sách
Câu 3: Thực hiện thuật toán tìm kiếm tuần tự để tìm số 20 trong danh sách [1, 3, 5, 4, 20, 2, 11]. Đâu ra của thuật toán là?
C. Vị trí ở giữa
A. Vị trí đầu tiên
B. Vị trí cuối cùng
D. Bất kì vị trí nào
Câu 4: Thuật toán tìm kiếm nhị phân bắt đầu thực hiện ở vị trí nào trong danh sách?
A. 3
B. 4
C. 5
D. 6
Câu 5: Khi thực hiện tìm kiếm nhị phân số 25 trong dãy số
[18, 21, 25, 27, 67, 69, 72, 77, 79, 81]
cần thực hiện mấy vòng lặp?
LUYỆN TẬP
Bài 1 (SGK-tr.93). Em hãy chỉnh sửa thuật toán tìm kiếm tuần tự để tìm ra tất cả các phần tử trong dãy bằng giá trị cần tìm, biết dãy đó có nhiều phần tử bằng giá trị cần tìm.
1 deaf LinearSearch(A,K):
2 kq = []
3 for i in range(len(A)):
4 if A[i] == K:
5 kq.append(i)
6 return kq
Chương trình sau sẽ thực hiện tìm kiếm tuần tự trên dãy A và trả về dãy bao gồm tất cả các chỉ số phần tử có giá trị bằng K, nếu không tìm thấy thì trả về dãy rỗng.
Bài 2 (SGK-tr.93). Viết chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần.
VẬN DỤNG
Bài 1 (SGK-tr.93). Cho A là danh sách tên các học sinh trong lớp, viết chương trình tìm kiếm tuần tự để tìm ra các học sinh có tên là Hoàn.
Chương trình tham khảo:
Bài 2 (SGK-tr.93). Cho A là danh sách tên các học sinh trong lớp được sắp xếp theo thứ tự bảng chữ cái, viết chương trình tìm kiếm nhị phân để tìm ra các học sinh có tên là Minh.
Chương trình tham khảo:
HƯỚNG DẪN VỀ NHÀ
1. Ôn tập các kiến thức đã học
2. Làm các bài tập trong SBT
3. Chuẩn bị trước Bài 20: Thực hành bài toán tìm kiếm
CẢM ƠN CÁC EM ĐÃ �THAM GIA TIẾT HỌC HÔM NAY!
Các em còn câu hỏi nào không?