1. Thuật toán sắp xếp (Sort algorithm) có các thuật toán cơ bản như: Thuật toán: Tại bước k = 1, 2, …, n đưa phần tử thứ k trong mảng đã cho vào đúng vị trí trong dãy gồm k phần tử. đầu tiên. Kết quả là sau bước thứ k, sẽ có k phần tử đầu tiên được sắp xếp theo thứ […]
1. Thuật toán sắp xếp (Sort algorithm)
có các thuật toán cơ bản như:
- Sắp xếp chèn (Insertion Sort)
Thuật toán:
Tại bước k = 1, 2, ..., n đưa phần tử thứ k trong mảng đã cho vào đúng vị trí trong dãy gồm k phần tử. đầu tiên.
Kết quả là sau bước thứ k, sẽ có k phần tử đầu tiên được sắp xếp theo thứ tự.
- Sắp xếp lựa chọn (Selection Sort)
Ý tưởng của Selection sort là tìm từng phần tử cho mỗi vị trí của mảng hoán vị trí A' cần tìm.
Thuật toán:
Tìm phần tử nhỏ nhất đưa vào vị trí 1
Tìm phần tử nhỏ tiếp theo đưa vào vị trí 2
Tìm phần tử nhỏ tiếp theo đưa vào vị trí 3
- Sắp xếp nổi bọt (Bubble Sort)
Thuật toán: Duyệt mảng từ phần tử đầu tiên. Ta sẽ so sánh mỗi phần tử với phần tử liền trước nó, nếu chúng đứng sai vị trí, ta sẽ đổi chỗ chúng cho nhau. Quá trình này sẽ được dừng nếu gặp lần duyệt từ đầu dãy đến cuối dãy mà không phải thực hiện đổi chỗ bất kì 2 phần từ nào
- Sắp xếp nhanh (Quick Sort)
Quick sort là thuật toán sắp xếp được phát triển dựa trên kỹ thuật chia để trị. đây là thuật toán.
QS có thời gian tính trung bình là O(n*log n), tuy nhiên thời gian tính tồi nhất của nó lại là O(n2)
ví dụ code cho thuật toán sắp xếp này
# Doi cho gia tri cua 2 bien
def doicho(m, n):
return n, m
# Thuat toan Quick Sort
def quicksort(L, R):
global a
if L >= R:
return
i = L
j = R
x = a[(L + R)//2]
while True:
while a[i] < x:
i = i+1
while a[j] > x:
j = j - 1
if i <= j:
a[i], a[j] = doicho(a[i], a[j])
i = i + 1
j = j - 1
else:
break
quicksort(L, j)
quicksort(i, R)
2. Thuật toán tìm kiếm (Search algorithm)
- Tìm kiếm tuyến tính(Linear Search) : là một giải thuật tìm kiếm rất cơ bản. Trong kiểu tìm kiếm này, một hoạt động tìm kiếm liên tiếp được diễn ra qua tất cả từng phần tử.
Hiểu đơn giản là duyệt từ đầu đền cuối thấy thì return kết quả
- Tìm kiếm nhị phân(Binary Search): là một giải thuật tìm kiếm nhanh với độ phức tạp thời gian chạy là Ο(log n). Giải thuật tìm kiếm nhị phân làm việc dựa trên nguyên tắc chia để trị (Divide and Conquer).
Tìm kiếm này cần dữ liệu được sắp xếp, và so sảnh với phần tử giữa lớn hơn hay nhỏ hơn thì tìm bên phải hoặc bên trái dữ liệu
- Tìm kiếm nội suy(Interpolation Search): là biến thể cải tiến của Tìm kiếm nhị phân (Binary Search). Để giải thuật tìm kiếm này làm việc chính xác thì tập dữ liệu phải được sắp xếp.
3. Thuật toán vét cạn (Brute force)
Ý tưởng của vét cạn là tạo ra hết tất cả các lời giải có thể có của một bài toán, và sau đó lựa chọn một giải pháp tốt nhất hoặc đếm số lượng lời giải phụ thuộc vào từng bài toán cụ thể.
Tìm kiếm vét cạn là một kỹ thuật tốt nếu dữ liệu đầu vào không quá lớn và đủ thời gian để đi qua hết tất cả các lời giải mà không tốn quá nhiều thời gian xử lý, vì việc tìm kiếm thường dễ để thực thi và nó luôn cho ra lời giải chính xác. Nếu tìm kiếm vét cạn là quá chậm, thì lúc đó ta sẽ nghĩ tới các thuật toán tham lam hoặc quy hoạch động
Bài toán liệt kê dãy nhị phân độ dài n
Bài toán liệt kê dãy nhị phân độ dài n, có nghĩa là ta đi liệt kê hết tất cả các dãy nhị phân từ 000..0(n số 0) cho tới 111..1(n số 1). Ví dụ liệt kê dãy nhị phân độ dài 3.
000, 001, 010, 011, 100, 101, 110, 111
Đây là một bài toán điển hình cho phương pháp vét cạn, và chúng ta sẽ sử dụng thuật toán quay lui để thực hiện.
n=3
a = [0,0,0]
def show():
for i in range(0,n):
print(a[i], end ="")
print(f"")
def Backtracking(k):
for i in range(0,2):
a[k] = i
if k == (n-1):
show()
else:
Backtracking(k+1)
Backtracking(0)
4 .Thuật toán quay lui (Backtracking)
Quay lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy
Backtracking(k) {
for([Mỗi phương án chọn i(thuộc tập D)]) {
if ([Chấp nhận i]) {
[Chọn i cho X[k]];
if ([Thành công]) {
[Đưa ra kết quả];
} else {
Backtracking(k+1);
[Bỏ chọn i cho X[k]];
}
}
}
}
5. thuật toán tham lam (Greedy)
Giải thuật tham lam (tiếng Anh: Greedy algorithm) là một thuật toán giải quyết một bài toán theo kiểu metaheuristic để tìm kiếm lựa chọn tối ưu địa phương ở mỗi bước đi với hy vọng tìm được tối ưu toàn cục.
Ví dụ: Ta có một ba lô có trọng lượng là 37 và 4 loại đồ vật với trọng lượng và giá trị tương ứng, yêu cầu ở đây là bạn sẽ phải chọn tối đa số lượng đồ vật để vừa phù hợp với trọng lượng của ba lô mà giá trị lấy được là lớn nhất.
Từ đó ta có kỹ thuật Tham lam áp dụng cho bài toán này là:
- Tính đơn giá cho các loại đồ vật.
- Xét các loại đồ vật theo thứ tự đơn giá từ lớn đến nhỏ.
- Với mỗi đồ vật được xét sẽ lấy một số lượng tối đa mà trọng lượng còn lại của ba lô cho phép.
- Xác định trọng luợng còn lại của ba lô và quay lại bước 3 cho đến khi không còn có thể chọn được đồ vật nào nữa.
Demo tý nhé : Ta có một ba lô có trọng lượng là 37 và 4 loại đồ vật với trọng lượng và giá trị tương ứng được cho như sau :
Loại đồ vật : A - B - C - D
Trọng lượng : 15 - 10 - 2 - 4
Giá trị : 30 - 25 - 2 - 6
Từ bảng đã cho ta tính đơn giá cho các loại đồ vật và sắp xếp các loại đồ vật này theo thứ tự đơn giá giảm dần ta có bảng sau.
Loại đồ vật : B - A - D - C
Trọng lượng : 10 - 15 - 4 - 2
Giá trị : 25 - 30 - 6 - 2
Đơn giá : 2.5 - 2.0 - 1.5 - 1.0
Theo đó thì thứ tự ưu tiên để chọn đồ vật là là B, A, D và cuối cùng là C.
Vật B được xét đầu tiên và ta chọn tối đa 3 cái vì mỗi cái vì trọng lượng mỗi cái là 10 và ba lô có trọng lượng 37. Sau khi đã chọn 3 vât loại B, trọng lượng còn lại trong ba lô là 37 – 3*10 = 7. Ta xét đến vật A, vì A có trọng lượng 15 mà trọng lượng còn lại của balô chỉ còn 7 nên không thể chọn vật A. Xét vật D và ta thấy có thể chọn 1 vật D, khi đó trọng lượng còn lại của ba lô là 7-4 = 3. Cuối cùng ta chọn được một vật C.
Như vậy chúng ta đã chọn 3 cái loại B, một cái loại D và 1 cái loại C. Tổng trọng lương là 310 + 14 + 12 = 36 và tổng giá trị là 325+16+12 = 83.
6 Thuật toán quy hoạch động (Dynamic programming)
Một số bài toán quy hoạch động
Ví dụ 1: Bài toán kinh điển với đồng xu
Đây là một ví dụ rất kinh điển khi học về quy hoạch động. Có thể có nhiều cách phát biểu khác nhau nhưng về cơ bản, nội dung của nó sẽ tương tự như sau.
Giả sử chúng ta có n đồng xu nặng lần lượt là W1, W2, ..., Wn, và bài toán đặt ra là tìm số lượng đồng xu nhỏ nhất để tổng khối lượng của chúng là một giá trị S. Tất nhiên, số lượng đồng xu là không giới hạn.
Với bài toán này, chúng ta cần xây dựng và giải các bài toán con gối nhau. Với ví dụ của chúng ta, mỗi bài toán con dp(P) với P <= S là bài toán tìm số đồng xu nhỏ nhất để khối lượng của chúng là P. và dp(P) = k chính là số lượng đồng xu nhỏ nhất đó.
Chúng ta sẽ áp dụng phương pháp quy hoạch động bằng cách bắt đầu từ bài toán con dp(0) sau đó tiếp tục với các bài toán con lớn hơn. Lời giải của các bài toán con sẽ được xây dựng lần lượt cho đến chúng ta xây dựng đến bài toán dp(S) và đó chính là kết quả của bài toán lớn. Một điều cần lưu ý với kỹ thuật này là bài toán con tiếp theo sẽ không thể giải được nếu chúng ta chưa giải bài toán con trước đó.
Cuối cùng là phần khó nhất của mọi bài toán quy hoạch động, đó là trả lời câu hỏi: cấu trúc con tối ưu của bài toán này ở đâu. Hay nói một cách khác, làm thế nào để từ những bài toán nhỏ hơn có thể tổ hợp ra lời giải cho bài toán lớn. Với vị dụ kinh điển này, mọi thứ sẽ tương đối đơn giản, nhưng với những bài toán phức tạp hơn, chúng ta cần suy nghĩ và tính toán nhiều hơn.
Quay trở lại với bài toán của chúng ta. Giả sử P là tổng khối lượng của các đồng xu nặng lần lượt là V1, V2, ..., Vj. Để có được khối lượng P, chúng ta cần thêm vài đúng 1 đồng xu nặng U vào khối lượng Q sao cho Q + U = P. Tất nhiên, bài toán con dp(Q) chúng ta đã có lời giải nên chúng ta sẽ biết được cần bao nhiêu đồng xu cho dp(P). Và vì có nhiều đồng xu U(nhiều nhưng hữu hạn) nên chúng ta có thể cần đến nhiều bài toán con trước đó, và dp(p) là giá trị nhỏ nhất sau khi tổng hợp những bài toán con đó.
Ví dụ với n = 3, S = 11, W = [1, 3, 5].
- Bắt đầu với bài toán con
0ta códp(0) = 0 - Với bài toán con
1, có 1 đồng xu (nặng 1) có thể thêm vào từ0đồng xu nào cả. Vậydp(1) = dp(0) + 1 = 1. - Với bài toán con
2, cũng chỉ có 1 đồng xu (nặng 1) có thể thêm vào từ1đồng xu. Vậydp(2) = dp(1) + 1 = 2. - Với bài toán con
3, chúng ta có thể thêm 1 đồng xu 3 vào0đồng xu hoặc thêm 1 đồng xu 1 vào2đồng xu. Rõ ràng là cách đầu tiên cho kết quả nhỏ hơn. Vậydp(3) = min(dp(2) + 1, dp(0) + 1) = min(3, 1) = 1 - …
- Cứ tiếp tục như vậy cho đến bài toán
Schính là đáp án chúng ta cần tìm.
Về mặt cài đặt, quy hoạch động thường lưu kết quả vào một mảng. Trong ví dụ của chúng ta, mảng dp[0..S] sẽ lưu kết quả cho từng bài toán con. Nói cách khác, dp[P] = k nghĩa là cần ít nhất k đồng xu để có khối lượng là PToàn bộ mảng này sẽ được tính bằng vòng lặp. Đoạn code sau mô tả toàn bộ quá trình này
n, S = map(int, input().split())
w = list(map(int, input().split()))
dp = [0] * (S + 1)
dp[0] = 0
for P in range(1, S + 1):
dp[P] = min(dp[P - x] for x in w if x <= P) + 1
print(dp)
print(dp[S])
# Nếu đầu vào như sau: n = 3, S = 11, w = [1, 3, 5]
# Thì bảng lời giải cho các bài toán con sẽ lần lượt như sau:
# P = 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11
# ------+--+--+--+--+--+--+--+--+--+--+--
# k = 0 |1 |2 |1 |2 |1 |2 |3 |2 |3 |2 |3
Ví dụ 2: Xâu con chung dài nhất (LCS)
Cho hai xâu ký tự. Tìm độ dài xâu con chung nhỏ nhất giữa chúng. Ví dụ với 2 xâu “quetzalcoatl” và “tezcatlipoca” thì xâu con chung dài nhất sẽ là “ezaloa” với độ dài 6.
Với bài toán này, chúng ta sẽ lần lượt giải các bài toán con như sau:
Lấy i ký tự đầu tiên từ xâu thứ nhất và j ký tự đầu tiên từ xâu thứ hai và tìm độ dài xâu chung dài nhất giữa 2 xâu con được lấy ra đó. Dễ dàng thấy được rằng, lời giải của mỗi bài toán con sẽ phụ thuộc vào i và j, dp(i, j). Và bài toán lớn sẽ được giải bằng cách lần lượt giải các bài toán con lần lượt từ dp(0, 0) và tăng dần độ dài xâu được lấy ra cho đến khi chúng ta lấy ra toàn bộ xâu của đề bài.
Chúng ta hãy bắt đầu lần lượt các bài toán con. Đương nhiên, nếu một trong hai xâu là rỗng thì xâu con chung của chúng cũng rỗng. Vậy dp(0, j) = dp(i, 0) = 0. Nếu cả i và j đều dương, chúng ta cần suy xét một vài trường hợp.
- Nếu ký tự cuối cùng của xâu thứ nhất không có mặt trong xâu con chung dài nhất, nó có thể bị bỏ qua mà không ảnh hưởng gì đến kết quả. Công thức ở đây sẽ là
dp(i, j) = dp(i - 1, j). - Tương tự như trường hợp trên, ký tự cuối cùng của xâu thứ hai không ảnh hưởng đến kết quả thì
dp(i, j) = dp(i, j - 1). - Trường hợp cuối cùng, nếu hai ký tự cuối cùng của hai xâu
x1, x2đều có mặt trong xâu con chung dài nhất. Dĩ nhiên là hai ký tự này phải là một thì điều này mới xảy ra, tức làx1 == x2. Trong trường hợp này, khi xoá đi bất cứ một ký tự nào trong hai ký tự đó đều khiến xâu con chung dài nhất ngắn đi 1 ký tự. Vậy rõ ràng làdp(i, j) = dp(i - 1, j - 1) + 1.
Trong cả ba trường hợp trên, chúng ta phải chọn ra trường hợp nào cho kết quả là xâu con chung dài nhất (với bài toán này thì chỉ cần đưa ra độ dài đó là đủ).
Về mặt cài đặt, dp sẽ được lưu trong mảng hai chiều. Kết quả của mảng này sẽ được tính toán thông qua vòng lặp hai lớp. Lưu ý rằng, chúng ta cần thực hiện vòng lặp sao cho chúng ta sẽ giải lần lượt từng bài toán con một, theo thứ tự từ nhỏ đến lớn. Bởi vì mỗi bài toán con dp(i, j) đều phụ thuộc vào các bài toán con trước đó dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1).
n1, n2 = map(int, input().split())
s1, s2 = input().split()
t = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
for i, x1 in enumerate(s1, 1):
for j, x2 in enumerate(s2, 1):
if x1 == x2:
t[i][j] = t[i - 1][j - 1] + 1
else:
t[i][j] = max(t[i][j - 1], t[i - 1][j])
print(t[-1][-1])
# Kết quả khi giải các bài toán con như bảng sau:
#
# S| t e z c a t l i p o c a
# T ji| 0 1 2 3 4 5 6 7 8 9 10 11 12
# ----+--------------------------------------
# 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0
# q 1 | 0 0 0 0 0 0 0 0 0 0 0 0 0
# u 2 | 0 0 0 0 0 0 0 0 0 0 0 0 0
# e 3 | 0 0 1 1 1 1 1 1 1 1 1 1 1
# t 4 | 0 1 1 1 1 1 2 2 2 2 2 2 2
# z 5 | 0 1 1 2 2 2 2 2 2 2 2 2 2
# a 6 | 0 1 1 2 2 3 3 3 3 3 3 3 3
# l 7 | 0 1 1 2 2 3 3 4 4 4 4 4 4
# c 8 | 0 1 1 2 3 3 3 4 4 4 4 5 5
# o 9 | 0 1 1 2 3 3 3 4 4 4 5 5 5
# a 10| 0 1 1 2 3 4 4 4 4 4 5 5 6
# t 11| 0 1 1 2 3 4 5 5 5 5 5 5 6
# l 12| 0 1 1 2 3 4 5 6 6 6 6 6 6