Ngăn xếp: Là một loại dữ liệu trừu tượng và các thao tác có thể dùng:
Push(data): Thêm data vào ngăn xếp
Top(): Tìm key mới nhất
Pop(): Trả về và xoá key mới nhất
Empty(): Kiểm tra ngăn xếp có rỗng không
Ví dụ: Cân bằng ngoặc
Đầu vào: Một chuỗi các ký tự '(', ')', '[', ']'
Đầu ra: Trả về việc dấu ngoặc tròn và dấu ngoặc vuông của chuỗi có cân bằng không.
Pseudocode
$IsBalanced(str)$ Stack stack for char in str: if char in [ '(', '[' ]: stack.push(char) else: if stack.empty(): return False top = stack.pop() if top = '(' and char != ')' or top = '[' and char != ']': return False return stack.empty()
Code
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
def print_stack(self):
temp = self.head
while temp is not None:
print(temp.data)
temp = temp.next
def push(self, data_new):
node_new = Node(data_new)
node_new.next = self.head
self.head = node_new
def pop(self):
if self.head is None:
return None
temp = self.head.data
self.head = self.head.next
return temp
def top(self):
return self.head.data
def empty(self):
return self.head is None
class IsBalanced:
def __init__(self, str):
self.str = str
def isbalanced(self):
s = Stack()
for char in self.str:
if char in ['(', '[']:
s.push(char)
else:
if s.empty(): return False
top = s.pop()
if top == '(' and char != ')' or top == '[' and char != ']':
return False
return s.empty()
string = ['(', ')', '[', ']']
I = IsBalanced(string)
print(I.isbalanced())
2. Hàng đợi
Định nghĩa
Ngăn xếp: Là một loại dữ liệu trừu tượng và các thao tác có thể dùng:
Mảng là một tập hợp các phần tử cố định có cùng một kiểu, được lưu trữ liên tiếp nhau trong các ô nhớ. Kiểu phần tử có thể là có các kiểu bất kỳ: ký tự, số, chuỗi ký tự…; cũng có khi ta sử dụng kiểu mảng để làm kiểu phần tử cho một mảng (trong trường hợp này ta gọi là mảng của mảng hay mảng nhiều chiều).
Tính chất của mảng có thể thêm, bớt phần tử trong mảng và có độ phức tạp về thời gian là $O(n)$, đây là một nhược điểm tuy nhiên ưu điểm là ta có thể truy cập bất kỳ phần tử nào trong mảng với độ phức tạp về thời gian là hằng số.
Chú ý: Mảng rất giống với list trong python. nhưng có một số điểm khác nhau như sau
List trong Python là một tập hợp các mục có thể chứa các phần tử của nhiều kiểu dữ liệu, có thể là số, ký tự, v.v.
Dưới đây là sự khác biệt giữa list và mảng trong Python:
List
Mảng
Có thể bao gồm các phần tử thuộc các kiểu dữ liệu khác nhau
Chỉ bao gồm các phần tử thuộc cùng một kiểu dữ liệu
Không cần nhập thư viện
Cần nhập thư viện
Không thể xử lý trực tiếp các phép toán số học
Có thể xử lý trực tiếp các phép toán số học
Ưu tiên cho chuỗi các mục dữ liệu ngắn hơn
Ưu tiên cho chuỗi các mục dữ liệu dài hơn
Tính linh hoạt cao hơn cho phép dễ dàng sửa đổi (thêm, xóa) dữ liệu
Tính linh hoạt kém hơn kể từ khi sửa đổi (thêm, xóa) dữ liệu
Sử dụng bộ nhớ lớn hơn
Tương đối nhỏ gọn hơn về kích thước bộ nhớ
2. Mảng động (nguồn funix)
Mảng động (dynamic aray) cấp phát bộ nhớ cho mảng một cách động trong quá trình chạy chương trình. Sử dụng mảng động ta bắt đầu với mảng có 1 phần tử, khi số lượng phần tử vượt qua khả năng của mảng thì ta gấp đôi kích thước mảng cũ và copy phần tử mảng cũ vào nửa đầu của mảng mới.
Ưu điểm: Tránh lãng phí bộ nhớ khi phải khai báo mảng có kích thước lớn ngay từ đầu.
Nhược điểm: Phải thực hiện thêm thao tác copy phần tử mỗi khi thay đổi kích thước. Một số thời gian thực hiện thao tác không còn là hằng số nữa.
Mảng động: kiểu dữ liệu trừu tượng với các thao tác sau (tối thiểu):
Get(i): Trả về phần tử tại chỉ mục i
Set(i, val): Thiết lập phần tử i với giá trị val
PushBack(val): Thêm giá trị vào cuối mảng
Remove(i): Xóa phần tử tại vị trí i
Size(): Số lượng của các phần tử
Code python. (lưu ý trong python không có mảng tĩnh)
class DArray():
def __init__(self):
self.size = 0 #so phan tu dang su dung trong array
self.capacity = 1 #kich thuoc cua array
self.array = [None]*self.capacity #array la mang duoc cap phat dong
def __len__(self):
return self.size
def get(self, i): #do phuc tap là O(1)
if i < 0 or i >= self.size:
return IndexError('i is out of bounds !')
return self.array[i]
def set(self, i, val): #do phuc tap là O(1)
if i < 0 or i >= self.size:
return IndexError('i is out of bounds !')
self.array[i] = val
def pushback(self, val): #do phuc tap là O(n)
if self.size == self.capacity:
new_arr = [None]*(2*self.capacity)
for i in range(self.size):
new_arr[i] = self.array[i]
self.array = new_arr
self.capacity = 2*self.capacity
self.array[self.size] = val
self.size += 1
def remove(self, i): #do phuc tap là O(n)
if i < 0 or i >= self.size:
return IndexError('i is out of bounds !')
if i == self.size - 1:
self.array = None
self.size -= 1
return
for j in range(i,self.size - 1):
self.array[j] = self.array[j+1]
self.array[self.size-1] = None
self.size -= 1
def Size(self): #do phuc tap là O(1)
return self.size
Danh sách liên kết đơn là một tập hợp các Node được phân bố động, được sắp xếp theo cách sao cho mỗi Node chứa một giá trị (Data) và một con trỏ (Next). Con trỏ sẽ trỏ đến phần tử kế tiếp của danh sách liên kết đó. Nếu con trỏ mà trỏ tới NULL, nghĩa là đó là phần tử cuối cùng của linked list.
Ta có thể thực hiện một số thao tác sau trên danh sách liên kết đơn
PushFront(Key): Thêm vào phía trước
TopFront(Key): Trả về phần tử phía trước
PopFront(): Xóa phần tử phía trước
PushBack(Key): Thêm phần tử phía sau
TopBack(Key): Trả về phần tử phía sau
PopBack(): Xóa phần tử phía sau
Find(Key): Kiểm tra key có trong danh sách hay không?
Erase(Key): Xóa key trong danh sách
Empty(): Kiểm tra danh sách có trống hay không?
AddBefore(Node, Key): Thêm key trước node
AddAfter(Node, Key): Thêm key sau node
Độ phức tạp về thời gian cho một số thao tác phổ biến
a. PushFront(Key)
Đầu tiên chúng ta tạo một nút với khóa là 26, sau đó cho con trỏ liên kết (next) của node mới trỏ vào node đầu tiên trong danh sách hiện tại và cập nhật head point trỏ đến nút mới tạo. Độ phức tạp là $O(1).$
b. PopFront(Key)
Đầu tiên ta cập nhật con trỏ head, sau đó loại bỏ node đầu, thao tác này là $O(1)$
c. PushBack(Key)
Đầu tiên chúng ta tạo một nút với khóa là 26, sau đó dò từ đầu đến đến cuối danh sách và thêm node vừa tạo ở đó. Vì vậy thao tác này mất $O(n).$
Tương tự, nếu chúng ta muốn TopBack hoặc PopBack, chúng ta cũng phải bắt đầu từ đầu, đi xuống phần tử cuối cùng. Sẽ mất $O(n).$
Để giảm độ phức tạp của cách thao tác trên xuống, chúng ta tạo thêm một con trỏ tail.
PushBack(Key) (with tail): Chúng ta tạo một node mới, sau đó cho con trỏ liên kết (next) của tail hiện tại trỏ tới node mới và cập nhật lại node tail. Vậy độ phức tạp giảm xuống còn $O(1)$
Code python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def print_llist(self):
val = self.head
while val is not None:
print(val.data, end = ',')
val = val.next
def pushfront(self, data_new):
node_new = Node(data_new)
node_new.next = self.head
self.head = node_new
if self.tail is None:
self.tail = self.head
def topfront(self):
return self.head.data
def popfront(self):
if self.head is None:
raise IndexError('empty list')
self.head = self.head.next
if self.head is None:
self.tail = None
def pushback_no_tail(self, data_new):
node_new = Node(data_new)
if self.head is None:
self.head = self.tail = node_new
return
last = self.head
while last.next is not None:
last = last.next
last.next = self.tail = node_new
def pushback_with_tail(self, data_new):
node_new = Node(data_new)
if self.head is None:
self.head = self.tail = node_new
else:
self.tail.next = self.tail = node_new
def topback_no_tail(self):
if self.tail is None:
raise IndexError('empty list')
last = self.head
while last.next is not None:
last = last.next
return last.data
def topback_with_tail(self):
return self.tail.data
def popback(self):
if self.head is None:
raise IndexError('empty list')
if self.head == self.tail:
self.head = self.tail = None
else:
last = self.head
while last.next.next is not None:
last = last.next
last.next = None
self.tail = last
def find(self, key):
p = self.head
while p is not None:
if key == p.data:
return 'YES'
p = p.next
return 'NO'
def erase(self, key):
while self.head is not None and self.head.data == key:
if self.head == self.tail:
self.head.data = self.tail.data = None
else:
self.head = self.head.next
temp = self.head
if temp is not None:
while temp.next is not None:
if temp.next.data == self.tail.data == key:
self.tail = temp
temp.next = None
elif temp.next.data == key:
temp.next = temp.next.next
else:
temp = temp.next
def empty(self):
if self.head is None:
return 'YES'
else:
return 'NO'
def add_after(self, node, key):
node_new = Node(key)
node_new.next = node.next
node.next = node_new
if self.tail is node:
self.tail = node_new
def add_before(self, node, key):
node_new = Node(key)
if self.head is node:
node_new.next = self.head
self.head = node_new
return
temp = self.head
while temp.next is not None:
if temp.next is node:
node_new.next = temp.next
temp.next = node_new
return
temp = temp.next
llist = LinkedList()
để giảm độ phức tạp của pop back và add before xuống chúng ta sử dụng danh sách liên kết đôi.
định nghĩa:
Danh sách liên kết đôi (Doubly Linked List) là một tập hợp các Node được phân bố động, được sắp xếp theo cách sao cho mỗi Node chứa một giá trị (Data), một con trỏ (Next) trỏ đến phần tử kế tiếp của danh sách liên kết, nếu con trỏ trỏ tới NULL nghĩa là đó là phần tử cuối cùng của doubly linked list và một con trỏ (Pre) sẽ trỏ đến phần tử trước của danh sách liên kết đó, nếu con trỏ mà trỏ tới NULL, nghĩa là đó là phần tử đầu tiên của doubly linked list.
Quy hoạch động (dynamic programming) giống với chia để trị, chia bài toán thành các bài toán con, sử dụng lời giải của các bài toán con để tìm lời giải cho bài toán ban đầu. Tuy nhiên khác với chia để trị, thay vì sử dụng đệ quy, quy hoạch động lưu trữ lời giải của các bài toán con đã giải. Do vậy, nếu sau này ta cần giải lại chính bài toán đó, ta có thể lấy và sử dụng kết quả đã được tính toán.
1. Bài toán đổi tiền
Tìm số lượng đồng xu tối thiểu cần thiết để đổi giá trị input (một số nguyên) thành tiền xu với mệnh giá coin_1,..., coin_d
a. Sử dụng đệ quy
def RecursiveChange(money, coins):
if money == 0:
return 0
MinNumCoins = float('inf')
for i in range(len(coins)):
if money >= coins[i]:
NumCoins = RecursiveChange(money - coins[i], coins)
if NumCoins + 1 < MinNumCoins:
MinNumCoins = NumCoins + 1
return MinNumCoins
print(RecursiveChange(9, [6, 5, 1]))
Ta để ý thấy sau khi đệ quy sẽ sẽ có những bài toán đã lặp lại cho nên ta tạo ra một bộ nhớ phụ để lưu lại kết quả đã tính toán trước đó, nếu gặp bài toán tương tự chỉ việc lấy đáp án ra sử dụng.
Code python
def edit_distance(str1, str2, n, m):
dp = [[-1 for j in range(m+1)] for i in range(n+1)]
if n == 0:return m
if m == 0:return n
if dp[n][m] != -1:return dp[n][m]
if str1[n-1] == str2[m-1]:
if dp[n-1][m-1] == -1:
dp[n][m] = edit_distance(str1, str2, n-1, m-1)
return dp[n][m]
else:
dp[n][m] = dp[n-1][m-1]
return dp[n][m]
else:
if dp[n][m-1] != -1:m1 = dp[n][m-1]
else:m1 = edit_distance(str1, str2, n, m-1)
if dp[n-1][m] != -1:m2 = dp[n-1][m]
else:m2 = edit_distance(str1, str2, n-1, m)
if dp[n-1][m-1] != -1:m3 = dp[n-1][m-1]
else:m3 = edit_distance(str1, str2, n-1, m-1)
dp[n][m] = 1 + min(m1, m2, m3)
return dp[n][m]
str1, str2 = "dis", "edi"
n, m = len(str1), len(str2)
print(edit_distance(str1, str2, n, m))
Độ phức tạp trên là quá lớn cho nên ta xem xét hướng tiếp cận bottom-up (Từ dưới lên) như sau
Code python
def edit_string(str_1, str_2, n, m):
dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n+1):
for j in range(m+1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif str_1[i-1] == str_2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
return dp[n][m]
str_2 = 'dis'
str_1 = 'edi'
print(edit_string(str_1, str_2, len(str_1), len(str_2)))
Độ phức tạp về không gian và thời gian là $O(n \times m)$, chúng ta có thể giảm độ phức tạp về không gia xuống còn $O(min{n,m})$. tham khảo giaithuatlaptrinh.com
Code python
def edit_distance(str1, str2, n, m):
ED = [1*j for j in range(m+1)]
for i in range(1,n+1):
left,dag = i, i-1
for j in range(1,m+1):
if str1[i-1] == str2[j-1]:
curr = min(ED[j]+1, left+1, dag)
else: curr = min(ED[j]+1, left+1, dag+1)
left, dag, ED[j] = curr, ED[j], curr
return ED[m]
str1 = "dis"
str2 = "edi"
print(edit_distance(str1, str2, len(str1), len(str2)))
3. Bài toán cái túi
a, Bài toán cái túi với điều kiện lặp
Giả sử bạn có một chiếc ba lô có thể đựng được $W(kg)$ và $n$ vật phẩm nặng $w_1,w_2,...,w_n$ với giá trị lần lượt là $v_1,v_2,...,v_n$. Bạn hãy chọn vật phẩm bỏ vào ba lô để mang đi sao cho giá trị là cao nhất. Chú ý mỗi vật phẩm có thể lấy vô số lần.
Phân tích
Gọi $value(w)$ là giá trị lớn nhất của knapsack có tổng trọng lượng tối đa là $W$, khi đó $value(w) = max\left \{ value(w-w_i)+v_i \right \}$
Code python
def kanapsack(W, w_i, v_i):
value = [None]*(W+1)
value[0] = 0
for w in range(1,W+1):
value[w] = 0
for i in range(len(w_i)):
if w_i[i] <= w:
val = value[w - w_i[i]] + v_i[i]
if val > value[w]:
value[w] = val
return value[W]
print(kanapsack(10,[6,3,4,2],[30,14,16,9]))
Độ phức tạp về thời gian là $O(n*W)$
b, Bài toán cái túi với điều kiện không lặp
Gọi $0 \leq w \leq W$ và $0 \leq i \leq n$, $value(w,i)$ là giá trị lớn nhất của knapsack, khi đó $value(w,i)=max\left \{value(w-w_i,i-1)+v_i,value(w,i-1) \right \}$
Code python
def knapsack(W,w_i,v_i):
value = [[None for j in range(W+1)] for i in range(len(w_i)+1)]
for j in range(W+1):
value[0][j] = 0
for i in range(1,len(w_i)+1):
value[i][0] = 0
for i in range(1,len(w_i)+1):
for w in range(1,W+1):
value[i][w] = value[i-1][w]
if w_i[i-1] <= w:
val = value[i-1][w-w_i[i-1]] + v_i[i-1]
if val > value[i][w]:
value[i][w] = val
return value[len(w_i)][W]
print(knapsack(10,[6,3,4,2],[30,14,16,9]))
Đầu tiên, chúng ta sử dụng giao diện dòng lệnh để tạo một lớp 'Scene(Cảnh)' mà qua đó manim tạo video. Trong 'Scene' chúng ta sẽ tạo một hoạt ảnh cho một vòng tròn. Sau đó, chúng ta sẽ thêm một cảnh khác hiển thị hình vuông biến thành một vòng tròn. Đây sẽ là phần giới thiệu cho chúng ta về khả năng hoạt ảnh của Manim. Sau đó, chúng ta sẽ định vị nhiều đối tượng toán học (Mobjects). Cuối cùng, chúng ta sẽ tìm hiểu cú pháp .animate, một tính năng mạnh mẽ làm sinh động các phương thức chúng ta sử dụng để sửa đổi Mobjects.
1. Hoạt ảnh một đường tròn
a. Ví dụ
from manim import *
class CreateCircle(Scene):
def construct(self):
circle = Circle() # tao mot hinh tron
circle.set_fill(PINK, opacity=0.5) # thiet lap mau sac va do trong suot
self.play(Create(circle)) # hien thi vong tron len man hinh
2. Chuyển hình vuông thành hình tròn
a. Ví dụ
from manim import *
class SquareToCircle(Scene):
def construct(self):
circle = Circle()
circle.set_fill(PINK, opacity= 0.5)
square = Square()
square.rotate(PI/4)
self.play(Create(square))
self.play(Transform(square, circle))
self.play(FadeOut(square))
3. Định vị Mobjects S
a. Ví dụ
from manim import *
class SquareAndCircle(Scene):
def construct(self):
circle = Circle()
circle.set_fill(PINK, opacity= 0.5)
square = Square()
square.set_fill(BLUE, opacity= 0.5)
square.next_to(RIGHT, buff= 0.5)
self.play(Create(circle), Create(square))
4. Sử dụng cú pháp .animate để tạo hiệu ứng cho các methods
a. Ví dụ 1
from manim import *
class AnimatedSquareToCircle(Scene):
def construct(self):
circle = Circle()
square = Square()
self.play(Create(square))
self.play(square.animate.rotate(PI / 4))
self.play(Transform(square, circle))
self.play(circle.animate.set_fill(PINK, opacity = 0.5))
Về cơ bản, manim đặt theo ý nghĩa của ba khái niệm khác nhau mà chúng ta có thể phối hợp với nhau để tạo ra các hoạt ảnh động toán học: Đối tượng toán học (mathematical object hay gọi tắt là mobject), hoạt ảnh (animation) và cảnh (scene). Như chúng ta sẽ thấy trong các phần sau, mỗi trong ba khái niệm này được thực hiện trong manim như một lớp riêng biệt: các lớp Mobject, Animation và Scene.
Mobjects
Mobject là khối xây dựng cơ bản cho tất cả các hoạt ảnh manim. Mỗi lớp xuất phát từ Mobject đại diện cho một đối tượng có thể được hiển thị trên màn hình. Ví dụ, các hình dạng đơn giản như Circle, Arrow và Rectangle tất cả đều là mobject. Các cấu trúc phức tạp hơn như Axes, FunctionGraph hoặc BarChart cũng là các mobject.
1. Tạo và hiển thị mobjects
a. Ví dụ
from manim import *
class CreatingMobjects(Scene):
def construct(self):
circle = Circle()
self.add(circle)
self.wait(1)
self.remove(circle)
self.wait(1)
2. Đặt mobjects
a. Ví dụ
from manim import *
class Shapes(Scene):
def construct(self):
circle = Circle()
square = Square()
triangle = Triangle()
circle.shift(LEFT)
square.shift(UP)
triangle.shift(RIGHT)
self.add(circle, square, triangle)
self.wait(1)
b. Ví dụ
from manim import *
class MobjectPlacement(Scene):
def construct(self):
circle = Circle().move_to(LEFT * 2)#di chuyen duong tron sang trai 2 don vi
square = Square().next_to(circle, LEFT)#dat hinh vuong ben trai duong tron
# can chinh vien trai cua tam giac voi vien trai cua vong tron
triangle = Triangle().align_to(circle, LEFT)
self.add(circle, square, triangle)
self.wait(1)
3. Tạo kiểu mobjects
a. Ví dụ
from manim import *
class MobjectStyling(Scene):
def construct(self):
circle = Circle().shift(LEFT)
square = Square().shift(UP)
triangle = Triangle().shift(RIGHT)
circle.set_stroke(color = GREEN, width = 20)
square.set_fill(YELLOW, opacity = 1)#do mo 100%
triangle.set_fill(PINK, opacity = 0.5)#do 50%
self.add(circle, square, triangle)
self.wait(1)
4. Thứ tự Mobject trên màn hình
a. Ví dụ
from manim import *
class MobjectStyling(Scene):
def construct(self):
circle = Circle().shift(LEFT)
square = Square().shift(UP)
triangle = Triangle().shift(RIGHT)
circle.set_stroke(color = GREEN, width = 20)
square.set_fill(YELLOW, opacity = 1)#do mo 100%
triangle.set_fill(PINK, opacity = 0)#do mo trong suot
self.add(triangle, square, circle)
self.wait(1)
Animations
Trung tâm của manim là animation. Nói chung, bạn có thể thêm animation vào cảnh của mình bằng cách gọi phương pháp play().
a. Ví dụ
from manim import *
class SomeAnimations(Scene):
def construct(self):
square = Square()
self.play(FadeIn(square))#tao hinh vuong
self.play(Rotate(square, PI / 4))#xoay hinh vuong 45 do
self.play(FadeOut(square))#xoa hinh vuong
self.wait(1)#dung 1s truoc khi ket thuc video
from manim import *
class RunTime(Scene):
def construct(self):
square = Square()
self.add(square)#hien thi hinh vuong
self.play(square.animate.shift(UP), run_time = 3)
self.wait(1)
3. Tạo hoạt ảnh tùy chỉnh
Mặc dù Manim có nhiều hoạt ảnh tích hợp, ta sẽ thấy những lúc cần chuyển động mượt mà từ trạng thái này Mobject sang trạng thái khác.
a. Ví dụ
from manim import *
class count(Animation):
def __init__(self, number, start, end, **kwargs):
super().__init__(number, **kwargs)
self.start = start
self.end = end
def interpolate_mobject(self, alpha):
value = self.start + alpha*(self.end - self.start)
self.mobject.set_value(value)
class counting_scene(Scene):
def construct(self):
number = DecimalNumber().set_fill(WHITE).scale(5)
self.add(number)
self.wait()
self.play(count(number, 0, 100), run_time = 4, rate_func = linear)
self.wait()
4. Sử dụng tọa độ của mobject
Mobjects chứa các điểm xác định ranh giới của chúng. Những điểm này có thể được sử dụng để thêm các mobject khác tương ứng với nhau, ví dụ như các phương pháp get_center(), get_top() và get_start().
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))
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])
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à
Đ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.
$Merge(B[1...p],C[1...q]):$ $D \text{ } \leftarrow$ mảng trống có kích thước $ p+q$ Điều kiện B và C khác rỗng: $b \text{ } \leftarrow$ phần tử đầu trong $B$
$c \text{ } \leftarrow$ phần tử đầu trong $C$
$if\text{ } b \leq c$: chuyển b từ B sang D $else:$ chuyển c từ C sang D chuyển phần còn lại của B và C sang D return D
def MergeSort(A: list) -> list:
def Merge(B: list, C: list) -> list:
while B and C:
yield (B if B[0]<=C[0] else C).pop(0)
yield from B
yield from C
if len(A) == 1:
return A
mid = len(A)//2
B = MergeSort(A[: mid])
C = MergeSort(A[mid: ])
result = list(Merge(B, C))
return result
def CountSort(A: list) -> list:
if A == []:
return A
A_len = len(A)
A_min = min(A)
A_max = max(A)
counting_A_length = A_max - A_min + 1
counting_A = [0]*counting_A_length
for i in A:
counting_A[i-A_min] += 1
for i in range(1,counting_A_length):
counting_A[i] += counting_A[i-1]
result = [0]*A_len
for i in range(A_len):
result[counting_A[A[i]-A_min] - 1] = A[i]
counting_A[A[i]-A_min] -= 1
return result
A=[-2,-2,-3,-1]
print(CountSort(A))
$Partition(A, l, r):$ $pivot \leftarrow A[l]$ $j=l$ $\text{for i from l+1 to r:}$ $if \text{ } A[i] \leq A[l]:$ $j \leftarrow j+1$ $swap \text{ } A[j] \text{ and } A[i] $ $swap \text{ } A[l] \text{ and } A[j]$ $return \text{ } j$
Code python
def QuickSort(A, left, right):
def partition(A, l, r):
j = l
x = A[l]
for i in range(l+1,r+1):
if A[i] <= x:
j = j + 1
A[i], A[j] = A[j], A[i]
A[j], A[l] = A[l], A[j]
return j
if left >= right:
return
m = partition(A, left, right)
QuickSort(A, left, m-1)
QuickSort(A, m+1, right)
A = [6,2,8,9,5]
left, right = 0, len(A) - 1
QuickSort(A, left, right)
print(A)
Độ phức tạp của thuật toán
Thời gian chạy của $Partition(A, l, r)$ là $O(n)$. Vậy thời gian chạy của $QuickSort(A, l, r)$ là $T(n)=T(m-1)+T(n-m)+O(n)$
Trường hợp tệ nhất $T(n)=O(n^2)$. Trường hợp tốt nhất $T(n)=O(n\log_2n)$
Nếu như ta luôn chọn phân tử đầu tiên của mảng A làm pivot thì rất có thể xảy ra trường hợp tồi tệ là $O(n^2)$ theo như định luật Murphy. Do đó ta cần chọn pivot ngẫu nhiên để luôn đảm bảo xác suất xảy ra trường hợp tồi tệ là thấp và xác suất xảy ra trường hợp tốt $O(n\log_2n)$ cao.
Pseudocode $RandomizedQuickSort$
$RandomizedQuickSort(A, left, right):$ $if \text{ } left \geq right:$ $return$ $k \leftarrow \text{random number between left and right}$ $swap \text{ } A[l] \text{ } and \text{ } A[k]$ $m \leftarrow partition(A, l, r)$ $RandomizedQuickSort(A, l, m-1)$ $RandomizedQuickSort(A, m+1, r)$
Code python
import random
def RandomizedQuickSort(A, left, right):
def Partition(A, l, r):
pivot = A[l]
j = l
for i in range(l+1, r+1):
if A[i] <= pivot:
j += 1
A[j], A[i] = A[i], A[j]
A[l], A[j] = A[j], A[l]
return j
if left >= right:
return
k = random.randint(left, right)
A[left], A[k] = A[k], A[left]
m = Partition(A, left, right)
RandomizedQuickSort(A, left, m - 1)
RandomizedQuickSort(A, m + 1, right)
A = [5,1,8,9,2,4,7,3,6]
left , right = 0, len(A) - 1
RandomizedQuickSort(A, left, right)
print(A)
Định lý
Giả sử rằng tất cả các phần tử của $A[1...n]$ đôi một khác nhau. Khi đó thời gian chạy trung bình của RandomizedQuickSort(A) là $O(n\log_2n)$ trong khi trường hợp xấu nhất thời gian chạy của thuật toán là $O(n^2).$
Chứng minh định lý
Nhận xét: Thời gian chạy của thuật toán tỉ lệ thuận với số phép so sánh trong hàm partition(A)
Để thuận tiện trong việc phân tích thời gian chạy ta gọi mảng $A'[1...n]$ là mảng đã được sắp xếp.
Với $i<j,$ ta định nghĩa biến ngẫu nhiên $\chi_{ij}$ như sau
$\chi_{ij}=\begin{cases} 1& A'[i] \text{ and } A'[j] \text{ được so sánh} \\ 0& \text{ngược lại} \\ \end{cases}$
Với mọi $i < j,A[i]$ và $A[j]$ được so sánh chính xác một lần hoặc hoàn toàn không được so sánh
Thời gian chạy trong trường hợp xấu nhất là $O(n^2).$ Tuy nhiên xác suất rất thấp.
Nhận xét quan trọng: $\chi_{ij}=1$ nếu pivot được chọn đầu tiên trong $A'[i...j]$ là $A[i]$ hoặc $A[j]$
Khi đó $Prob(\chi_{ij}=1)=\frac{2}{j-i+1}$
Gọi $X$ là số lượng phép so sánh trong quá trình chạy hàm $RandomizedQuickSort(A).$
Ta có $X= \sum_{i=1}^{n}\sum_{j=i+1}^n\chi_{ij}$
Luật số lớn mạnh nói rằng trung bình cộng của $X$ hội tụ hầu như chắc chắn về $E(X)$
Phát biểu này cho phép ta ước tính thời gian chạy trung bình của thuật toán là
Tổng $1+\frac{1}{2}+\dots+\frac{1}{n}$ ký hiệu là $H_n$, được gọi là chuỗi điều hòa thứ n và nằm trong khoảng $[\ln n,1+\ln n]$. Vì vậy
$E(X)<2n(H_n-1)\leq 2n\ln n=\Theta(n\ln n).$
Định lý trên đã được chứng minh, để ý thấy rằng nếu các phần tử của mảng $A[1...n]$ không thỏa mãn điều kiện đôi một khác nhau thì các phân tích ở trên sẽ không đúng, vì vậy để xử lý các phần tử bằng nhau, chúng ta thay thế dòng
$m \leftarrow Partition(A, l, r)$
bằng dòng
$(m_1,m_2) \leftarrow Partition3(A, l, r)$
sao cho
Với mọi $l \leq k \leq m_1-1,A[k] < X$
Với mọi $m_1 \leq k \leq m_2, A[k] = X$
Với mọi $m_1+1 \leq k \leq r, A[k]>X$
Pseudocode $RandomizedQuickSort$
$RandomizedQuickSort(A, left, right):$ $if \text{ } l \geq r:$ $return$ $k \leftarrow \text{ramdom number between l and r}$ $swap \text{ } A[l] \text{ }and \text{ }A[k]$ $(m_1,m_2) \leftarrow Partition3(A, left, right)$ $RandomizedQuickSort(A, left, m_1-1)$ $RandomizedQuickSort(A, m_2+1, right)$
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
Bài viết khá dài, cho nên mình xin dừng lại tại đây, qua tết sẽ viết bổ sung phần rút gọn code đệ quy của quick sort, và một số chú thích thêm, bài viết này tham khảo rất nhiều từ giaithuatlaptrinh.com
.gif)
.gif)
