Bài 1: Cho một dãy gồm $n$ số nguyên và một số nguyên $x$. Hãy đếm xem trong dãy có bao nhiêu phần tử có giá trị $x$.
Code python
def counting(A, l, r, key):
if len(A) == 0:
return 0
elif l == r:
if A[l] == key:
return 1
else:
return 0
mid = (l + r + 1) // 2
return counting(A, l, mid - 1, key) + counting(A, mid, r, key)
A = [1, 2, 3, 2, 4]
key = 2
print(counting(A, 0, len(A) - 1, key))Link bài tập của coursera Programming Assignment 4: Divide-and-Conquer
1. Tìm kiếm tuyến tính.
Trong vấn đề này, chúng ta sẽ triển khai thuật toán tìm kiếm nhị phân cho phép tìm kiếm rất hiệu quả các list (thậm chí rất lớn), miễn là list đó đã được sắp xếp.
Code python
import sys
def binary_search(a, left, right, key):
while left <= right:
mid = (left + right + 1) // 2
if a[mid] == key:
return mid
elif a[mid] > key:
right = mid - 1
else:
left = mid + 1
return -1
if __name__ == '__main__':
inputs = sys.stdin.read()
data = list(map(int,inputs.split()))
n = data[0]
m = data[n + 1]
a = data[1 : n + 1]
left, right = 0, len(a) - 1
for key in data[n + 2 :]:
print(binary_search(a, left, right, key))2. Phần tử đa số (Majority Element).
Một phần tử của dãy có độ dài $n$ được gọi là “phần tử đa số” nếu nó xuất hiện trong dãy nhiều hơn $\frac{n}{2}$ lần.
Code python
class Solution:
def majority_element(self, a, l, r):
def majority(l, r):
if l == r:
return a[l]
mid = (l + r + 1) // 2
left = majority(l, mid - 1)
right = majority(mid, r)
if left == right:
return left
counting_left = sum(1 for i in range(l, r + 1) if a[i] == left)
if counting_left > (r - l + 1) // 2:
return left
counting_right = sum(1 for i in range(l, r + 1) if a[i] == right)
if counting_right > (r - l + 1) // 2:
return right
return -1
return majority(l, r)
a = [2,3,9,2,2]
if Solution().majority_element(a, 0, len(a) - 1) != -1:
print(1)
else:
print(0)3. Cải tiến thuật toán Quick Sort
Mục tiêu trong vấn đề này là thiết kế lại một triển khai đã cho của thuật toán Quick Sort ngẫu nhiên để nó thao tác nhanh ngay cả trên các chuỗi chứa nhiều phần tử bằng nhau.
Code python
import random
def Randomized_Quick_Sort(a, l, r):
def Partition3(A, l, r):
pivot = A[l]
m_1, m_2 = l, r
i = l
while i <= m_2:
if A[i] < pivot:
A[i], A[m_1] = A[m_1], A[i]
m_1 += 1
i += 1
elif A[i] == pivot:
i += 1
else:
A[i], A[m_2] = A[m_2], A[i]
m_2 -= 1
return m_1, m_2
if l >= r:
return
x = random.randint(l,r)
a[l], a[x] = a[x], a[l]
m1, m2 = Partition3(a, l, r)
Randomized_Quick_Sort(a, l, m1 - 1)
Randomized_Quick_Sort(a, m2 + 1, r)
a = [2,3,9,2,2]
Randomized_Quick_Sort(a, 0, len(a) - 1)
print(a)4. Số nghịchđảo (Number of Inversions)
Nghịch đảo của dãy $a_0, a_1, \dots, a_{n-1}$ là một cặp chỉ số $0 \leq i < j < n$ sao cho $a_i> a_j.$
Code python
def count_inversions(X):
def count_cross_inversion(A,B):
R = []
i = j = num_reversion = 0
while i < len(A) and j < len(B):
if A[i] > B[j]:
R.append(B[j])
num_reversion += len(A) - i
j += 1
else:
R.append(A[i])
i += 1
if i < len(A):
R.extend(A[i:])
else:
R.extend(B[j:])
return R, num_reversion
if len(X) == 1:
return X, 0
mid = len(X) // 2
A, inversion_p = count_inversions(X[:mid])
B, inversion_q = count_inversions(X[mid:])
C, cross_inversion = count_cross_inversion(A, B)
num_reversions = inversion_p + inversion_q + cross_inversion
return C, num_reversions
X = [6, 5, 12, 10, 9, 1]
print(count_inversions(X)[1])Mô tả cây đệ quy Mathcha.io
6. Closest Points
Giới thiệu vần đề.
Trong vấn đề này, mục tiêu của chúng ta là tìm cặp điểm gần nhất trong số $n$ điểm đã cho. Đây là một vấn đề nguyên thủy cơ bản trong hình học tính toán có các ứng dụng như đồ họa, thị giác máy tính, hệ thống điều khiển giao thông.
Bài tập. Cho $n$ điểm trên một mặt phẳng, tìm khoảng cách giữa cặp điểm gần nhất
Phân tích
Một thuật toán ngây thơ sử dụng hai vòng lặp duyệt qua tất cả các cặp điểm để tìm ra cặp gần nhất, với thời gian chạy bậc hai. Mục tiêu của chúng ta là thiết kế một thuật toán chia để trị với thời gian $O(n \log_2n)$.
Để giải quyết vấn đề trong thời gian $O(n \log_2n)$, đầu tiên chúng ta hãy chia $n$ điểm đã cho bởi một đường thẳng đứng được chọn thích hợp thành hai nửa $S_1$ và $S_2$ có kích thước $\frac{n}{2}$(giả sử đơn giản rằng tất cả các tọa độ $x$ của các điểm đầu vào là khác nhau). Bằng cách thực hiện hai lệnh gọi đệ quy cho tập hợp $S_1$ và $S_2$ , chúng ta tìm được khoảng cách nhỏ nhất $d_1$ và $d_2$ trong các tập con này. Đặt $d=min\left \{ d_1,d_2 \right \}.$
Cần kiểm tra xem có tồn tại các điểm $p_1 \in S_1$ và $p_2 \in S_2$ sao cho khoảng cách giữa chúng nhỏ hơn d hay không. Chúng ta không thể kiểm tra tất cả các cặp như vậy vì có độ phức tạp là $\frac{n}{2}.\frac{n}{2}=O(n^2)$
Để kiểm tra điều này nhanh hơn, Đầu tiên chúng ta loại bỏ tất cả các điểm từ $S_1$ và $S_2$ có khoảng cách theo $x$ đến đường thẳng ở giữa lớn hơn d. Nghĩa là chúng ta tập trung vào dải sau:
Dừng lại và suy nghĩ: Tại sao chúng ta có thể thu hẹp tìm kiếm trong dải này? Bây giờ, hãy sắp xếp các điểm của dải theo tọa độ $y$ và biểu thị danh sách được sắp xếp theo $P=\left [p_1,p_2,\dots,p_k \right ]$. Nó chỉ ra rằng nếu $\left |i-j\right |>7$, thì khoảng cách giữa hai điểm $p_i$ và $p_j$ chắc chắn lớn hơn d.
Thật vậy: phân vùng dải thành các hình vuông $d\times d$ như được hiển thị bên dưới
Mỗi hình vuông như vậy chứa nhiều nhất bốn điểm đầu vào.
Để ý thấy $p_2 \equiv p_3, p_6 \equiv p_7,$ do đó trong hình vuông $d \times 2d$ có tối đa 6 điểm khác nhau.
Mỗi hình vuông $\frac{d}{2} \times \frac{d}{2}$ chứa một điểm duy nhất vì khoảng cách lớn nhất giữa hai điểm là
$\sqrt{(\frac{1}{2})^2+(\frac{1}{2})^2}=\sqrt{\frac{1}{2}}=\frac{\sqrt{2}}{2}\approx 0,7<1$
Điều này dẫn đến thuật toán sau. Đầu tiên, chúng ta sắp xếp $n$ điểm đã cho theo tọa độ $x$ và sau đó chia danh sách đã sắp xếp thành hai nửa $S_1$ và $S_2$ có kích thước $\frac{n}{2}$. Bằng cách thực hiện một cuộc gọi đệ quy cho từng tập hợp $S_1$ và $S_2$, chúng ta tìm được khoảng cách nhỏ nhất giữa $d_1$ và $d_2$. Đặt $d = min \left\{d_1,d_2\right\}$. Tuy nhiên, chúng ta vẫn chưa hoàn thành vì chúng ta cũng cần tìm khoảng cách nhỏ nhất giữa các điểm từ các tập hợp khác nhau (tức là một điểm từ $S_1$ và một điểm từ $S_2$) và kiểm tra xem nó có nhỏ hơn d. Để thực hiện kiểm tra như vậy, chúng ta lọc tập điểm ban đầu và chỉ giữ lại những điểm có khoảng cách theo $x$ đến đường thẳng ở giữa nhỏ hơn hoặc bằng d. Sau đó, chúng ta sắp xếp tập hợp các điểm trong dải theo tọa độ y của chúng và quét qua danh sách các điểm đó. Đối với mỗi điểm, chúng ta tính khoảng cách của nó tới 5 điểm tiếp theo trong danh sách và tính $d'$, khoảng cách nhỏ nhất mà chúng ta gặp phải trong quá trình quét này. Sau đó, chúng ta trả về $min(d,d')$.
Thời gian chạy của thuật toán thỏa mãn hệ thức truy hồi
$T(n)=2T(\frac{n}{2})+O(n\log_2n).$
$O(n\log_2n)$ là thời gian sắp xếp các điểm trong dải theo tọa độ y tại mọi phép lặp.
Giải bài tập: Chỉ ra cách giảm thời gian chạy xuống $O(n\log_2n)$ bằng cách tránh sắp xếp ở mỗi lần gọi đệ quy.
Code python the-algorithms.com
7. Đảo ngược chuỗi
Code
def reversestring(str):
if len(str) <= 1:
return str
n = len(str)//2
return reversestring(str[n:]) + reversestring(str[:n])
string = 'abc'
print(reversestring(string))
