Slide bài giảng Khoa học máy tính 11 cánh diều Chủ đề F(CS) Bài 7: Lập trình giải bài toán tìm kiếm

Tóm lược nội dung

BÀI 7. LẬP TRÌNH GIẢI BÀI TOÁN TÌM KIẾM

HOẠT ĐỘNG KHỞI ĐỘNG

GV đặt câu hỏi: Khi mới tạo một tài khoản người dùng, em được yêu cầu nhập tên người dùng “user name”. Có trường hợp em phải nhập lại tên khác vì tên vừa nhập đã được sử dụng. Theo em, máy tính sẽ làm gì ngay sau khi nhận được yêu cầu tạo tài khoản mới? Hãy diễn đạt điều này thành một bài toán.

NỘI DUNG BÀI HỌC GỒM

• Bài toán tìm kiếm
  • Khái niệm bài toán tìm kiếm
  • Tìm kiếm tuần tự bằng hàm của Python
• Thuật toán tìm kiếm tuần tự
• Thuật toán tìm kiếm nhị phân
• Thực hành lập trình giải bài toán tìm kiếm
• Luyện tập
• Vận dụng

HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1: Bài toán tìm kiếm

a) Khái niệm bài toán tìm kiếm

GV yêu cầu học sinh trao đổi: Thế nào là Bài toán tìm kiếm ? 

Nội dung gợi ý:

Theo nghĩa chung nhất, bài toán tìm kiếm là: Cho một yêu cầu tìm kiếm và một tập hợp dữ liệu là phạm vi tìm kiếm. Hãy tìm mục (các mục) dữ liệu đáp ứng yêu cầu tìm kiếm đã cho hoặc khẳng định không có mục dữ liệu nào đáp ứng yêu cầu đó.

b) Tìm kiếm tuần tự bằng hàm của Python

Nêu phương thức tìm kiếm tuần tự hằng hàm của Python.

Nội dung gợi ý:

- Phương thức index thực hiện tìm kiếm theo cách tuần tự cho dãy xâu kí tự, mảng hoặc danh sách.

- Các trường hợp trả về khi dùng index

+ Nếu xuất hiện nhiều lần thì đưa ra chỉ số của lần xuất hiện đầu tiên.

Ví dụ: 

a = [1, 3, 3, 4, 3, 5, 6]

print(a.index(3))

+ Báo lỗi “valueError” nếu không tìm thấy.

Ví dụ:

a = [1, 2, 3, 4, 5, 6]

print(a.index(5, 1, 4))

+ Phương thức index có hai tham số tùy chọn: lo, hi để hạn chế thực hiện tìm kiếm chỉ trong đoạn con của dãy số, bắt đầu từ chỉ số lo (lowest) và kết thúc ở hi (highest).

Cú pháp:

dãy_số.index(giá_trị, lo, hi)

Hoạt động 2: Thuật toán tìm kiếm tuần tự

Thế nào là thực hiện thuật toán tìm kiếm tuần tự ?

Nội dung gợi ý:

- Thực hiện tìm kiếm tuần tự bằng phép lặp duyệt từ đầu dãy số với điều kiện dừng khi “tìm thấy” hoặc “đã xét hết dãy số”.

Hoạt động 3: Thuật toán tìm kiếm nhị phân

Dựa vào mô tả thuật toán tìm kiếm nhị phân trong Hình 3, em hãy tóm tắt ý tưởng của thuật toán này.

Nội dung gợi ý:

- Nếu dãy số đã sắp xếp theo thứ tự thì có thể áp dụng thuật toán tìm kiếm nhị phân.

- Phép lặp lại thực hiện tìm kiếm nhị phân chia đôi dãy số tại điểm “giữa” có chỉ số (lo + hi)//2, bỏ bớt nửa dãy cho đến khi “tìm thấy” hoặc hết dãy.

Hoạt động 4: Thực hành lập trình giải bài toán tìm kiếm

HS thảo luận trả lời câu hỏi: Em hãy thực hiện các yêu cầu sau:

a) Hãy viết mã giả cho thuật toán tìm kiếm nhị phân.

b) Hãy ước lượng số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân.

c) Hãy ước lượng độ phức tạp thời gian của thuật toán tìm kiếm nhị phân.

Nội dung gợi ý:

a) Mã giả cho thuật toán tìm kiếm nhị phân

def tkNhiPhan (x, a) #Phạm vi tìm kiếm là dãy ban đầu

lo ← 0

hi ← len(a) - 1

while (lo ≤ hi): #Vẫn còn trong phạm vi tìm kiếm

m = (lo + hi) //2  #Xác định phần tử ở giữa phạm vi tìm kiếm

if a_m  == x:

return m #Thông báo tìm thấy x ở vị trí m và kết thúc

elif x < a_m:

hi ← m – 1 #Loại bỏ nữa dãy chắc chắn không chứa x

else: 

lo ← m + 1 #Phạm vi tìm kiếm là nửa dãy còn lại

return  - 1 #Thông báo không tìm thấy x và kết thúc

b) Ước lượng số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân: Kết thúc khi 2^k ~ n tức là k ~ log₂n.

c) Ước lượng độ phức tạp thời gian của thuật toán tìm kiếm nhị phân: Độ phwucs tạp thời gian logarit, O(log₂n).

HOẠT ĐỘNG LUYỆN TẬP

Câu 1: Quá trình giải toán bằng lập trình trên máy tính có …bước:

A. 2

B. 3

C. 4

D. 5

Câu 2: Bước xác định bài toán là:

A. Lựa chọn cách tổ chức dữ liệu và sử dụng ngôn ngữ lập trình để điễn đạt đúng thuật toán.

B. Xác định những giá trị đã cho và mối quan hệ giữa chúng.

C. Tìm thuật toán dựa trên bước xác định bài toán, dựa trên mối quan hệ giữa các đại lượng đã cho với những giá trị cần tìm, đồng thời xác định cách tổ chức dữ liệu có thể sử dụng tương ứng với thuật toán đó.

D. Dùng các bộ dữ liệu khác nhau để kiểm thử và hiệu chỉnh chương trình.

Câu 3: Các bước giải bài toán trên máy tính:

A. Xác định bài toán → Tìm thuật toán của bài toán và cách tổ chức dữ liệu → Kiểm thử, chạy và hiệu chỉnh chương trình → Viết chương trình.

B. Viết chương trình → Xác định bài toán → Tìm thuật toán của bài toán và cách tổ chức dữ liệu → Kiểm thử, chạy và hiệu chỉnh chương trình.

C. Xác định bài toán → Kiểm thử, chạy và hiệu chỉnh chương trình → Viết chương trình → Tìm thuật toán của bài toán và cách tổ chức dữ liệu.

D. Xác định bài toán → Tìm thuật toán của bài toán và cách tổ chức dữ liệu → Viết chương trình  → Kiểm thử, chạy và hiệu chỉnh chương trình.

Câu 4: Bước tìm thuật toán của bài toán và cách tổ chức dữ liệu là:

A. Lựa chọn cách tổ chức dữ liệu và sử dụng ngôn ngữ lập trình để điễn đạt đúng thuật toán.

B. Xác định những giá trị đã cho và mối quan hệ giữa chúng.

C. Tìm thuật toán dựa trên bước xác định bài toán, dựa trên mối quan hệ giữa các đại lượng đã cho với những giá trị cần tìm, đồng thời xác định cách tổ chức dữ liệu có thể sử dụng tương ứng với thuật toán đó.

D. Dùng các bộ dữ liệu khác nhau để kiểm thử và hiệu chỉnh chương trình.

Câu 5: Bước viết chương trình là:

A. Lựa chọn cách tổ chức dữ liệu và sử dụng ngôn ngữ lập trình để điễn đạt đúng thuật toán.

B. Xác định những giá trị đã cho và mối quan hệ giữa chúng.

C. Tìm thuật toán dựa trên bước xác định bài toán, dựa trên mối quan hệ giữa các đại lượng đã cho với những giá trị cần tìm, đồng thời xác định cách tổ chức dữ liệu có thể sử dụng tương ứng với thuật toán đó.

D. Dùng các bộ dữ liệu khác nhau để kiểm thử và hiệu chỉnh chương trình.

Đáp án gợi ý:

HOẠT ĐỘNG VẬN DỤNG

GV yêu cầu HS hoàn thành Vận dụng SGK trang 120: 

Viết chương trình tìm kiếm vị trí tên của một người trong các danh sách sau:

a) Danh sách học sinh trong lớp em.

b) Danh sách tên các chủ tài khoản ngân hàng (không có dấu) và đã được sắp xếp theo thứ tự bảng chữ cái.