Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 8: Thực hành thiết kế thuật toán tìm kiếm theo kĩ thuật chia để trị

XIN CHÀO CÁC EM!

CHÀO MỪNG CÁC EM ĐẾN VỚI

BÀI HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

Cho một dãy số A bất kì. Để xác định một số C cho trước xuất hiện trong dãy A bao nhiêu lần thì làm thế nào?

BÀI 8. THỰC HÀNH THIẾT KẾ THUẬT TOÁN TÌM KIẾM THEO KĨ THUẬT CHIA ĐỂ TRỊ

NHIỆM VỤ. TÌM SỐ

LẦN LẶP CỦA MỘT GIÁ TRỊ TRÊN DÃY ĐÃ SẮP XẾP

Cho trước dãy số A đã sắp xếp theo thứ tự tăng dần, cho trước hằng số C. Hãy tìm xem trong dãy trên có bao nhiêu phần tử có giá trị bằng C. Ví dụ, nếu A = [0, 1, 2, 2, 2, 2 ,4 ,5 ,5 ,6], C = 2 thì kết quả cần tìm là 4.

YÊU CẦU

Ý TƯỞNG

• Bài tập này có thể dễ dàng giải bằng phương pháp tìm kiếm tuần tự đã quen biết.
• Gọi count là số lần xuất hiện của C trong dãy. Thực hiện tìm kiếm tuần tự với C, mỗi lần tìm thấy C, tăng biến count lên 1.

• Chương trình đơn giản như sau:

Có một vòng lặp tại dòng 3 thực hiện n lần (n = len(A)), do đó thời gian chạy là O(n).

• Chương trình đơn giản như sau:

NHẬN XÉT

Giống: Tương tự thuật toán tìm kiếm nhị phân

Khác: dòng lệnh từ 6 đến 13 khi xử lí trường hợp A[mid] = C.

• Các dòng 2, 3 là phần cơ sở của đệ quy.
• Việc "chia" được thực hiện tại dòng 5.
• Các lệnh tiếp theo chính là "trị".  Bài toán này khá đơn giản nên sau khi "trị" sẽ thu được luôn kết quả.

• Trong hầu hết các trường hợp việc xử lí tại dòng 6 đến dòng 13 sẽ mất O(1) thời gian.
• Trong một số trường hợp xấu nhất, ví dụ dãy ban đầu bao gồm toàn các số C thì việc xử lí khi A[mid] = C sẽ mất O(n) thời gian.

LUYỆN TẬP

Chỉnh sửa nâng cấp chương trình của nhiệm vụ thực hành để đưa ra kết quả là vùng các phần tử có giá trị bằng C của dãy gốc, tức là yêu cầu đưa ra chỉ số đầu, chỉ số cuối và số lượng phần tử của vùng có giá trị bằng C.

Ví dụ nếu A = [0, 1, 2, 2, 2, 2, 4, 5, 5, 6], C = 2, thì kết quả trả lại là 2, 5, 4.

1 def countNum(A,left,right,C):

2 if left > right:

3 return None, None, 0

4 else:

5 mid = (left+right)//2

6 if A[mid] == C:

7 start = mid

8 while start >= left and A[start]==C:

9 start = start -1

10 end = mid

11 while end <= right and A[end]==C:

12 end = end + 1

13 return start+1, end-1, end – start - 1

14 elif A[mid] < C:

15 return countNum(A, mid+1, right,C)

16 else:

17 return countNum(A,left,mid-1,C)

13 return start+1, end-1, end – start - 1

14 elif A[mid] < C:

15 return countNum(A, mid+1, right,C)

16 else:

17 return countNum(A,left,mid-1,C)

VẬN DỤNG

Bài 1. Cho một dãy số bất kì (chưa được sắp xếp) và một số K, hãy tìm số lần xuất hiện của K trong dãy số trên. Yêu cầu sử dụng phương pháp chia để trị.

Bài 2. Cho một dãy số nguyên được sắp xếp theo thứ tự tăng dần. Hãy thiết kế hàm tìm trong dãy phần tử thứ i có giá trị bằng I (A[i] = i). Phần tử A[i] như vậy được gọi là phần tử cố định.

Bài 3. Cho trước dãy số A đã sắp xếp theo thứ tự tăng dần, cho trước hằng số C. Cần thiết lập hai hàm sau bằng kĩ thuật chia để trị:

– Hàm firstInd(A, left, right, C) sẽ tìm chỉ số của phần tử đầu tiên của dãy A có giá trị bằng C. Nếu không sẽ trả về -1.

– Hàm lastInd(A, left, right, C) sẽ tìm chỉ số của phần tử cuối cùng của dãy A có giá trị bằng C. Nếu không thấy sẽ trả về – 1.

Từ hai hàm đã thiết kế trên, đưa ra một cách giải khác cho bài toán trong nhiệm vụ 1. Lời giải này có độ phức tạp O(logn).

1 def find(A,left,right,K):

2 if left > right:

3 return 0

4 else:

5 mid = (left+right)//2

6 if A[mid] == K:

7 count = 1

8 else:

9 count = 0

10 return count + find(A,left,mid-1,K)+find(A,mid+1,right,K)

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