Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị

XIN CHÀO MỪNG CÁC EM

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

KHỞI ĐỘNG

Khi làm việc với danh sách/mảng, nhiều trường hợp đòi hỏi cần kiểm tra các danh sách mảng đã được sắp thứ tự để áp dụng thuật toán phù hợp.

Cho một dãy số, theo em làm thế nào để xác định dãy số đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần?

• Dãy số đã được sắp xếp tăng dần nếu không có cặp nghịch đảo nào, ngược lại dãy số sẽ sắp xếp giảm dần nếu nó có n(n-1)/2 cặp nghịch đảo.
• Bài toán đếm cặp nghịch đảo cũng là một cách dùng để nhận biết một dãy số đã sắp xếp tăng dần hoặc giảm dần hay chưa.

GỢI Ý

BÀI 10. THỰC HÀNH

GIẢI TOÁN BẰNG KĨ THUẬT CHIA ĐỂ TRỊ

NHIỆM VỤ:

ĐẾM CẶP SỐ NGHỊCH ĐẢO (INVERSION) CỦA DÃY SỐ

BÀI TOÁN:

Đếm số cặp nghịch đảo (inversion) của dãy số.

Cho một dãy số A bất kì. Hãy đếm số cặp nghịch đảo của dãy số đó. Một cặp phần tử A[i] và A[j] được gọi là nghịch đảo nếu i < j và A[i] > A[j].

Ví dụ dãy A = [4, 5, 2, 10, 4] sẽ có 4 cặp nghịch đảo là: (4,2), (5,2), (5,4), (10,4).

Cách 1. Phương pháp duyệt đơn giản

Ý TƯỞNG

Duyệt lần lượt từng phần tử của dãy số.

Với mỗi phần tử đang xét A[i], thực hiện so sánh với tất cả các phần tử đứng sau nó A[j], nếu A[i] > A[j] ta sẽ tăng số cặp nghịch đảo lên 1 đơn vị.

Chương trình 1

1 def getInvCount(A):

2 n = len(A)

3 inv_count = 0

4 for i in range(n-1):

5 for j in range(i + 1, n):

6 if (A[i] > A[j]):

7 inv_count = inv_count + 1

8 return inv_count

• Thuật toán trên sử dụng hai vòng for lồng nhau tại dòng 4 và 5, do đó thời gian chạy là O(n2).

Cách 2. Sử dụng phương pháp chia để trị dựa trên thuật toán sắp xếp trộn mergeSort

Ý tưởng: Thực hiện thuật toán sắp xếp trộn trên dãy đã cho, trong quá trình trộn sẽ đồng thời tiến hành đếm số các cặp phần tử nghịch đảo.

Các bước thực hiện

Chia dãy thành hai phần bằng nhau

Đếm số các cặp nghịch đảo của hai dãy

Gọi đệ quy đếm số cặp nghịch đảo cho hai nửa bên trái và bên phải, tính tổng số nghịch đảo.

1 def getInvCount(A,left,right):

2 if left >= right:

3 return 0

4 else:

5 mid = (left + right)//2

6 countL = getInvCount(A, left,mid)

7 countR = getInvCount(A,mid + 1,right)

8 countM = merge(A,left,mid,right)

9 return countL + countR + countM

• Chương trình chính như sau:

1 def merge(A,left,mid,right):

2 i = left

3 j = mid + 1

4 k = left

5 inv_count = 0

6 while i <= mid and j <= right:

7 if A[i] <= A[j]:

8 temp_arr[k] = A[i]

9 k = k + 1

10 i = i + 1

11 else:

12 temp_arr[k] = A[j]

13 inv_count = inv_count + (mid - i + 1)

14 k = k + 1

15 j = j + 1

16 while i <= mid:

17 temp_arr[k] = A[i]

18 k = k + 1

19 i = i + 1

20 while j <= right:

21 temp_arr[k] = A[j]

22 k = k + 1

23 j = j +1

24 for k in range(left,right + 1):

25 A[k] = temp_arr[k]

26 return inv_count

• Chương trình sau sẽ tiến hành trộn hai nửa dãy A từ left đến mid và từ mid + 1 đến right, đồng thời đếm được số các cặp nghịch đảo dạng (i,j)

10 i = i + 1

11 else:

12 temp_arr[k] = A[j]

13 inv_count = inv_count + (mid - i + 1)

14 k = k + 1

15 j = j + 1

16 while i <= mid:

17 temp_arr[k] = A[i]

18 k = k + 1

19 i = i + 1

20 while j <= right:

21 temp_arr[k] = A[j]

22 k = k + 1

23 j = j +1

24 for k in range(left,right + 1):

25 A[k] = temp_arr[k]

26 return inv_count

22 k = k + 1

23 j = j +1

24 for k in range(left,right + 1):

25 A[k] = temp_arr[k]

26 return inv_count

• Lệnh gọi trong chương trình chính:

1 A = [4,5,2,10,4]

2 n = len(A)

3 temp_arr = [0]*n

4 result = getInvCount(A,0,n-1)

LUYỆN TẬP

Nhiệm vụ: Nâng cấp chương trình của nhiệm vụ 1 với yêu cầu bổ sung: Cần đưa ra kết quả là số lượng các cặp nghịch đảo và toàn bộ dãy các cặp chỉ số nghịch đảo đã tìm thấy. Ví dụ với A = [4, 5, 2, 10, 4] thì chương trình sẽ đưa ra giá trị 4 và dãy [(4, 2), (5, 2), (5, 4), (1, 4)].

• Hàm merge(A,left,mid,right) sẽ trả về dãy các cặp nghịch đảo khi tiến hành "trộn" tại chỗ hai phần của cùng dãy A. Phần thay đổi chương trình nằm ở dòng lệnh 13.

1 def merge(A,left,mid,right):

2 i = left

3 j = mid + 1

4 k = left

5 kq = []

6 while i <= mid and j <= right:

7 if A[i] <= A[j]:

8 temp_arr[k] = A[i]

9 k = k + 1

10 i=i+1

11 else:

12 temp_arr[k] = A[j]

13 kq.extend([(x,A[j]) for x in A[i:mid+1]])

14 k = k + 1

15 j=j+1

16 while j <= mid:

17 temp_arr[k] = A[i]

18 k = k + 1

19 i =i+1

20 while j <= right:

21 temp_arr[k] = A[j]

22 k = k + 1

23 j = j+1

24 for 1 in range(left, right + 1):

25 A[1] = temp_arr[1]

26 return kq

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