Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 11: Bài toán tìm kiếm và kĩ thuật duyệt

XIN CHÀO CÁC EM!

CHÀO MỪNG CÁC EM

ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

Để xác định một giá trị a có xuất hiện trong một dãy A cho trước hay không ta có thể áp dụng phương pháp tìm kiếm tuần tự: lần lượt so sánh a với từng phần tử trong A. Theo em, liệu có cách nào để giải bài toán này trong trường hợp A là một dãy bất kì hay không?

CHUYÊN ĐỀ 3: THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT DUYỆT

BÀI 11. BÀI TOÁN

TÌM KIẾM VÀ KĨ THUẬT DUYỆT

NỘI DUNG BÀI HỌC

1

Kĩ thuật duyệt trong bài toán tìm kiếm

2

Tìm kiếm vét cạn

KĨ THUẬT DUYỆT TRONG BÀI TOÁN TÌM KIẾM

01

Thảo luận nhóm và hoàn thành Hoạt động 1

SGK tr.48.

Hoạt động 1

Cho A, B, C, D lần lượt là các danh sách tên học sinh, điểm thi môn Toán, điểm thi môn Vật lí và điểm thi môn Hóa học. Danh sách điểm Toán được sắp xếp theo thứ tự tăng dần và các danh sách tên học sinh và điểm các môn còn lại được sắp xếp theo tương ứng.

A = [“Nam”, “Sơn”, “Hương”, “Huyền”, “Hà”, “Hùng”]

B = [8.3, 8.4, 8.7, 8.9, 9.1.96]

C= [ 8.3, 7.8, 8.9, 9.5, 9.3, 9.0]

D= [7.9, 9.0, 8.9, 8.2, 9.5, 9.1]

Hãy thảo luận về kĩ thuật tìm kiếm được thực hiện với mỗi yêu cầu sau:

• Tìm một học sinh có điểm Toán lớn hơn điểm Vật lí.
• Tìm tất cả các học sinh có điểm Vật lí lớn hơn điểm Hóa học.
• Tìm tất cả các học sinh có cả 3 điểm đều lớn hơn hoặc bằng 9.

HƯỚNG DẪN

Một học sinh có điểm Toán lớn hơn điểm Vật lí: Sơn.

a

Tất cả các học sinh có điểm Vật lí lớn hơn điểm Hoá học: Nam, Huyền.

b

Tất cả các học sinh có cả 3 điểm đều lớn hơn hoặc bằng 9: Hà, Hùng.

c

Kĩ thuật duyệt

Sau khi xác định được miền tìm kiếm, kĩ thuật duyệt sẽ lần lượt xét các dữ liệu trong miền tìm kiếm để đưa ra được phần tử thỏa mãn.

Các bài toán tìm kiếm có thể:

• Đa dạng về yêu cầu tìm kiếm.
• Đa dạng về miền tìm kiếm.

Tùy thuộc vào yêu cầu tìm kiếm, miền tìm kiếm, ta thực hiện các kĩ thuật duyệt theo những cách khác nhau.

Ví dụ 1

Bài toán yêu cầu tìm kiếm một nghiệm; hoặc bài toán tìm nghiệm tối ưu hoặc tìm tất cả các nghiệm.

2 Miền tìm kiếm là danh sách thông thường chưa sắp xếp; hoặc miền tìm kiếm danh sách đã được sắp xếp.

Ví dụ 2

Chương trình mô tả thuật toán tìm kiếm theo ba yêu câu của Hoạt động 1

Ví dụ

1 A = [“Nam”, “Sơn”, “Hương”, “Huyền”, “Hà”, “Hùng”]

2 B = [8.3, 8.4, 8.7, 8.9, 9.1, 9.6]

3 C = [8.3, 7.8, 8.9, 9.5, 9.3, 9.0]

4 D = [7.9, 9.0, 8.9, 8.2, 9.5, 9.1]

5 kqa= “”

6 for i in range(0, len(A)):

7 if B[i] > C[i]:

8 kqa = A[i]

9 break

10 if kqa ! = “”:

11 print ( “Tên một học sinh có điểm Toán lớn hơn điểm Vật lí là:” , kqa)

12 kqb = []

13 for i in rang(0, len(A)):

• if C[i] > D[i]:

12 kqb = []

13 for i in rang(0, len(A)):

• if C[i] > D[i]:

Trả lời Câu hỏi (SGK – tr50) để củng cố kiến thức:

Câu 1: So sánh số vòng lặp cần thực hiện để thực hiện các yêu cầu a, b, c trong ví dụ trên.

Giải

• Với a) Nếu duyệt từ đầu dãy đến cuối dãy thì chương trình có thể kết thúc sau vòng lặp thứ hai.
• Với b) và c) cần duyệt toàn bộ học sinh có trong danh sách, số vòng lặp cần thực hiện là 6.

Câu 2: Phân tích và viết chương trình để thực hiện các yêu cầu sau:

• Tìm học sinh có điểm Toán bằng 8.9.
• Tìm một học sinh có tổng điểm ba môn Toán, Vật lí, Hoá học lớn hơn 26.5.
• Tìm học sinh có tổng điểm ba môn Toán, Vật lí, Hoá học nhỏ nhất.

a

Ta có thể duyệt từ đầu dãy và dừng lại khi tìm thấy một học sinh có điểm Toán bằng 8.9

b

Duyệt từ đầu dãy và dừng lại khi tìm thấy học sinh có tổng điểm ba môn lớn hơn 26.5.

c

Duyệt toàn bộ danh sách các học sinh trong danh sách.

TÌM KIẾM VÉT CẠN

02

Hoạt động 2

Với các bài toán sau, em hãy thảo luận với bạn để tìm kĩ thuật tìm kiếm đã học (tìm kiếm trên các mảng 1 hoặc 2 chiều) để giải.

1. Cho trước số tự nhiên n. Tìm và in ra tất cả các xâu nhị phân có độ dài n.

2. Viết chương trình tìm và liệt kê tất cả các hoán vị của tập hợp [1, 2, ..., n] với n là số tự nhiên cho trước.

HƯỚNG DẪN THỰC HIỆN

Với mỗi phần tử trong mảng, ta sẽ thử đặt giá trị 0 hoặc 1 vào đó và tiếp tục thử đặt giá trị cho các phần tử tiếp theo. Khi đã duyệt hết tất cả các phần tử trong mảng, ta sẽ có được một xâu nhị phân độ dài n.

1

 Quá trình này sẽ được lặp lại cho đến khi tất cả các xâu nhị phân độ dài n đã được tìm thấy.

• Quá trình đệ quy sẽ được tiếp tục cho đến khi tất cả các số đã được sử dụng trong mảng, lúc đó ta sẽ có được một hoán vị của tập hợp [1, 2, ..., n].
• Quá trình này sẽ được lặp lại cho đến khi tất cả các hoán vị của tập hợp [1, 2, ..., n] đã được tìm thấy.

2

• Với mỗi số trong tập hợp [1, 2, ..., n], ta đưa số đó vào một mảng và gọi lại hàm đệ quy với tập hợp [1, 2, ..., n] đã loại bỏ số đó.

TÌM KIẾM VÉT CẠN

• Là kĩ thuật duyệt trên toàn bộ miền tìm kiếm để giải quyết các yêu cầu đa dạng của các bài toán tìm kiếm.
• Tuy nhiên, có nhiều bài toán tìm kiếm dùng duyệt vét cạn cũng không hiệu quả.

Ví dụ

Về hai bài toán ở Hoạt động 2.

Bài toán 1

Bài toán 2

Đọc thông tin và trả lời Câu hỏi (SGK – tr51) để củng cố kiến thức:

• Câu 1: Tìm kiếm tuần tự trên một dãy n phần tử có phải là duyệt vét cạn hay không?
• Câu 2: Một mảng hai chiều kích thước m×n thì duyệt vét cạn sẽ phải duyệt qua tổng số bao nhiêu phần tử?
• Câu 3: Theo em, thuật toán tìm kiếm nhị phân có sử dụng duyệt vét cạn hay không?

HƯỚNG DẪN THỰC HIỆN

1

Trong kĩ thuật tìm kiếm tuần tự, chúng ta phải duyệt toàn bộ các phần tử có trong mảng dữ liệu, do đó tìm kiếm tuần tự được coi là một ví dụ của duyệt vét cạn.

Mảng hai chiếu kích thước m × n có tổng số m × n phần tử. Theo định nghĩa của duyệt vét cạn, chúng ta cần duyệt toàn bộ các phần tử có trong mảng, số phần tử phải duyệt là m × n.

2

Thuật toán tìm kiếm nhị phân chỉ duyệt một vài phần tử trong mảng dữ liệu nên không phải kĩ thuật duyệt vét cạn.

3

LUYỆN TẬP

Bài 1. Viết chương trình cho phép người dùng nhập một số nguyên dương N từ bàn phím rồi in ra số có nhiều ước số nhất trong các số nhỏ hơn N.

Để thực hiện bài toán này, chúng ta cần duyệt tất cả các số nguyên dương nhỏ hơn N để tìm ra số có nhiều ước số nhất.

--------------- Còn tiếp ---------------