> TÀI LIỆU CÓ THỂ CÓ PHẦN SAI SÓT, CHỈ RA SAI Ở ĐÂU = 1 BINGXUE
# Stack
## Chuyển biểu thức từ trung tố sang hậu tố:
Ta đến với dạng bài tiêu biểu cho stack đó là xử lý trung-hậu tố cho biểu thức. Ta bắt đầu với dạng trung tố -> hậu tố đầu tiên. Đây sẽ là nền móng cho ta làm loại còn lại.
Để chuyển 1 biểu thức từ trung tố sang hậu tố, ta cần 1 stack để lưu độ ưu tiên.
### Cách làm?
Quy luât:
- Nếu gặp toán tử hạng hay số hạng thì ta đưa nó vào string hay mảng kết quả `res`.
- Nếu gặp `(` thì ta nhét nó vào stack, đến khi nào gặp `)` ta sẽ tiến hành `pop` stack cho đến khi nào gặp `(`.
- Nếu gặp toán tử `+-*/`, ta xét đến độ ưu tiên của chúng trong biểu thức toán học, toán tử nào có độ ưu tiên lớn hơn hoặc bằng nhau: `*/` > `+-`.
### Solution
```cpp!
init(stack){
stack->top = -1;
}
Uu_tien(intput){
if (intput == '+' || input == '-'){
return 1;
}
else if(intput == '*' || input == '/'){
return 2;
}
return 0;
}
Top(stack){
return stack->data[stack->top];
}
isEmty(stack){
if (stack->top == -1) return 1;
return 0;
}
Trungto_sang_hauto(trungto, hauto){
s;
init(s);
i = 0; c = 0;
while(trungto[c] != '\0'){
token = trungto[c];
if (isalnum(token)){ // nếu token là số hạng
hauto[i] == token;
i++;
}
else if (token == '('){
push(s, token);
}
else if(token == ')'){
while(isEmty(s) != 1 && Top(s) != '('){
hauto[i] = pop(s);
i ++;
}
pop(s);
}
else{
while(isEmty(s) != 1 && Top(s) != '(' && Uu_tien(token) <= Uu_tien(Top(s))){
hauto[i] = pop(s);
i ++;
}
push(s, token);
}
c ++;
}
while(isEmty(s) != 1){
hauto[i] = pop(s);
i++;
}
hauto[i] = '\0';
}
```
## Chuyển từ hậu tố sang trung tố
Hiểu được ý tưởng của bài toán trên thì phần này được coi là dễ hơn. Ta vẫn sẽ dùng 1 stack.
### Cách làm?
Quy luật:
- Nếu thấy toán tử hạng hay số hạng -> đưa nó vào stack.
- Nếu thấy toán tử `+-*/`, ta sẽ tiến hành lấy 2 phần $a, b$ lần lượt là phần tử thứ 2 và phần tử đầu từ đỉnh xuống của stack. Thực hiện toán tử với 2 số hạng này theo: $a (op) b$ rồi lưu chúng vào đỉnh stack.
- Ta sẽ không bao giờ gặp `()` trong biểu thức hậu tố nữa đâu. Sau khi thực hiện các bước trên ta tiến hành trả về kết quả của biểu thức là giá trị đầu tiên trong stack.
### Solution:
```cpp
inside(c, op){
i = 0;
while(op[i] != '\0'){
if (op[i] == c){
return 1;
}
i++;
}
return 0;
}
Danh_gia_bt_hau_to(hauto){
s;
init(s);
c = 0;
op = '+-*/'
while(hauto[c] != '\0'){
token = hauto[c];
if (inside(token, op)){
b = pop(s);
a = pop(s);
if (token == '+'){
push(s, a + b);
}
else if(token == '-'){
push(s, a - b);
}
else if(token == '*'){
push(s, a*b);
}
else{
push(s, a / b);
}
}
else{
push(s, atoi(token)); //atoi là lệnh chuyển string số về số.
}
c ++;
}
return pop(s);
}
```
## Duyệt Cây
Nhắc đến duyệt cây thì ta thường làm với đệ quy do chúng có cú pháp rất đơn giản, nhưng nếu phải dùng stack để mô phỏng đệ quy thì ta có 3 TH như sau:
### Duyệt Preorder(N->L->R)
Nhớ lại cách duyệt Preorder, ta liên tục đi sang trái của cây, add lần lượt các node trong khi đi vào mảng kết quả. Sau khi không đi sang trái được nữa thì ta trả lại đi sang phải.
Sử dụng stack ta mô phỏng cách đi này bằng cách liên tục đưa node phải rồi đến node trái vào stack, sau khi đưa thì pop phần tử trên cùng. Ý tưởng đằng sau cách này đó là SANG TRÁI liên tục nên phải để phải vào trước.
```cpp!
Preorder(root, res){
i = 0;
s;
init(s);
push(s, root);
while (isEmty(s) != 1){
node = pop(s);
res[i] = node->val;
i++;
if (node->right != NULL){
push(s, node->right);
}
if (node->left != NULL){
push(s, node->left);
}
}
}
```
### Duyệt Inorder(L->N->R)
Giống với phần trước, ta đi liên tục sang trái của cây, nhưng ta không đưa node trong các lần đi vào mảng kết quả luân mà đưa node cuối cùng.
Ta duyệt đến cuối cùng nhánh trái của 1 node, sau khi không duyệt được nữa thì sẽ tiến hành đưa phần tử đỉnh từ stack vào mảng kết quả. Tiếp tục, duyệt sang phải node hiện tại và tiếp tục duyệt trái theo logic trên.
```cpp!
Inorder(root, res){
i = 0;
init(s);
cur = root;
while (cur != NULL || isEmty(s) != 1){
while (cur != NULL){
push(s, cur);
cur = cur->left;
}
node = pop(s);
res[i] = node->val;
i++;
cur = node->right;
}
}
```
### Duyệt Postorder:
```cpp!
Postorder(root, res){
i = 0;
init(s);
push(s, root);
while (isEmty(s)){
node = pop(s);
res[i] = node->val; i++;
if (node->left != NULL){
push(s, node->right);
}
if (node->right != NULL){
push(s, node->left);
}
}
reverse(res);
}
```
# Trees
## Validate BST
```cpp!
dfs(root, big, small, check){ //check là con trỏ int *check
if(root == NULL){
return;
}
else if(root.val >= max || root.val <= min){
check++;
return;
}
dfs(root->left, root->val, small, check);
dfs(root-.right, big, small, check);
}
isValidBST(root){
check = 0;
dfs(root, INT_MAX, INT_MIN, check);
if (check != 0){
return 0;
}
return 1;
}
```
# Đề cương a Phác:
# Lý thuyết:
## C1: Trình bày mối quan hệ giữa cấu trúc giữ liệu và giải thuật, cho ví dụ minh hoạ.
Giữa ctdl và gt có mối quan hệ khăng khít, tương hỗ không thể tách rời, được thể hiện qua công thức kinh điển:
`Chương trình = ctdl + gt`
### 1. Mỗi quan hệ tương hỗ
- `CTDL là nền tảng cho giải thuật`: CTDL lưu trữ và tổ chức dữ liệu 1 cách có hệ thống để giải thuật hoạt động trên đó 1 cách hiệu quả. Việc chọn CTDL phù hợp sẽ ảnh hưởng đến thiết kế và độ hiệu quả của giải thuật.
- `Giải thuật thao tác trên CTDL`: giải thuật là tập hợp các bước được định nghĩa rõ ràng. Các bước này thao tác trực tiếp lên dữ liệu trong cấu trúc dữ liệu đã chọn.
### 2. Sự ảnh hưỡng lẫn nhau
- `Lựa chọn CTDL ảnh hướng đến hiệu quả của giải thuật`: Cùng 1 bài toán, nếu chọn cấu trúc dữ liệu khác nhau sẽ dẫn đến giải thuật có độ phức tạp và hiệu suất khác nhau.
- `Giải thuật quyết định CTDL`: Tùy thuộc vào yêu cầu theo tác cần thực hiện, ta sẽ chọn cấu trúc dữ liệu sao cho tối ưu nhất để đáp ứng yêu cầu đó.
### VD:
Bài toán: Tìm kiếm mã sinh viên:
Lựa chọn 1: Sử dụng `mảng` để mã sinh viên:
- Cấu trúc dữ liệu: Dữ liệu được lưu trữ trong các ô nhớ liên tiếp.
- Lúc này ta sẽ cần duyệt tuần tự từ đầu mảng để tìm mã sinh viên.
- Độ phức tạp thời gian: $O(n)$
Lựa chọn 2: Sử dụng `BST`:
- Cấu trúc dữ liệu: Dữ liệu được tổ chức theo cấu trúc cây, mỗi node có tối đa 2 con. Các giá trị bên trái nhỏ hơn node cha và các giá trị bên phải lớn hơn node cha.
- Để tìm kiếm mã sinh viên cần tìm, ta chỉ cần duyệt BST bằng cách so sánh giá trị với node hiện tại để quyết định sang trái hay phải.
- Độ phức tạp thời gian: $O(logn)$ - Hiệu quả hơn mảng.
## C2: Trình bày mối quan hệ giữa cấu trúc dữ liệu và các phép toán trên cấu trúc dữ liệu
CTDL và các phép toán có mối quan hệ `Định nghĩa và Thực thi`. CTDL không chỉ là cách thức tổ chức dữ liệu mà còn xác định bởi tập hợp các phép toán có thể thực hiện trên nó.
### Các phép toán định nghĩa bản chất của CTDL
- Mỗi `CTDL` được thiết kế để tối ưu hóa cho một số phép toán cụ thể: Bản chất và mục đích sử dụng của 1 CTDL được thể hiện rõ nhất qua các phép toán mà nó hỗ trợ.
- Ví dụ: Stack có phép toán `PUSH` - `POP` tức là đưa dữ liệu lên đỉnh stack hoặc lấy dữ liệu và xóa đỉnh.
### CTDL quyết định cách thức và hiệu quả thực thi của phép toán.
- Cách dữ liệu được tổ chức sẽ quyết định thuật toán cụ thể để cài đặt các phép toán.
- Hiệu suất (độ phức tạp không và thời gian) của phép toán phụ thuộc vào CTDL đã chọn.
## C3: Trình bày sự khác nhau giữ cấu trúc dữ liệu và cấu trúc lưu trữ, cho ví dụ minh hoạ.
### 1. Định nghĩa:
- `CTDL`: Là 1 mô hình toán học hoặc logic mô tả cách tổ chức, sắp xếp dữ liệu và mối quan hệ giữa chúng. Kèm theo đó là 1 tập hợp các phép toán được định nghĩa để theo tác trên dữ liệu đó. CTDL mang tính trừu tượng và không phụ thuộc vào cách nó được cài đặt trên máy tính.
- `Cấu trúc lưu trữ`: Là cách biểu diễn vật lý của CTDL trong bộ nhớ máy tính. Nó mô tả cách các phần tử dữ liệu được tổ chức, cấp phát và truy cập trong bộ nhớ (như RAM). Đây là bước thực hiện hóa cụ thể của CTDL trừu tượng.
### 2. Phân biệt:
- `Mức độ 'Trừu tượng'`:
- `CTDL`: Tập trung vào mối quan hệ Logic giữa các phần tử dữ liệu và các phép toán.
- `CTLT`: Tập trung vào cách tổ chức dữ liệu trong bộ nhớ máy tính.
- `Góc nhìn`:
- `CTDL`: Góc nhìn của người lập trình, người thiết kế giải thuật.
- `CTLT`: Góc nhìn của hệ thống, trình biên dịch khi cấp phát bộ nhớ
- `Mối quan hệ`:
- `CTDL`: 1 CTDL có thể có nhiều CTLT khác nhau.
- `CTLT`: Là sự cài đặt cụ thể của 1 CTDL.
### VD:
CTDL: Stack
- Stack là 1 danh sách các phần tử hoạt động theo nguyên tắc LIFO, tức là phần tử vào sau thì ra trước. Nó gồm các phép toán là `PUSH`, `POP`.
=> Để cài đặt CTDL này ta có thể dùng mảng lưu trữ các phần tử và con trỏ top ở phần tử cuối giúp thực hiện phép toán. Hoặc có thể sử dung LinkedList với 2 con trỏ `head` trỏ đầu và `tail` trỏ cuối.
## C4: Trình bày những đặc điểm về cấu trúc dữ liệu trong các ngôn ngữ lập trình bậc cao, có liên hệ với ngôn ngữ C.
Trong các ngôn ngữ lập trình bậc cao, dữ liệu được phân thành các kiểu dữ liệu. Kiểu dữ liệu của 1 biến được xác định bởi giới hạn giá trị biến đó có thể nhận và các phép toán thực hiện được trên các giá trị đó. `VD` trong C có kiểu dữ liệu `int` miền giá tị từ khoảng `-2.1 tỉ -> 2.1 tỉ`. Ta có thể thực hiện các phép toán số học, thao tác bit, so sánh, vv...
Mỗi ngôn ngữ lập trình sẽ cung cấp cho ta các `kiểu dữ liệu cơ bản`. Trong các ngôn ngữ lập trình bậc cao khác nhau thì kiểu dữ liệu cơ bản có thể khác nhau. VD trong C:
- int: số nguyên
- float: số thực
- char: ký tự
- vv...
-
Các kiểu dữ liệu cơ bản này thường không đủ o người lập trình sử dụng. Từ đó ta phải sử dụng chúng như thành phần kiến tạo nên kiểu dữ liệu có cấu trúc phức tạp hơn. Ngôn ngữ lập trình sẽ cung cấp cú pháp, phương thức để ta có thể kết hợp các `kiểu dữ liệu cơ bản` và `kiểu dữ liệu do người dùng định sẵn - kiểu dữ liệu mà người lập trình xây dựng` thành 1 ` kiểu dữ liệu mới`. `VD`: C cho ta quy tắc xây dựng kiểu dữ liệu mới như: mảng, struct, móc nối, ...
Các kiểu dữ liệu được xây dựng từ nhiều kiểu dữ liệu khác gọi là kiểu dữ liệu cấu trúc - thường gọi là cấu trúc dữ liệu. `VD`: trong C: mảng, struct, móc nối... được coi là cấu trúc dữ liệu.
Trong ngôn ngữ lập trình C/C++, có 3 cách để liên kết các dữ liệu:
- Liên kết các dữ liệu cùng kiểu dữ liệu thành mảng.
- Liên kết các kiểu dữ liệu có thể không cùng kiểu thành 1 struct.
- Dùng con trỏ để móc nối: Linkedlist, Trees...
## C5: Trình bày nguyên tắc thiết kế Top-Down, cho ví dụ minh hoạ
### 1. Định nghĩa:
Thiết kế `TOP-DOWN` là phương hướng tiếp cận để giải quyết bài toán hay thiết kế chương trình. Nguyên tắc cốt lõi của nó là `chia để trị`.
Cụ thể 1 bài toán lớn sẽ được chia thành nhiều bài toán nhỏ - đơn giản hơn. Qúa trình phân rã này diễn ra liên tục cho đến khi nào bài toán con đủ nhỏ để giải quyết trực tiếp bằng 1 module(hàm hay thủ tục) đơn giản.
### 2. Các bước thực hiện:
- B1: Xác định mục tiêu chính và yêu cầu của bài toán ở mức cao nhất (`TOP`).
- B2: Chia bài toán tổng thể thành các module chính, mỗi modulo giải quyết 1 phần của bài toán lớn.
- B3: Nếu các module vẫn còn quá phức tạp ta sẽ tiếp tục phân rã chúng cho đến khi đạt được các module con đủ đơn giải và dễ dàng cài đặt.
- B4: Tiến hành cài đặt và kiểm thử, viết mã cho các module thấp nhất, sau đó tích hợp lại hoàn thiện module ở mức cao hơn và dần dần là toàn bộ chương trình.
### 3. VD:
### Ưu + nhược:
- Dễ gỡ lỗi.
- Tăng tính module hóa
- Dễ bảo trì và gỡ lỗi
- Thúc đẩy tái sử dụng mã
- Hỗ trợ làm việc nhóm
## C6: Trình bày Phương pháp tinh chỉnh từng bước, cho ví dụ minh hoạ
### 1. Định nghĩa và mối quan hệ với Topdown:
Đây là 1 kĩ thuật phát triển chương trình từ đặc tả trừu tượng của bài toán và sau đó phân rã, chi tiết hóa nó thành các mã lệnh cụ thể.
Nếu Top-Down là chiến lược "nghĩ từ tổng thể đến chi tiết", thì Tinh chỉnh từng bước là quá trình "viết từ tổng thể đến chi tiết".
### 2. Nguyên tắc cốt lõi:
1. `Bắt đầu từ mức trừu tượng cao nhất`: Viết ra mục tiêu của toàn bộ chương trình bằng ngôn ngữ tự nhiên hoặc mã giả.
2. `Phân rã ở mỗi bước`: Tại mỗi bước chọn 1 lệnh trừu tượng và thay thế nó bằng chuỗi lệnh chi tiết hơn nhưng có thể vẫn có yếu tố trừu tượng.
3. `Trì hoãn các quyết định chi tiết`: Các quyết định về CTDL chi tiết hay cách cài đặt chi tiết được hoãn lại để tập trung vào luồng logic chính
4. `Kết thúc khi tất cả là mã lệnh`: Quy trình tinh chỉnh kết thúc khi mà toàn bộ mã lệnh trừu tượng được thay thế bằng mã lệnh của ngôn ngữ lập trình.
### 3. VD:
## C7: Trình bày cách Phân tích thời gian thực hiện giải thuật. Định nghĩa O lớn:
Để phân tích thời gian thực nghiệm của giải thuật ta có 2 cách chính:
- Phương pháp Thực nghiệm:
- Cài đặt giải thuật bằng 1 ngôn ngữ lập trình cụ thể.
- Chạy dữ liệu với nhiều bộ dữ liệu đầu vào với kích thước khác nhau.
- Đo thời gian thực nghiệm bằng các hàm của hệ thống(`clock` trong C).
- Phương pháp Lý thuyết:
- Không chạy chương trình, phân tích dựa vào mã giả hoặc mã nguồn của giải thuật.
- Ước tính thời gian bằng cách đếm số lượng các phép tính toán đơn giản mà giải thuật phải thực hiện. Các `phép toán cơ bản` là các phép toán mà thời gian thực hiện của nó hằng số
- Thời gian thực hiện được biểu dưới dạng hàm $T(n)$ theo kích thước đầu vào `n`.
### Y/N BigO()notation:
#### 1. Định nghĩa
O-lớn miêu tả cận trên của mức độ ` tăng tưởng độ phức tạp` của 1 hàm khi kích thước đầu vào tiến ra vô cùng. Nó cho ta biết rằng trong trường hợp xấu nhất, độ phức tạp sẽ không tăng nhanh hơn 1 mức độ cố định.
- Định nghĩa chính thức: Hàm $T(n)$ được gọi là $O(f(n))$ khi mà tồn tại 2 hằng số dương $c$ và $n_0$ sao cho: $T(n) < c.f(n) (n > n_0)$.
- Diễn giải: $T(n)$ sẽ không tăng trưởng nhanh hơn $f(n) khi $n$ đủ lớn. $f(n)$ là 1 hàm đơn giản hơn (VD: $n, logn, n^2,...$) đại diện cho lớp "Hiệu năng" của giải thuật.
#### 2. Các quy tắc xác định O-lớn:
1. `Quy tắc bỏ hằng số`: Nếu $T(n) = c.f(n)$ thì độ phức tạp thời gian là $O(f(n))$.
2. `Quy tắc bỏ số hạng bậc thấp`: Bỏ qua số hạng có đọ tăng trưởng chậm hơn ($n^2 + n + 1$ thì chỉ là $O(n^2)$ thôi).
3. `Quy tắc nhân`: Nếu 1 thao tác $O(f(n))$ được lặp lại $O(g(n))$ lần (như 2 vòng for lồng nhau trong BB Sort) thì ta có độ phức tạp là: $O(f(n).g(n))$
4. `Quy tắc cộng`: Nếu giải thuật có 2 bước nối tiếp có độ phức tạp là $O(f(n))$ và $O(g(n))$ thì độ phức tạp của nó là: $O(max(f, g))$
#### TC-Chart:
## C8: Trình bày cách Xác định độ phức tạp tính toán của giải thuật, với những nội dung: Qui tắc tổng, Phép toán tích cực, thời gian chạy của các câu lệnh lặp, cho ví dụ minh hoạ.
Câu này giống câu trên, ta tập trung cài vài điểm khác duy nhất
Phép toán tích cực là phép toán được thực hiện nhiều nhất trong giải thuật. Nó thường là thao tác cốt lõi, nằm trong vòng lặp sâu nhất và là yếu tố quyết định đến tổng thời gian thực hiện giải thuật.
-> Nói cách khác, đây là 'công việc chính' và giải thuật lặp đi lặp lại để giải quyết bài toán.
#### VD:
```python!
#PYTHON
for i in range(n):
for j in range(n):
a += 1
```
- Ta thấy phép toán `a += 1` nằm ở vòng lặp sâu nhất. Đây là phép cộng 1 số `a` thêm 1 đơn vị và ta có thể coi đây là 1 phép toán tích cực.
- Ta thấy rằng 2 vòng lặp này lồng nhau, mỗi cái chạy `n` lần thì phép toán tích cực được thực hiện khoảng: $O(n^2)$ lần.
## Đề cương mới C7: Trình bày phương pháp chia để trị, mô tả ý tưởng + đưa VD minh họa:
Ý tưởng cốt lõi của giải thuật liên quan đến `chia để trị`:
- Thay vì chú tâm giải bài toán lớn 1 các trự tiếp, ta giải các bài toán con liên quan trước rồi sau đó kết hợp lời giải của chúng lại để đưa ra kết quả của bài toán lớn.
### Steps:
Quy trình này sẽ gồm 3 bước chính:
- `Chia`: Phân rã bài toán ban đầu có kích thước `n` thành các bài toán con nhỏ hơn. Các bài toán thường có dạng giống hệt bài toán ban đầu nhưng có `n` nhỏ hơn.
- `Trị`: Giải các bài toán con này 1 cách đệ quy, sau khi phân rã bài toán lớn đủ nhỏ( đến được basecase ), ta sẽ tiến hành giải trực tiếp mà không cần phải phân rã trước.
- `Tổng hợp`: Xây dựng lời giải cho bài toán lớn ban đầu từ những bài toán con đã được giải quyết.
### VD: Thuật toán Merge Sort:
Thuật toán này dựa theo nguyên lý chia để trị, ta chia 1 mảng ra thành nhiều mảng con cho đến khi mảng con chỉ còn có 1 ô, lúc này ta sẽ tiến hành sử dụng thuật toán `Trộn 2 mảng đã được sắp xếp` để trộn 2 mảng con có 1 phần tử vì bản chất 1 mảng có 1 phần tử thôi dã được coi là 1 mảng đã được sắp xếp. Và khi trộn được 2 mảng con này thành 1 mảng được sắp xếp cũng chính là mảng con của mảng lớn hơn cũng đã được sắp xếp chỉ chờ đợi để được trộn với mảng con khác đã được sắp xếp bên cạnh:
```cpp!
merge(arr[], l, m, r){
len1 = m - l + 1;
len2 = r - m;
arr1[len1];
arr2[len2];
for(int i = 0; i < len1; i++){
arr1[i] = arr[l + i];
}
for(int i = 0; i < len2; i++){
arr2[i] = arr[m + i + 1];
}
i = 0; j = 0; k = l;
while(i < len1 && j < len2){
if(arr1[i] < arr2[j]){
arr[k] = arr1[i];
i++;
k++;
}
else{
arr[k] = arr2[j];
j ++;
k ++;
}
}
while(i < len1){
arr[k] = arr1[i];
i++;
k++;
}
while(j < len2){
arr[k] = arr2[j];
j++;
k++;
}
}
sort(arr[], l, r){
if(l < r){
m = (l + r) / 2;
sort(arr, l, m);
sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
```
## Đề cương mới C8: Trình bày Phương pháp quy hoạch động, sử dụng nó vào bài Unbounded Knapsack
### Quy hoạch động (Dynamic Programming)
Đây là giải thuật khá giống với chia để trị, ta phân rã bài toán lớn gốc thành các bài toán con nhỏ hơn và cần đưa ra lời giải cho chúng trước khi ghép lại để xử lý bài toán lớn. Nếu so sánh với `Chia để trị`, thì các bài toán con trong phương pháp này sẽ `Chồng chéo lên nhau - 1 bài toán con có thể sẽ được sử dụng lại nhiều lần`.
Nguyên tắc giải: giải mỗi bài toán con 1 lần duy nhất rồi lưu kết quả vào 1 cấu trúc dữ liệu (mảng or bảng). Khi cần ta chỉ cần lấy kết quả của nó khiến việc tính toán được giảm đi đánh kể.
### Unbounded Knapsack
Như đã đề cập, để giải bài toán lớn ta sẽ phân rã nó ra thành các bài toán nhỏ hơn. Ở bài `xếp n đồ vật vào balo có trọng tải tối đa W` này ta sẽ tiền hành chia bài toán này thành -> `xếp (0, 1, 2, 3, ..., n) đồ vật vào balo có trọng tải tối đa (0, 1, 2, 3, ... W)`.
Cụ thể:
- Ta lập 1 bảng 2 chiều, với W + 1 cột và n + 1 hàng.
- Thứ tự hàng sẽ là thứ tự của đồ vật bắt đầu từ 0, tại mỗi hàng có thứ tự cột bằng với trọng tải tối đa của balo bài toán con.
- ta duyệt bắt đầu từ hàng đầu tiên (hàng 0), mỗi hàng duyệt từ cột đầu đến cột cuối. Tại mỗi ô, ta sẽ tính toán xem giá trị tối đa của balo có thể là bao nhiều với số đồ vật bắt đầu từ 0 (thứ tự hàng) có thể nhét vào balo có W = thứ tự cột, theo công thức:
- i == 0 || j == 0: điền 0
- pick = value[i - 1] + dp[i][j - weight[i - 1]]
- notpick = dp[i - 1][j];
- Điền max(pick, notpick)
### Code:
```cpp!
Dp(W, val, wt){
n = len(val) // số lượng đồ vật
dp[n+1][W + 1];
for(i = 0; i <= n; i++){
for(j = 0; j <= W; j++){
if(i == 0 || j == 0){
dp[i][j] = 0;
}
else{
pick = 0;
if(j - wt[i - 1] >= 0){
pick = val[i - 1] + dp[i][j - wt[i - 1]];
}
notpick = dp[i - 1][j];
dp[i][j] = max(pick, notpick);
}
}
}
return dp[n][W];
}
```
## Đề cương mới C9: Trình bày phương pháp quay lui và mô tả ý tưởng phương pháp này:
`Backtracking` là giải thuật thiết kế dựa trên đệ quy để giải quyết bài toán cách thử xây dựng 1 lời giải từng bước một. Tại mỗi bước nếu phát hiện ra lựa chọn hiện tại không thể dẫn tới 1 lời giải hợp lệ, thuật toán sẽ "quay lui" - hủy bỏ lựa chọn vừa rồi và thử lựa chọn khác. Hoặc cũng có thể nếu ta đã tìm được 1 hướng giải hoàn chỉnh rồi thì ta lại "quay lui" bước trước đó để xem có cách nào nữa hay không, ...
Ý tưởng cốt lõi của giải thuật này giống như giải 1 mê cung:
- Ta thử đi theo 1 con đường
- Ta tiếp tục đi sâu hơn cho đến khi gặp 1 ngõ cụt hoặc tìm được 1 lỗi ra
- Nếu ta gặp 1 ngõ cụt, cần phải tiến hành quay lại bước trước đó để thử 1 con đường khác mà ta chưa đi
- Qúa trình này lặp lại cho đến khi tìm được tất cả đường ra hợp lệ hoặc giải được bài toán ta mong muốn.
### Thuật toán Backtracking tổng quát:
```python!
def Backtracking():
if found_solution?: #Tìm thấy 1 đáp án, ghi đáp án đó lại
process_solution()
return #trả về đệ quy (quay lui)
for next_choice in choices: # Xem xét các lựa chọn hướng giải
if condition_valid: #Nếu điều kiện để đưa ra lựa chọn đi theo hướng giải hợp lý
add_to_solution(next_choice) #đi theo hướng giải đó
Backtracking(smt) #Tìm hướng giải kế tiếp
add_to_solution.pop() #quay lui để tìm hướng giải mới khi hướng hiện tại ko khả quan hoặc đã tìm được 1 lời giải hợp lý
```
## Đề cương mới C10: Phương pháp nhánh cận và hàm miêu tả ý tưởng
`Nhánh cận` là 1 cách thiết kế giải thuật nâng cao, tập trung vào việc tối ưu hóa (`Tìm giá trị nhỏ nhất or lớn nhất`)
Điểm cải tiến của `Nhánh cận` so với quay lui đó là mỗi khi thử 1 hướng giải - hay thử phát triển 1 nhánh ta sẽ dùng 1 `hàm cận - bound function` để đánh giá tiềm năng của các nhánh - hay các hướng giải. Dựa vào đó ta có thể đánh giá và tỉa `prune` những nhánh được coi là không tối ưu.
Ta thấy rằng `Nhánh cận` có thể được mô tả bằng 1 cây nhị phân tìm kiếm:
- Gốc của cây được hiểu là chưa tìm được thành phần nào của nghiệm.
- Các node con là mỗi lựa chọn $x_i$ - tìm các thành phần nghiệm. Nếu ta thấy 1 nhánh được coi là không tối ưu vậy thì node lá của nhánh đó sẽ không cần phải xét hay phát triển nữa.
=> Ta thấy rằng việc giải thuật này chạy nhanh hay chậm tùy thuộc vào số nhánh bị cắt => Điều này lại phụ thuộc vào các cận. Vì vậy, ta cần cố gắng chọn cận sao cho nếu là cận trên thì nhỏ nhất có thể và cận dưới là lớn nhất có thể.
### Ý tưởng cốt lõi
- `Nhánh`: Đầu tiên khởi tạo giá trị phù hợp của vector nghiệm tối ưu. Sau đó đi tìm thành phần tiếp theo của vector nghiệm. Việc đi tìm này cũng giống như việc phát triển các `nhánh` .
- `Cận`: Tại mỗi node - ứng với 1 bài toán con, ta sẽ tính cận trên( hoặc dưới ) để tìm lời giải tốt nhất nếu ta tiếp tục phát triển nhánh này.
- `Cắt tỉa`: Tại 1 node - 1 bài toán con hay 1 hướng giải hay 1 nhánh nào đấy, ta so sánh cận trên - dưới của nó mới lời giải tối ưu nhất tới nay, nếu cận trên - dưới không tối ưu bằng lời giải này thì ta không phát triển nhánh này nữa. Đây gọi là cắt tỉa.
### Hàm minh họa:
```cpp!
Bound_and_Branch(j) //thành phần j của vector nghiệm
for(xj thuộc Aj){ // Duyệt mọi giá trị khả dĩ xj trong mọi ứng viên Aj. Ta có thể tưởng tượng xj thuộc (0, 1) trong bài toán Knapsack 01 chẳng hạn
Lưu lại tình trạng xj; //Sau sẽ dùng để Backtrack
if(Đã tìm được nghiệm mới){
if(Gía trị nghiệm mới > nghiệm tối ưu){
Chọn nó làm nghiệm tối ưu
}
}
else{
if(các giá trị cận f(x1, x2,..., xj) > nghiệm tối ưu){ //Phát triển nhánh có triển vọng
Bound_and_branch(j + 1);
}
}
Quay lui trạng thái trước xét xj; //Backtrack
}
```
## Đề cương mới C11: Trình bày Greedy Method(tham lam). Sử dụng vào bài toán Unbounded Knapsack:
### Greedy Method?
Trong thực tế, việc đi tìm nghiệm tối ưu cho 1 bài toán quá lớn là không thực tế. Vì vậy, thuật toán tham ăn được sử dụng để tìm 1 nghiệm chỉ cần `đủ tốt` là ok.
Ý tưởng chính của `Tham ăn` đó chính là:
- Quyết định được lựa chọn ở mỗi bước là quyết định tối ưu địa phương. Tùy theo bài toán mà ta đưa ra lựa chọn nào là tối ưu thích hợp.
- Có nghĩa là để giải bài toán lớn ta cũng sẽ bắt đầu từ các bài toán con, thì ở mỗi bài toán con ta sẽ lựa chọn hướng đi tốt nhất theo ngữ cảnh hiện tại. Chọn được hướng đi dẫn đến bài toán tiếp theo thì ta cũng sẽ thực hiện hành động tương tự chọn hướng đi tối ưu nhất trong ngữ cảnh bài toán tiếp theo này. Cứ như vậy cho đến khi nào ta tìm được nghiệm.
### Ứng dụng vào Unboundef Knapsack:
Gỉa sử ta có bài toán: 
Các bước thực hiện Greedy Method:
- B1: Trong số các đồ vật chưa được đưa vào balo, ta sẽ chọn đồ vật có đơn giá lớn nhất để đưa vào balo với số lượng nhiều nhất có thể (tức là thêm $T = W/(trọng lượng vật đó)$).
- B2: Sau khi thêm thì tải trọng của balo chỉ còn lại là $W' = W - T.trongluongdovat$. Nếu như tải trọng lúc này là 0 hoặc là đã hết đồ vật để thêm vào balo thì nghĩa là ta đã tìm được nghiệm. Nếu không thì quay lại B1.
Với các bước như vậy, bài toán trên sẽ được giải như sau:
- Đầu tiên, ta có thể đưa 2 vật 1 vào balo và giờ balo sẽ có giá trị là: `20`
- Sau khi đưa các vật 1 vào balo, thì lúc này tải trọng của balo sẽ chỉ còn có thể chứa được đồ vật có trọng lượng là `1` mà thôi nên không thể đưa vật 2 vào balo được mà chỉ có thể đưa 1 vật 1 vào balo.
- Sau đó, W của balo lúc này chỉ còn `0` tức là ta tìm được 1 nghiệm là `21`. Có thể thấy rằng đây hoàn toàn không phải nghiệm tối ưu nhất, nhưng nó vẫn đủ tốt khi chỉ thua kém nghiệm tối ưu 1 đơn vị.
## Đề cương mới câu cuối cùng: Trình bày ưu nhược điểm của (MERGE, QUICK, HEAP) - SORT. Nhận xét khi sử dụng chúng:
### Merge sort:
#### Ưu điểm:
Không có trường hợp tệ nhất: Đối với mọi mảng nếu chạy qua thuật toán Merge sort đều sẽ tốn chi phí thời gian là: $O(nlogn)$
#### Nhược điểm:
Độ phức tạp về không gian lớn hơn cả 2 thuật toán sắp xếp còn lại. Vì phải tạo các mảng phụ trong khi sắp xếp, điều này khiến cho giải thuật cần đến khoảng 2n phần tử nhớ.
### Quick sort:
#### Ưu điểm:
Thuật toán sắp xếp này cũng giống như Merge sort khi mà độ phức tạp thời gian trung bình sẽ là: $O(nlogn)$. Trong thực tế, nếu các phần tử trong mảng cần sắp xếp gần như là ngẫu nhiên thì thuật toán này tỏ ra vô cùng hiệu quả và có thể nhanh hơn Merge hay Heap.
Độ phức tạp không gian cũng là 1 ưu điểm: vì ta không cần phải tạo mảng phụ nên chi phí bỏ ra chỉ là khoảng O(logn) - số lần đệ quy chia mảng ra thành 2 phần.
#### Nhược điểm:
Thuật toán Quick sort lại có `Worst Case` của nó: Khi mà Time và Space complex lần lượt là $O(n^2)$ và $O(n)$
Tại sao lại xảy ra điều này: Nếu ta chọn 1 pivot xấu (giả sử như chọn đầu hoặc cuối và chúng là phần tử lớn nhất hoặc nhỏ nhất trong mảng). Lúc này, mỗi khi `partion` được chạy, nó sẽ chia mảng thành 2 phần với bên trải hoặc phải cực ít phần tử hoặc không có gì và bên còn lại chứa ố lượng phần tử gần như ban đầu. Vậy, nếu mảng gần như đã được sắp xếp thì trường hợp trên sẽ diễn ra liên tục: Ta sẽ chia mảng thành gần như $O(n)$ mảng con, với mỗi mảng con ta chạy hàm `partion` duyệt từ đầu đến cuối sẽ tốn trung bình $O(n)$ chi phí thời gian
=> Toàn bộ quá trình sẽ khiến ta tốn khoảng $O(n*n)$ phức tạp thời gian (Not so good).
### Heap sort:
#### Ưu điểm:
Cũng giống như MergeSort, thuật toán này có độ phức tạp thời gian trung bình (kể cả xấu nhất) là $O(nlogn)$.
- Ta chạy hàm `swift_down` cho `(n-2/2)` phần tử đầu tiên để tạo Heap. Hàm `swift_down` có thời gian chạy trung bình chỉ khoảng $O(logn)$ cho 1 cây cân bằng.
- Sau đó trong hàm Heapsort ta cũng liên tục chạy hàm `swift_down` cho (n-1) phần tử trong mảng. Vậy thì tổng độ phức tạp thời gian sẽ khoảng $O(nlogn)$
- Gộp lại, từ build heap cho đến sắp xếp, ta cũng chỉ mất khoảng $O(nlogn)$ chi phí thời gian.
=> Ta có thể thấy rằng, nếu như mảng gần như được sắp xếp ngược lại theo cách ta mong muốn, thì đây là trường hợp tối ưu nhất cho Heapsort
Đây có cũng là giải thuật giúp tiết kiệm bộ nhớ, vì không phải dùng đệ quy hay tạo mảng phụ nên chi phí không gian chỉ còn là $O(1)$
#### Nhược điểm
Heapsort được cho là có thời gian chạy trung bình kém hơn thời gian chạy trung bình của Quicksort do nó cần nhiều lần hoán đổi các phần tử hơn
Heapsort cũng có debug và hình dung hơn vì phải thao tác trên cây trừu tượng.
### Nhận xét và đánh giá:
- Thuật toán `Heap & Quick sort` được sử dụng nhiều hơn do đạt hiệu quả cao hơn Merge sort trên thực tế. Merge sort có cũng không kém hiệu lực về mặt thời gian nhưng độ yêu cầu khoonng gian của nó chính là điểm yếu chết người.
- Thuật toán Quicksort được dùng thường khi mà mảng có cấu trúc ngẫu nhiên. Nếu mảng có cấu trúc gần như đã được sắp xếp thì việc chọn pivot kém hiệu quả sẽ gây ra sự kém hiệu lực về mặt thời gian cho thuật toán này.
- Heapsort sẽ trở nên vô cùng mạnh mẽ nếu như cầu trúc mảng gần như đã được sắp xếp ngược lại so với điều kiện sắp xếp mà ta yêu cầu.
# Phần bài tập:
## C1: Skip
## C2: Biết thứ tự duyệt cây nhị phân theo thứ tự trước và giữa, hãy dựng lại cây nhị phân. Ví dụ thứ tự trước là: A B D E H C F I G, thứ tự giữa là: D B H E A F I C G.
Đây là dạng bài chuyển hướng duyệt cây về lại cây gốc, may mắn là chúng ta không cần code vì nó phải tư duy đệ quy + tìm node giữa khá phức tạp, câu này mà chỉ cần vẽ lại cây.
### Dạng bài dựng cây từ Preorder và Inorder:
Đây là dạng bài t thấy khá là tricky, để làm được ta sẽ phải nắm rõ cách duyệt BT theo `Pre - Inorder`.
- `Preorder`: (N->L->R) Với cách duyệt cây thế này, ta thấy rằng gốc của cây luôn là phần tử đầu tiên.
- `Inorder`: (L->N->R) Với cách duyệt cây thế này, ta thấy rằng nếu biết được node gốc của cây thì ta thấy rằng bên trái nó là toàn bộ nhánh trái và bên phải nó là toàn bộ nhánh phải.
Ta sẽ lấy 1 ví dụ ngắn hơn bài này: 
- PR là `Preorder`, IN là `Inorde`.
### Cách làm:
Để ý tới tính chất ta vừa bàn ban nãy, ta nhận ra rằng node đầu tiên của `Pr` chính là gốc của cây:
- Nếu ta tìm phần tử `1` trong `In`, ta được phần bên trái của nó là toàn bộ node bên trái, cùng với nhánh phải bên phải. Đồng thời, nếu tính từ ô của `1` trong `In` thì `Pr` cũng có thể được chia thành 2 phần nhánh trái và nhánh phải node gốc của cây(số node tính từ đầu cho đến node `1` của `In` là các số các phần tử nhánh trái có thể xác đjnh được tính từ phần tử 2 bên trái, nhánh phải sẽ là phần còn lại).
- Áp dụng quy tắc trên tương tự với nhánh trái và nhánh phải của `1` - hay ta gọi nó là node giữa `mid` cho đến khi nào duyệt xong toàn bộ cả 2 `Pr, In`, ta đạt được 1 thuật toán đệ quy để chuyển từ `In, Pr` để thành cây hoàn chỉnh.
### Code và đáp án của đề:
- Code t sẽ dùng Python, C sẽ phức tạp hơn khá nhiều do ta cần tự xây hàm `cắt mảng` và `tìm ô của 1 phần tử trong mảng`
```python!
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
root.left = self.buildTree(preorder[1:mid + 1], inorder[:mid])
root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
return root
```
- Đáp án: 
## C3: Biết thứ tự duyệt cây nhị phân theo thứ tự giữa và sau, hãy dựng lại cây nhị phân. Ví dụ thứ tự giữa là: D H B E A F C I G, thứ tự sau là: H D E B F I G C A.
Sau khi hoàn thành xây dựng cầy là `In, Preorder`, dạng xây cây từ `In,Post` order thực ra chỉ là làm ngược lại so với dạng kia 1 chút.
### Cách làm:
- Đọc lại phần duyệt cây bằng stack ở phần trên, ta nhận ra rằng bản chất của duyệt cây theo `Postorder` là việc duyệt cây theo `Preorder` nhưng ưu tiên duyệt phải trước rồi đọc ngược lại.
- Hiểu được điều này, vẫn theo lối logic cũ, khác là gốc của cây bây giờ sẽ là phần tử cuối cùng của `Post`, ta sẽ tiến hành xây cây từ phải sang trái, và tìm mid bằng cách duyệt `Post` từ phải sang trái thay vì trái sang phải như dạng cũ.
### Code và đáp án đề:
```python!
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if not inorder or not postorder:
return None
root_val = postorder[len(postorder) - 1]
root = TreeNode(root_val)
mid = inorder.index(root_val)
root.left = self.buildTree(inorder[:mid], postorder[:mid])
root.right = self.buildTree(inorder[mid+1:], postorder[mid:len(postorder) - 1])
return root
#len(arr) -> trả về số phần tử của 1 mảng/string
```
- Đáp án: 
## C4:
Cách dùng quy hoạch động ae xem trong link `Knapsack`:
### Code:
```cpp!
Dp(W, val, wt){
n = len(val);
dp[n + 1][W + 1];
for(int i = 0; i <= n; i ++){
for(int j = 0; j <= W; j ++){
dp[i][j] = 0;
}
}
for(in i = 1; i <= n; i++){
for(int j = 1; j <= W; j++){
pick = 0;
if(wt[i - 1] <= j){
pick = val[i - 1] + dp[i][j - wt[i - 1]];
}
notpick = dp[i - 1][j];
dp[i][j] = max(pick, notpick);
}
}
}
```
## C5:
### Phương Pháp Nhánh Cận?
Ta có các đơn vị được ghim trong phần đầu ảnh.
- Đầu tiên, ta sẽ cần sắp xếp theo chiều giảm dần đơn giá của các đồ vật (Gía trị / trọng lượng)
- Bước đầu tiên, giả sử như ta không cho gì vào balo, thì lúc này `T` hay `M` đều là 0, `W = 7` và `C = 21`.
- Ta đang giải dạng Unbounded Knapsack nên từ những bước sau, tại mỗi mức ta thử đưa dần phần tử từ đầu đến cuối, nếu đưa thì chia ra các trường hợp đưa (Nhiều nhất cho đến ít nhất - hay không đưa). Tính toán các giá trị `T` và `C`.
- Khi mà tìm được 1 node có `W = 0` hoặc đã tới giới hạn đồ vật thì ta đã tính được 1 nghiệm mới, so sánh nghiệm này với `M` và nếu nó lớn hơn thì ta lấy `M = T`.
- Đặc biệt, nếu nhánh nào tìm được `T` Lớn nhất, ta thử coi nó là M và cắt tỉa những nhánh có `C` nhỏ hơn M.
- Cứ như vậy cho đến khi không thể phát triển chiều sâu cây được nữa (các lá có W = 0, hết đồ vật,...). Thì ta chọn Node có `T` lớn nhất.
->`UPDATE`: Ở node chọn x2 = 1 thì cận trên của nó chỉ là 19.5 THÔI NHÉ. Đồng thời bài này ta cũng có thể cắt tỉa toàn bộ các nhánh: x1 = 2; x1 = 1 và x1 = 0 do cận trên của chúng đã bé hơn 20 rồi.
## C6: Minh họa Quicksort:
```
10 7 31 12 9 30 14
```
### Code giải:
```cpp!
partion(arr, l , r){
pivot = arr[l];
i = r + 1;
for(j = r; j > l; j --){
if(arr[j] > pivot){
i --;
swap(arr[j], arr[i]);
}
}
i --;
swap(arr[j], arr[i]);
return i;
}
Quick(arr, l, r){
if(l < r){
pivot = partion(arr, l, r);
Quick(arr, l, pivot - 1);
Quick(arr, pivot + 1, r);
}
}
```
### Visual:
- Chạy Partion lần 1: Mảng bị chia: 
- Chạy Partion lần 2 với mảng bên trái rồi chạy lần 3 cho mảng bên phải: 
- Mảng trái được sắp xếp rồi, ta xét mảng con bên trái mảng bên phải của pivot lần Partion đầu tiên, chạy Partion cho nó:
- Sau khi chạy thì ta thấy rằng mảng đã thành công được sắp xếp.
## C10: Duyệt Graph:
- Duyệt BFS(Theo chiều rộng):
2 Mảng kết quả BFS này đều là hợp lệ, chúng có thứ tự khác nhau do ta đã chọn đỉnh để bắt đầu khác nhau.
- Duyệt DFS(Theo chiều sâu): Ta lấy điểm bắt đầu là 7
## C7: Minh họa Heapsort
### Code giải:
```cpp!
swift_down(arr[], r, n){
v = arr[r];
while(r*2 + 1 <= n - 1){
c = r*2 + 1;
if(c + 1 < n && arr[c + 1] > arr[c]){
c += 1;
}
if(arr[c] < v){
break;
}
arr[r] = arr[c];
r = c;
}
arr[r] = v;
}
heaplify(arr, n){
for(i = (n - 2)/2; i >= 0; i--){
swift_down(arr, i, n);
}
}
heap_sort(arr, n){
heaplify(arr, n);
for(i = n - 1; i > 0; i --){
swap(arr[i], arr[0]);
swift_down(arr, 0, i);
}
}
```
### Visual:
Như ta có thể thấy câu nhị phân của đề bài cho bản chất đã là 1 Heap, nên giờ ta sẽ mô phỏng quá trình diễn ra của hàm Heapsort mà thôi:
## C8: Minh họa MergeSort:
## mệt qá đéo code nữa:
### Minh họa lun:
À mà thôi vãi cả l 11 số minh họa gãy tay mất: Xem ảnh trường hợp khác đơn giản hơn nhé hihihihihi:
## C9: Cài đặt cây nhị phân tìm kiếm
```cpp!
Insert_node(root, val){
newNode;
newNode->val = val; newNode->left = NULL; newNode->right = NULL;
if(root == NULL){
root = newNode;
return;
}
cur = root;
prev = NULL;
while (cur != NULL){
if(val > cur->val){
prev = cur;
cur = cur->right;
}
else{
prev = cur;
cur = cur->left;
}
}
if (val > prev->val){
prev->right = newNode;
}
else{
prev->left = newNode;
}
}
```
Theo như Logic này, ta chạy InsertNode từ đầu đến cuối mảng, ta được cây:
## C11: Duyệt Graph P2:
- Duyệt theo chiều rộng (lấy đỉnh 1 làm điểm xuất phát): 
- Duyệt theo chiều sâu (vẫn lấy đỉnh 1 làm đỉnh xuất phát):
# Phần giải thuật:
## C1:
```cpp!
add_node(Pdau,Pcuoi,X, Q
if(Q == NULL){
return;
}
newNode = malloc();
newNode->L = NULL;newNode->R = NULL; newNode->DATA = X;
if(Pdau == NULL){
Pdau = newNode;
Pcuoi = Pdau;
return;
}
else if (Q == Pdau){
newNode->R = Pdau;
Pdau->L = newNode;
Pdau = newNode;
return;
}
pre = Q->L;
newNode->R = Q;
Q->L = newNode;
pre->R = newNode;
newNode->L = pre;
}
```
## C2:
```cpp!
delete_node(Pdau,Pcuoi,Q){
if(Q == NULL){
return;
}
if(Q == Pdau){
if(Pdau->R == NULL){
free(Q);
Pdau = NULL;
return;
}
Pdau->R->L = NULL;
Pdau = Pdau->R;
free(Q);
return;
}
else if(Q == Pcuoi){
pre = Pcuoi->L;
pre->R = NULL;
free(Pcuoi);
Pcuoi = pre;
return;
}
pre = Q->L;
pre->R = Q->R;
Q->R->L = pre;
free(Q);
}
```
## C3:
### Phân tích
Đây là biến thể của dạng bài nối 2 LinkedList được sắp xếp sẵn. Nhìn vào đề ta thấy rằng ta cần tạo 1 LinkedList kết quả C là tổng của 2 LinkedList A, B với quy tắc cộng là:
- Các số hạng có cùng số Mũ thì ta cộng Hệ số của chúng.
- Nếu có số hạng tồn tại trong A hoặc B nhưng không tồn tại trong số hạng còn lại thì ta chỉ cần thêm số hạng đó vào C.
- Ta thấy rằng việc cần làm ở đây là việc nối 2 thằng A, B với nhau thành 1 LinkedList C.
### Solution
Đây chính là phần đặc biệt của bài này, nếu ta có 2 số hạng mang cùng 1 số mũ thì lúc đó thay vì nối cả 2 Node trong A, B thì ta chỉ chọn 1 trong 2 Node, và Node đó chứa tổng Hệ số.
```cpp!
else if(l1->MU == l2->MU){
l1->HSO += l2->HSO;
cur->next = l1;
cur = l1;
l1 = l1->next //Ta sẽ phải cập nhật cả con trỏ duyệt A, B trong trường hợp này!
l2 = l2->next;
}
```
Sol:
```cpp!
res(A, B){
dummy = malloc();
cur = dummy;
l1 = A; l2 = B;
while(l1 != NULL && l2 != NULL){
if(l1->MU < l2->MU){
cur->next = l1;
cur = l1;
l1 = l1->next;
}
else if(l1->MU == l2->MU){
l1->HSO += l2->HSO;
cur->next = l1;
cur = l1;
l1 = l1->next;
l2 = l2->next;
}
else{
cur->next = l2;
cur = l2;
l2 = l2->next;
}
}
if(l1 != NULL){
cur->next = l1;
}
if(l2 != NULL){
cur->next = l2;
}
return dummy->next;
```
### Phác Method:
```cpp!
Attach(HSO, MU, T){ // Đây là đưa các phần tử hạng vào biểu thức kết quả C
ELE = malloc(); ELE->HSO = HSO; ELE->MU = MU;
if(T == NULL){ //Nếu như C chưa có phân tử hạng nào, ta gán nó là ELE
C = ELE;
}
else{ // Nối C với phần tử tiếp theo cua nó
T->next = ELE;
}
T = ELE;
}
Cong_dathuc(A, B, C){ // Hàm cộng
DT1 = A; DT2 = B; // 2 con trỏ DT1, DT2 giúp duyệt 2 đa thức A, B
C = NULL; // Tạo kết quả C, ban đầu chưa có gì thì là NULL
while(DT1 != NULL && DT2 != NULL){ // Khi cả 2 đa thức vẫn còn phần tử
if(DT1->MU == DT2->MU){ // Nếu 2 phần tử của A và B có số mũ giống nhau
HSO = DT1->HSO + DT2->HSO; //Hệ số phần tử được thêm vào C sẽ là tổng của 2 Hệ số phần tử A, B
if(HSO != 0){ // Nếu Hệ số khác 0, ta nối nó vào kết quả
ATTACH(HSO, DT1->MU, T);
}
DT1 = DT1->next; //Duyệt đến phần tử tiếp theo của A, B
DT2 = DT2->next;
}
else{ //Nếu số mũ 2 phần tử khác nhau, ta sẽ chọn phần tử nào có phần tử cao hơn thì cho vào kết quả trước.
if(DT1->MU > DT2->MU){
Attach(DT1->HSO, DT1->MU, T);
DT1 = DT1->next;
}
else{
Attach(DT2->HSO, DT2->MU, T);
DT2 = DT2->next;
}
}
}
// Sau khi 1 trong 2 đa thức đã hết phần tử, ta sẽ chỉ cần đưa nốt phần tử của đa thức còn lại vào kết quả
while(DT1 != NULL){
Attach(DT1->HSO, DT1->MU, T);
DT1 = DT1->next;
}
while(DT2 != NULL){
Attach(DT2->HSO, DT2->MU, T);
DT2 = DT2->next;
}
T->next = NULL;
return C;
}
```
## C4: (PHẦN ĐẦU NHÉ)
### Phác Method
```cpp!
Dinhgiabieuthuc(){
// giải thuật này sử dụng stack S, trỏ bởi T, lúc đầu S rỗng nên T = -1
do{
đọc phần tử X trong biểu thức
if(X là toán hạng){
Push(S, T, X);
}
else{
B = Pop(S, T);
A = Pop(S, T);
// Tác động toán tử X vào A và B, gán giá trị cho W và đưa nó vào S
W = A X B;
Push(S, T, W);
}
}
while(Chưa gặp dấu kết thúc biểu thức);
Res = Pop(S, T); // Kết quả thuật toán chính là giá tị cuối cùng trong stack
return R;
}
```
## C5 + C6 (PHẦN ĐẦU NOTE)
## C7:
### Binary Search
Cho 1 mảng gồm `n` phần tử đã được sắp xếp sẵn. Để tìm phần tử có giá trị `k` trong mảng. Cách naive là duyệt từ đầu đến cuối, cách này sẽ tốn Time complex là $O(n)$ cho trường hợp xấu nhất.
Lợi dụng việc mảng đã được sắp xếp sẵn, ta có thể giảm độ phức tạp xuống:
### Cách làm:
Đặt 2 con trỏ đầu và cuối mảng `l & r`, tại mỗi bước ta tiến hành:
- Tính giá trị `mid = (l + r) / 2`, so sánh giá trị của k với giá trị của `arr[mid], arr[r], arr[l]`.
- Nếu tìm được ô có chứa giá trị k thì thì return ô đó là xong.
- Còn nếu không, nếu $k > arr[mid]$ tức là ta hiểu rằng chỉ cần tiếp tục tìm kiểm ở nửa bên phải còn lại của mảng. Lý do là bởi vì mảng đã được sắp xếp sẵn, bên trái của mid luôn nhỏ hơn và bên phải luôn lớn hơn nó.
- Tương tự nhưng ngược lại nếu $k < arr[mid]$.
```cpp!
Binary_search(arr[], len_arr, k){
l = 0;
r = len_arr - 1;
while(l <= r){
mid = (l + r) / 2;
if(k == arr[mid]){
return mid;
}
else if(k > arr[mid]){
l = mid + 1;
}
else{
r = mid - 1;
}
}
printf("Deo thay gi");
}
```
Đánh giá: Ta thấy rằng ta liên tục chia đôi mảng để tìm kiếm, vì vậy trong trường hợp xấu nhất ta cần chia mảng cho đến khi nào không thể chia được nữa. Time complex sẽ khoảng $O(logn)$ cho mảng có `n` phần tử.
## C8
```cpp!
search(root, k){
if(root == NULL){
root = CreatNode(k);
return root;
}
cur = root;
prev = NULL;
while (cur != NULL){
if(cur->key == k){
return cur;
}
else if(cur->key > k){
prev = cur;
cur = cur->right;
}
else{
prev = cur;
cur = cur->left;
}
}
if(k > prev->key){
prev->right = CreatNode(k);
return prev->right;
}
else{
prev->left = CreateNode(k);
return prev->left;
}
}
```
## C9: Backtracking 8 quân hậu:
Bài này là 1 bài toán kinh điển sử dụng Backtracking. Ta cần đặt 8 - hay có thể là n quân hậu vào bàn cờ sao cho chúng không thể ăn nhau. Vì đây là 1 vấn đề chưa hề có công thức giải cụ thể vì vậy ta chỉ có thể BruteForce bằng Backtracking để tìm toàn bộ cách đặt hậu.
### Cách làm:
- Tại mỗi hàng, ta tiến hành đặt thử lần lượt 1 quân hậu từ ô 1 đến ô n, sao cho nó không cùng cột, đường chéo của các con hậu khác.
- Cứ tiếp tục thử đặt như vậy với mỗi hàng, cho đến khi nào đặt được con hậu cuối cùng vào hàng cuối cùng. Lúc này ta đã tìm được 1 cách đặt hậu. Giờ thì chỉ cần tiến hành bỏ cách đặt con hậu hiện tại ở hàng hiện tại và thử xem có đặt được vào ô khác nữa hay không.
- Cứ như vậy, sau khi tìm được toàn bộ cách đặt con hậu hiện tại ở hàng hiện tại này rồi, thì ta bỏ cách đặt hậu ở hàng trước và tiếp tục thử với logic như trên.
```cpp!
len_stack(stack){
if(stack->T == -1){
return 0;
}
return stack->T + 1;
}
not_in(stack, k){
if(stack->T == -1){
return 1;
}
for(int i = 0; i < len_stack(stack); i++){
if(k == stack->data[i]){
return 0;
}
}
return 1;
}
backtracking(r, res, cols, dia1, dia2, n){
if (r == n){
res += 1;
return;
}
for(int c = 0; c < n; c++){
if(not_in(cols, c) == 1 && not_in(dia1, c + r) == 1 && not_in(dia2, c - r) == 1){
push(cols, c);
push(dia1, c + r);
push(dia2, c - r);
backtracking(r + 1, res, cols, dia1, dia2, n);
pop(cols);
pop(dia1);
pop(dia2);
}
}
}
solution(n){
res = 0;
cols; dia1; dia2;
init(cols), init(dia1); init(dia2);
backtracking(r, res, cols, dia1, dia2, n);
return res;
}
```
Ta cũng có thể dùng mảng để giải bài này kèm theo đó là in kết quả, nhưng sẽ phức tạp hơn 1 chút:
```cpp!
In_kq(res){ // 1 nghiệm hợp lệ sẽ ở dạng mảng 1 chiều: ô tương ứng với hàng, giá trị ở ô đó là giá trị cột đăth hậu ở hàng đó.
for(i = 1; i <= 8; i ++){
printf("%d ", res[i]);
}
}
backtracking(r, cols, dia1, dia2, res){
if(r > 8){
In_kq(res);
return;
}
for(c = 1; c <= 8; c ++){
if(cols[c] == 0 && dia1[c + r] == 0 && dia2[c - r + 8] == 0){ // Vì mảng không thể truy cập vào chỉ số ô là âm, nên ta cần cộng thêm 8 để giữ cho c - r luôn dương
res[r] = c;
cols[c] = 1;
dia1[c + r] = 1;
dia2[c - r + 8] = 1;
backtracking(r + 1, cols, dia1, dia2, res);
cols[c] = 0;
dia1[c + r] = 0;
dia2[c - r + 8] = 0;
}
}
}
8th_queen(){
cols[20];dia1[20];dia2[20];res[9];
for(i = 1; i <= 19; i++){
cols[i] = 0; dia1[i] = 0; dia2[i] = 0;
}
backtracking(1, cols, dia1, dia2, res);
}
```
## C10: Sử dung giải thuật tham lam giải bài toán tô màu đồ thị:
### Ý tưởng chính:
Việc áp dụng thuật toán tham lam vào bài này nghĩa là t muốn tô ít màu nhất có thể - oh this is minimization problem!
```cpp!
Greedy(i, mau_moi){
Tạo tập Dinh_to là mảng rỗng chứa những đỉnh đã được tô bởi mau_moi hiện tại;
Tô mau_moi cho đỉnh i;
Đưa đỉnh i vào mảng Dinh_to;
for(với mỗi đỉnh k chưa được tô màu){
if(Nếu k không được nối bởi đỉnh nào được tô mau_moi - hay có thể nói là không kề với các đỉnh trong tập Dinh_to){
Tô mau_moi cho đỉnh k;
Đưa k vào tập Dinh_to; // Đoạn này sách nói sai nhé
}
}
}
```
Nói chung là:
- Duyệt tửng đỉnh của đồ thị, nếu như đỉnh này chưa được tô màu thì đưa đỉnh này + màu mới vào hàm `Greedy`.
- Mỗi lần chạy Greedy ta cố gắng tô nhiều đỉnh nhất có thể bằng màu mới này.
- Lặp lại cho đến khi nào toàn bộ đỉnh đã được tô.
### Lời giải:
```cpp!
// Mảng Dinh_to chứa các đỉnh đã được tô bằng mau_moi hiện tại
// Mảng kq_to sẽ chữa kết quả tô mà của đồ thị
// A[i][j] là ma trận kề, biểu diễn 2 đỉnh i và j giữa chúng có cung nối hay không: 1 có 0 không
// biến so_dinh_to theo dõi có bao nhiêu đỉnh đã được tô bằng mau_moi hiện tại và đồng thời cũng giúp ta đánh dấu số lượng phần tử của mảng Dinh_to
Greedy(i, mau_moi){
kq_to[i] = mau_moi;
so_dinh_to = 1;
Dinh_to[so_dinh_to] = i;
for(k = 1; k <= n; k++){
// Check xem đỉnh k đã được tô màu chưa và đồng thời các đỉnh trong đã được tô bằng mau_moi có kề với đỉnh k hay không?
if(kq_to[k] == 0){ // Chưa được tô
j = 1;
check = 0;
while(check != 1 && j <= so_dinh_to){
if(A[k][Dinh_to[j]] == 1){ // Nếu như giữa đỉnh k và 1 đỉnh nào đó trong mảng Dinh_to có chứa 1 cung nối, thì nghĩa là ta bỏ qua đỉnh này
check += 1;
}
j ++;
}
if(check == 0){ //Nếu tìm được đỉnh hợp lệ: Tô màu cho k và đưa nó vào mảng Dinh_to đánh dấu rằng nó đã đc tô bởi màu mới.
kq_to[k] = mau_moi;
so_dinh_to ++;
Dinh_to[so_dinh_to] = k;
}
}
}
}
main(){
for(v = 1; v <= n; v++){
if(kq_to[v] == 0){
mau_moi ++;
Greedy(v, mau_moi);
}
}
}
```
## C11:
> Bài này là ta cần Minh Họa Callstack ae:
```cpp!
Factorial(n){
Bước 1 // Bảo lưu giá trị N và địa chỉ quay lui (Ta có thể hiểu ta đang push hàm vào Callstack)
Push(A, T, TEMREC);
Bước 2 //Check xem N đã là 0 chưa? - basecase
if(T.N == 0){ //Nếu là 0 rồi thì ta tiến hành đưa dần các phần tử ra khỏi callstack (Popstack)
Giaithua = 1; // Tạo biến giai thừa
goto Bước 4;
}
else{
PARA = T.N - 1;
ADDRESS = Bước 3;
}
goto Bước 1;
Bước 3 // Tính N!
Giaithua = T.N*Giaithua;
Bước 4 // Khôi phục giá trị N và địa chỉ quay lui của 1 phần tử nào trong callstack
TEMREC = Pop(A, T);
goto ADDRESS;
return Giai_thua;
}
```
| Số mức | Các bước thực hiện | Stack |
| --- | --- | --- |
|1| Bước 1: Push(A, - 1, (3, ĐCC - địa chỉ chính)) -> Bước 2: N != 0 => Para = 2, ADDRESS = Bước 3|[3, DCC]|
|2|Bước 1: PUSH(A, 0, (2, Bước 3)) -> Bước 2: N != 0 => Para = 1, ADDRESS = Bước 3| [3, DCC], [2, Bước 3]|
|3|Bước 1: Push(A, 1, (1, Bước 3)) -> Bước 2: N != 0 => Para = 0, ADDRESS = Bước 3|[3, DCC], [2, Bước 3], [1, Bước 3]|
|4|Bước 1: Push(A, 2, (0, Bước 3)) -> Bước 2: N = 0 => Giaithua = 1|[3, DCC], [2, Bước 3], [1, Bước 3], [0, Bước 3]|
|3|Bước 4: Pop(A, 3) -> Bước 3: Giai thừa = 1*1 |[3, DCC], [2, Bước 3], [1, Bước 3]|
|2|Bước 4: Pop(A, 2) -> Bước 3: Giaithua = 2*1| [3, DCC], [2, Bước 3]|
|1|Bước 3: Pop(A, 1) -> Bước 3: Giaithua = 3* 1| [3, DCC]]
||Pop(A, 0) -> goto DCC| RỖNG |
## C12: Chuyển biểu thức trung tố sang hậu tố
Phần đầu làm rồi nhé:
```cpp!
// Stack: hautom stack
// Ham nay tra ve 1 stack
Trung_sang_hau(trungto){
hauto;
c = 0;
stack;
while (trungto[c] != '\x0'){
token = trungto[c];
if(isalnum(token)){
push(hauto, token);
}
else if(token == '('){
push(stack, token);
}
else if(token == ')'){
while(Top(stack) != '('){
push(hauto, pop(stack));
}
pop(stack);
}
else{
if(isEmty(stack) != 1 && Uu_tien(Top(stack)) >= Uu_tien(token)){
push(hauto, pop(stack));
}
push(stack, token);
}
c ++;
}
while(isEmty(stack) != 1){
push(hauto, pop(stack));
}
return hauto;
}
```
## C13: Trình bày QuickSort, đánh giá Timecomplex trong trường hợp tốt nhất
```cpp!
partion(arr, l, r){
pivot = arr[r];
i = l - 1
for(j = l; j < r; i++){
if(arr[j] < pivot){
i++;
swap(arr[i], arr[j]);
}
}
i++;
swap(arr[i], arr[r]);
return i;
}
Quick(arr, l, r){
while(l < r){
pivot = partion(arr, l, r);
Quick(arr, l, mid - 1);
Quick(arr, mid + 1, r);
}
}
```
### Đánh giá
Trong trường hợp tốt nhất, mảng gần như đã bị random, thì lúc này thực chất công việc của ta là chia mảng ra thành 2 liên tục (sẽ tốn $O(logn)$) và gần như chỉ duyệt các mảng con tốn $O(n)$
Vì điều này, trong trường hợp tốt nhất: Time $O(nlogn)$
## C14: Trình bày Heapsort, đánh giá Time Complex với mảng có n phần tử:
```cpp!
swift_down(arr, r, n){
v = arr[r];
while(2*r + 1 <= n - 1){
c = 2*r + 1;
if(c + 1 < n && arr[c + 1] > arr[c]){
c = c + 1;
}
if(v > arr[c]){
break;
}
arr[r] = arr[c];
r = c;
}
arr[r] = v;
}
heaplify(arr, n){
for(i = (n-2)/2; i >= 0; i--){
swift_down(arr, i, n);
}
}
Heap_sort(arr, n){
heaplify(arr, n);
for(i = n - 1; i > 0; i--){
swap(arr[i], arr[0]);
swift_down(arr, 0, i)
}
}
```
### Đánh giá:
Trước khi sử dụng Heapsort thì ta phải xây dựng ctdl Heap từ mảng ban đầu:
- Ta tiến hành tạo heap từ các cây con trước(bắt đầu từ node cha sâu nhất -> gốc) bằng hàm swiftdown, độ phức tạp thời gian theo đó sẽ tốn từ $O(1)$ cho đến $O(logn)$. Vậy thì nếu ta chạy hàm swift_down cho (n - 2/ 2) phần tử trong mảng thì ta sẽ tồn tầm $O(n)$.
- Sau khi hoàn thành, ta tiến hành Heapsort bằng cách tráo đổi phần tử đầu với phần tử cuối, điều này cũng sẽ làm hỏng cấu trúc Heap đã xây ban đầu, nên cần chạy 1 hàm swiftdown để tái cấu trúc lại và mỗi lần như vậy sẽ tốn tầm $O(nlogn)$ nếu ta duyệt cả mảng.
- Cuối cùng, ta có độ phức tạp thời gian của cả thuật toán sẽ là: $O(n) + O(nlogn) = O(nlogn)$
## C15: Merge Sort và Đánh giá:
```cpp!
Merge(arr, l, m, r){
len1 = mid - l + 1;
len2 = r - mid;
arr1[len1];
arr2[len2];
for(i = 0; i < len1; i ++){
arr1[i] = arr[l + i];
}
for(i = 0; i < len2; i ++){
arr2[i] = arr[mid + 1 + i];
}
i = 0; j = 0; k = l;
while(i < len1 && j < len2){
if(arr1[i] < arr2[j]){
arr[k] = arr[1];
i++;
k++;
}
else{
arr[k] = arr2[j];
j++;
k++;
}
}
while(i < len1){
arr[k] = arr1[i];
i++;
k++;
}
while(j < len2){
arr[k] = arr2[j];
j++;
k++;
}
}
Merge_sort(arr, l, r){
if(l < r){
mid = (l + r) / 2;
Merge_sort(arr, l, mid);
Merge_sort(arr, mid + 1, r);
Merge(arr, l, mid, r)
}
}
```
### Đánh giá
Ta liên tục chia đôi mảng cho đến khi nào không thể chia được nữa (mảng con giờ chỉ còn 1 phân tử). Mảng gốc chia thành 2 mảng con, mỗi mảng con lại cứ chia đôi liên tục. Toàn bộ thao tác này tốn $O(logn)$ - tương ứng với số tầng đệ quy.
Sau khi chia xong, 2 mảng con của 1 mảng được trộn với nhau bằng hàm trộn `Merge` bắt đầu từ 2 mảng con có 1 phần tử bì bản chất chúng có thể được coi như 2 mảng đã được sắp xếp. Cứ như vậy, với mỗi mảng con ta duyệt toàn bộ các phần tử luôn. Nên tại mỗi tầng đệ quy ta đều duyệt với độ phức tập khoảng $O(n)$, nên tổng thời gian thuật toán thực hiện sẽ tốn $O(n*logn)$ trong mọi trường hợp kể cả xấu nhất.
## C16:
```cpp!
delete_node(root, key){
if (root == NULL){
return NULL;
}
if (key > root->key){
root->P_R = delete_node(root->P_R, key);
}
else if(key < root->key){
root->P_L = delete_node(root->P_L, key)
}
else{
if(root->P_L == NULL){
return root->P_R;
}
else if(root->P_R == NULL){
return root->P_L;
}
else{
cur = root->P_R;
while (cur->P_L != NULL){
cur = cur->P_L;
}
root->key = cur->key;
root->P_R = delete_node(root->P_R, cur->key);
}
}
return root;
}
```
### Đánh giá:
So với giải thuật tìm kiếm bổ sung trên BST, ta đều phải duyệt cây để tìm ra node chứa giá trị key: Chi phí trung bình phải bỏ ra là $O(h)$ với `h` là chiều cao của cây.
Điểm khác biệt ở đây là nếu ta tìm được node cần tìm, đối với Thuật toán tìm kiếm bổ sung, ta chỉ cần trả về giá trị hay trả về Node là xong và điều này chỉ tốn $O(1)$ phức tạp thời gian. Thuật toán xóa node cũng chỉ tốn 1 chi phí tương tự nếu như node cần xóa đó là node `lá` hoặc node `có 1 con duy nhất`. Nhưng nếu là 1 node trong thì việc tìm kiếm Inorder Successer rồi xóa nó đi sẽ mất khoảng $O(h)$ độ phức tạp thời gian.
Kết luận rằng dù 2 thuật toán sẽ tiêu tốn chi phí là $O(h)$ nhưng thuật toán Xóa Node thường sẽ mất chi phí nhiều hơn nếu ta muốn xóa 1 node trong.
## C17: Kiểm tra Valid BST
```cpp!
Valid(root, check, maximum, minimum){ //đầu vào check là 1 con trỏ
if(root == NULL){
return;
}
if(root->key >= maximum || root->key <= minimum){
check += 1;
return;
}
Valid(root->P_L, check, root->key, minimum);
Valid(root->P_R, check, maximum, root->key);
}
Valid_BST_check(root){
check = 0;
Valid(root, check, INT_MAX, INT_MIN); //Ta đưa địa chỉ của check vào hàm
if(check == 0){
return 0;
}
return 1;
}
```
- New Approach:
```cpp!
Valid(root, max, min){
if (root == NULL){
return True;
}
else if(root >= max || root <= min){
return False;
}
return Valid(root->P_L, root->key, min) && Valid(root->P_R, max, root->key);
}
Valid_BST(root){
return Valid(root, INT_MAX, INT_MIN);
}
```
## C18: Dijkstra
### Dijkstra?
#### Bài toán:
Ta được cho 1 đồ thị có hướng được biểu diễn bởi ma trận liền kề A.
Bài toán đặt ra là: Chọn 1 đỉnh xuất phát `s` (nguồn), hãy tìm đường đi ngắn nhất tới mọi đỉnh còn lại.
#### Ý tưởng của Dijkstra:
Đầu tiên, ta sẽ cần đánh dấu từ điểm nguồn `s`, đường đi tới các đỉnh còn lại là bao nhiêu:
- Nếu các đỉnh không có direct path từ s -> nó thì mặc định khoảng cách là vô hạn.
- Nếu đỉnh nào được nối trực tiếp vào s thì khoảng cách là cung.
Thuật toán sử dụng nguyên lý Greedy, tức tại mỗi bước, ta chọn đỉnh liền kề của đỉnh hiện tại sao cho đường đi tới đó là ngắn nhất, modify đường đi tới các đỉnh còn lại:
- Đầu tiên, chọn `s` nào đó làm điểm xuất phát, thực hiện đánh dấu lần đầu tiên. Đường đi từ `s -> s` luôn là 0.
- Từ `s`, chọn xem có đỉnh nào ngoài nó mà đường đi từ `s` đến đỉnh này là ngắn nhất.
- Khi đã chọn được đỉnh `u` thỏa mãn yêu cầu này rồi. Thử tính toán xem đường đi từ `s -> u` và đến các điểm xung quanh bằng công thức
- `D[u] + A[u][v] < D[v] ?`
- D[u] là khoảng cách từ `s -> u`.
- A[u][v] là khoảng cách `u -> v`
- D[v] là khoảng cách từ `s -> v`
- Ở lần này v chính là u do đây mới là lần đầu xem xét.
- Nếu công thức kia có thỏa mã, ta để `D[v] = vế trái`.
- Ta thấy đấy, đỉnh `s & u` đã được xem xét, ta sẽ tạo 1 mảng `S` chứa các đỉnh đã được xem xét.
- Quay trỏ lại Bước 3, ta tìm đỉnh nào chưa có trong `S` mà khoảng cách đến nó thấp nhất.
#### Mã giả trình bày ý tưởng Dijkstra:
```cpp!
Dijkstra(s){ // Bắt đầu từ nguồn s
Khởi tạo tập S, lúc này chỉ chứa nguồn s;
for(mỗi đỉnh v thuộc tập V - s){ //V là tập tất cả các đỉnh
D[v] = A[s][v]; //D: tập chứa khoảng cách từ s -> đỉnh ngoài nó
P[v] = s; //P: tập chứa đỉnh cuối cùng gần nhất dẫn đến đỉnh v. Khi mới khởi tạo, mỗi phần tử đều có giá trị là s do ta chỉ đi từ s-> các đỉnh ngoài nó
}
do{
Tìm đỉnh u thuộc tập V - S và đồng thời D[u] khác vô cực và D[u] nhỏ nhất;
if(tìm được u){
Thêm u vào tập S;
for(mỗi đỉnh v thuộc V - S){
if(D[u] + A[u][v] < D[v]){ //Thực hiện relaxation: giảm khoảng cách ban đầu đã thiết lập
D[v] = D[u] + A[u][v];
P[v] = u; // Nếu đi theo đường trung gian thì ta sẽ chỉnh lại đỉnh cuối cùng trước khi đi đến đỉnh v là đỉnh trung gian u.
}
}
}
}
while(tìm được u);
}
```
### Thực hiện trên đồ thị đã cho:
#### Code giải:
```cpp!
In_kq(s, v){
if(P[v] == s){
printf("\n(%d,%d) %d", s, v, A[s][v]);
}
Dinh_truoc = P[v];
In_kq(s, Dinh_truoc);
printf("\n(%d,%d) %d", Dinh_truoc, v, A[Dinh_truoc][v]);
}
Dijkstra(s){
for(v = 1; v <= n; v ++){
S[v] = 0;
D[v] = A[s][v];
P[v] = s;
}
S[s] = 1;
do{
Min = INT_MAX;
for(i = 1; i <= n; i++){
if(S[i] != 1 && D[i] < Min){
Min = D[i];
u = i;
}
}
//Perform Relaxation
if(Min < INT_MAX){
S[u] = 1;
for(v = 1; v <= n; v++){
if(S[v] != 1 && D[u]+A[u][v] < D[v]){
D[v] = D[u] + A[u][v];
P[v] = u;
}
}
}
}
while(Min < INT_MAX); // tìm được 1 đỉnh u phù hợp khi mà ta tìm được D[u] và đưa nó làm Min
}
main(){
s = 1;
Dijkstra(1);
for(v = 1; v <= n; v++){
if(D[v] == INT_MAX){
printf("Từ %d đến %d không có cung đường nào", s, v);
}
else{
printf("Cung đường ngắn nhất đi từ %d đến %d dài %d", s, v, D[v]);
In_kq(s, v);
}
}
}
```
Bảng thể hiện thay đổi của D và P trong lúc thực hiện Dijkstra:
## C19: Floyd
### Floyd:
Với giải thuật Dijkstra, nếu muồn tìm đường đi ngắn nhất tới các đỉnh tới mọi đỉnh thì ta cần chạy `n` lần Dijktra -> Không tối ưu 1 chút nào.
Giải thuật `Floyd` sinh ra để giải quyết nhu cầu này, và nó sẽ chỉ thao tác trên 1 Ma trận duy nhất.
Bằng cách áp dụng Dynamic Programming - giải các bài toán con theo Bottom up. Gỉa sử ta có ma trận $D_k(s, v)$:
- Mỗi ô lưu đường đi ngắn nhất từ: s->v
- Chỉ được phép đi qua trung gian từ: 1->k.
Ta tính bảng $D_k(s, v)$ với hệ số trung gian k tăng dần. Khi nào `k = n` thì lúc này ta có được bảng chứa kết quả.
### Example:
```cpp!
In_kq(s, v){ //In đường đia từ s->v
if(P[s][v] == s){
printf("\n(%d, %d) %d", s, v, D[s][v]);
}
Dinhtruoc = P[s, v];
In_kq(s, Dinhtruoc);
printf("\n(%d, %d) %d", Dinhtruoc, v, D[Dinhtruoc, v]);
}
Floyd(){
for(i = 1; i <= n; i++){ // Điền ma trận D0, thật ra ta chỉ cần copy chỉ số của ma trận kề A biểu diễn đồ thị là được
for(j = 1; j <= n; j++){
D[i][j] = A[i][j];
P[i][j] = i;
}
}
for(k = 1; k <= n; k++){
for(i = 1; i <= n; i ++){
for(j = 1; j <= n; j++){
if(D[i][k] + D[k][j] < D[i][j]){
D[i][j] = D[i][k] + D[k][j];
P[i][j] = P[k][j];
}
}
}
}
}
main(){
Floyd();
for(s = 1; s <= n; s ++){
printf("Các đường đi ngắn nhất từ đỉnh s\n");
for(v = 1; v <= n; v ++){
if(D[s][v] == INT_MAX){
printf("Từ %d đến %d không có cung đường nào\n" s, v);
}
else{
printf("Cung đường ngắn nhất đi từ %d đến %d là %d\n", s, v, D[s][v]);
printf("Đi qua các cung là: ");
In_kq(s, v);
}
}
}
}
```
## C20: Kahn & Topological Sort
### Kahn, Topo?
#### Đồ thị có hướng không chu trình - DAG:
Ta chỉ có thể áp dụng Topological Sort và giải thuật Kahn khi mà đồ thị ta đang làm việc là 1 đồ thị: `Có hướng không chu trình` -> Tức là đồ thị có các cung nối đỉnh là mũi tên có hướng đồng thời nếu xuất phát từ 1 đỉnh thì ta không thể quay lại chính nó.
#### VD: Đây là 1 DAG:
#### Topological Sort?
Hiểu đơn giản sắp xếp Topo nghĩa là ta duyệt 1 đồ thị DAG:
- Duyệt các đỉnh không có direct path dẫn đến nó.
- Khi duyệt được 1 đỉnh, ta có thể coi đỉnh này không cần phải quan tâm trong đồ thị. Nghĩa là đỉnh kề với nó lúc này có đỉnh trước dẫn đến không còn là nó nữa.
Cũng với VD trên, topological sort của nó có thể là: `1 2 3 4 5` nếu ta chọn đỉnh xuất phát là 1.
#### Giải thuật Kahn
```cpp!
Kahn(){
T = 0; // Khởi tạo stack
for(i = 1; i <= n; i ++){
if(V[i].COUNT == 0){ // Ta sẽ tiến hành đưa các phần tử có COUNT = 0 hay không có đỉnh nào nối đến nó vào stack, con trỏ T sẽ trỏ vào phần tử ở đỉnh stack
V[i].COUNT = T;
T = i;
}
}
for(v = 1; v <= n; v++){ // Bốc đỉnh stack, có n đỉnh thì ta bốc n lần và nếu đang bốc mà stack rỗng (T = 0) tức là đây không phải DAG.
if(T == 0){ // Nếu quá trình sắp xếp Topo diễn ra với n đỉnh chưa kết thúc mà stack đã rỗng - T = 0 thì nghĩa là đồ thị CÓ CHU TRÌNH
printf("Đồ thị không hợp lệ");
return;
}
else{ // Ta tiến hành Popstack
j = T; // Ta lấy đỉnh j ở đầu stack
printf(j); //In đỉnh j vào kết quả
T = V[j].COUNT; // Popstack -> Ta mô phỏng điều này bằng cách quay về đỉnh trước của đỉnh j
R = V[j].NEXT; // Con trỏ R duyệt Danh sách kề. Khi đỉnh j đã được duyệt thì nghĩa là ta sẽ bỏ đi nó trong đồ thị và các cung nối nó với các đỉnh kề. Các đỉnh kề với nó lúc này sẽ bị mất đi 1 đỉnh trước chúng.
while(R != NULL){ // Duyệt sách sách của đỉnh j
i = R->VERTEX; // Đỉnh kề của j
V[i].COUNT -= 1; // Giảm số đỉnh liền trước của của đình kề j đi 1 đơn vị
if(V[i].COUNT == 0){
V[i].COUNT = T; // Sau khi giản, nếu như ta tìm được đỉnh nào không có đỉnh nào trước nó, ta đưa nó vào stack để duyệt vào kết quả
T = i;
}
R = R->NEXT;
}
}
}
}
```
### Chữa bài tập
=> Đây sẽ là danh sách kề biểu diễn đồ thị: 
Các diễn biến của stack theo thuật toán Kahn như sau:
- B1: Khởi tạo stack.
- B2: Đưa phần tử đầu stack là 1 ra ngoài, cập nhật COUNT của 2, 3 và cập nhật lại stack:
- B3: Đưa phần tử đầu stack là 3 ra ngoài, cập nhật COUNT của 4, 5 và cập nhật lại stack:
- B4: Đưa phần tử đầu stack là 2 ra ngoài, cập nhật COUNT của 4,5 và cập nhật lại stack: 
- B5: Đưa phần tử đầu stack là 4 ra ngoài, cập nhật COUNT của 5, 6 và cập nhật lại stack: 
- B6: Đưa phần tử đầu stack là 6 ra ngoài, cập nhật stack: 
- B7: Đưa nốt phần tử còn lại là 5 ra ngoài. T = 0: 
=> Kết quả: `1 3 2 4 6 5`
Sign in with Wallet
Connect another wallet