(Trang 45)
| Sau bài này em sẽ:
|
|
Khi làm việc với các danh sách/mảng, nhiều trường hợp đòi hỏi cần kiểm ra 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? |
NHIỆM VỤ 1
Đế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).
Hướng dẫn:
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(n²).
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 nghịch đảo.
(Trang 45)
Các bước thực hiện giải bài toán này như sau:
Chia dãy thành hai phần bằng nhau cho đến khi mỗi dãy chỉ còn 1 phần tử.
Khi tiến hành hàm trộn hai dãy sẽ đồng thời đếm số các cặp nghịch đảo của hai dãy này. Kết quả vẫn tạo được dãy trộn như đã mô tả trong thuật toán sắp xếp trộn, vừa đếm được số nghịch đảo.
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ố cặp nghịch đảo khi trộn hai dãy. Kết quả sẽ thu được tổng số cặp nghịch đảo cần tìm.
Chương trình chính như sau:
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
Lưu ý:
- countL là số các cặp nghịch đảo của dãy con bên trái (A, left, mid).
- countR là số các cặp nghịch đảo của dãy con bên phải (A, mid+1, right).
- countM là số cặp nghịch đảo mà chỉ số đầu nằm bên trái, chỉ số sau nằm bên phải.
Tổng số các giá trị trên chính là đáp án cần tìm.
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 đang (i, j), trong đó i nằm trong [left, mid] và j nằm trong khoảng [mid + 1, right]. Mảng phụ temp_arr[] dùng để lưu và cập nhật các thay đổi trên dãy A.
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
(Trang 47)
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
Lưu ý:
- Nếu gộp trường hợp A[i] > A[j], thì sẽ suy ra tất cả các số A[i], A[i + 1], ..., A[mid] đều lớn hơn A[j], do đó tất cả các cặp (i, j), (i + 1, j), ..., (mid, j) đều là nghịch đảo. Vậy suy ra số lượng cặp chỉ số nghịch đảo sẽ tăng lên (mid - i + 1) tại thời điểm này. Điều này được mô tả bằng dòng lệnh 13.
- Các dòng lệnh 24, 25 sẽ cập nhật lại dãy A từ dãy tạm temp_arr sau khi đã tiến hành trộn. Dãy temp_arr được cập nhật trong quá trình trộn tại các lệnh 8, 12, 17, 21.
Lệnh gọi trong chương trình chính:
1 A = [4, 4-7]
2 n = len(A)
3 temp_arr = *n
4 result = getInvCount(A, 0, n - 1)
Phân tích thời gian chạy của thuật toán mergesort thuật toán getInvCount trên có độ phức tạp là O(nlogn).
LUYỆN TẬP
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 = thì chương trình sẽ đưa ra giá trị 4 và dãy [(4, 2), (5, 2), (5, 4), (10, 4)].
VẬN DỤNG
1. Cho dãy số A, cần tìm phần tử từ một (mode) của A. Phần tử mốt là phần tử có số lần xuất hiện nhiều nhất trong A. Nếu tồn tại nhiều thì chỉ yêu cầu tìm ra một phần tử mốt. Yêu cầu sử dụng kĩ thuật chia để trị.
2. Cho một dãy số bất kì A[0], A[1]....,A[n – 1]. Một tổng con được định nghĩa là tổng của một dãy con liên tục dạng S(i, j) = A[i] + A[i + 1] + ... + A[j]. Bài toán yêu cầu tìm i và j chi ra một tổng con và dãy con tương ứng có giá trị lớn nhất. Yêu cầu sử dụng kĩ thuật chia để trị.
