¶ Quy hoạch động cơ bản (Phần 2)
Bài viết được sưu tầm và bổ sung từ bài viết "Một số bài toán quy hoạch động kinh điển" của thầy Nguyễn Thanh Tùng, Tạp chí Tin học và Nhà trường số , năm .
Người viết: Nguyễn Anh Bảo - Đại học Bách Khoa Hà Nội
Reviewer:
- Hồ Ngọc Vĩnh Phát - Đại học Khoa học Tự nhiên, ĐHQG-HCM
- Ngô Nhật Quang - Trường THPT chuyên Khoa học Tự Nhiên, ĐHQGHN
¶ Giới thiệu
Ở phần trước, chúng ta đã được làm quen với khái niệm Quy hoạch động đồng thời xem xét một số bài toán điển hình. Bài viết này nhằm giới thiệu thêm một số bài toán quy hoạch động thường gặp khác.
¶ 1. Biến đổi xâu
Để thuận tiện cho việc trình bày và tính toán, trong mục ta sẽ quy ước các xâu đều bắt đầu từ chỉ số .
¶ 1.1. Mô hình
Cho hai xâu , có độ dài lần lượt là và , bắt đầu từ chỉ số . Ta muốn biến đổi xâu về xâu qua một số phép biến đổi thuộc các loại sau:
- Chèn kí tự vào sau kí tự thứ :
I i C,icó thể bằng- Thay thế kí tự ở vị trí thứ bằng kí tự :
R i C- Xoá kí tự ở vị trí thứ :
D iHãy tìm số ít nhất các phép biến đổi để biến xâu thành xâu .
Điều kiện: .
Ví dụ 1: ILoveVNOIILoveVNOIMore
| Lượt biến đổi | Phép biến đổi | A |
|---|---|---|
I 9 e |
ILoveVNOIe |
|
I 9 r |
ILoveVNOIre |
|
I 9 o |
ILoveVNOIore |
|
I 9 M |
ILoveVNOIMore |
Ví dụ 2: asrefghuarregular
| Lượt biến đổi | Phép biến đổi | A |
|---|---|---|
R 8 l |
asrefghlar |
|
R 7 u |
asrefgular |
|
D 5 |
asregular |
|
D 1 |
sregular |
|
D 1 |
regular |
Ví dụ 3: D9M12Y2022D1M1Y2023
| Lượt biến đổi | Phép biến đổi | A |
|---|---|---|
R 2 1 |
D1M12Y2022 |
|
R 10 3 |
D1M12Y2023 |
|
D 5 |
D1M1Y2023 |
¶ 1.2. Lời giải
Chú ý: Chỉ số bắt đầu của và là , không phải .
Đặt là xâu gồm kí tự đầu tiên của , là xâu gồm kí tự đầu của . Quy ước và là 2 xâu rỗng (có kí tự).
Ý tưởng bài toán này là quy hoạch động mảng - số phép biến đổi ít nhất để biến xâu thành xâu .
Dễ thấy và .
Ta đi tìm công thức truy hồi:
Có 2 trường hợp xảy ra:
- Nếu : Cần biến xâu thành xâu . Để biến đổi tối ưu, cần biến đổi xâu thành xâu sau ít phép biến đổi nhất, giữ nguyên kí tự . Số phép biến đổi cần thiết là .
- Nếu : Để biến đổi thành , ta có thể dùng một trong các cách sau:
- Xoá kí tự : Sau khi xóa, cần biến thành . Số phép biến đổi ít nhất là . Do đó số phép biến đổi phải dùng là .
- Thay thế bởi : Sau đó, cần biến thành . Số phép biến đổi ít nhất là .
- Chèn vào sau : Sau đó, cần biến đổi thành . Số phép biến đổi ít nhất là .
- Các cách biến đổi khác đều phải chứa phép biến đổi hoặc . Do đó, ta có thể đảo thứ tự các phép biến đổi để đưa về lần biến đổi đầu tiên là hoặc .
Tổng kết lại, ta có công thức QHĐ sau:
- , với mọi .
- , với mọi .
- nếu .
- nếu .
Bài này ta có thể tiết kiệm biến hơn bằng cách dùng 2 mảng 1 chiều tính lẫn nhau và một mảng đánh dấu 2 chiều để truy vết.
¶ 1.3. Code tham khảo
Cần lưu ý thứ tự tính. Để tính cần biết và . Hơn nữa, và có thể tính trực tiếp nên ta có thể tính theo trình tự sau:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int m, n;
string a, b;
vector<vector<int>> L;
int main()
{
cin >> a >> b;
m = a.length();
n = b.length();
L.resize(m + 1);
for (auto& i : L)
i.resize(n + 1);
/* Vì a và b bắt đầu từ chỉ số 1 nên
* chèn thêm 1 kí tự vào đầu 2 xâu */
a = "_" + a;
b = "_" + b;
for (int i = 0; i <= m; i++)
L[i][0] = i;
for (int j = 0; j <= n; j++)
L[0][j] = j;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
{
if (a[i] == b[j])
L[i][j] = L[i - 1][j - 1];
else
L[i][j] = 1 + min(L[i - 1][j - 1],
min(L[i - 1][j], L[i][j - 1]));
}
cout << L[m][n];
}
¶ 1.4. Một số bài toán khác
¶ 1.4.1. Xâu con chung dài nhất
Link nộp bài: VNOJ-LCS
Cho xâu A và B. Tìm xâu con chung dài nhất của và .
Xâu là xâu con của xâu khi và chỉ khi có thể thu được bằng cách xóa một số kí tự của (có thể tất cả hoặc không kí tự nào).
Điều kiện: .
Input: xâu và .
Output: Độ dài xâu con chung dài nhất.
Lời giải:
Gọi là độ dài xâu con chung dài nhất của xâu gồm kí tự phần đầu của () và xâu gồm kí tự phần đầu của ().
- Nếu thì ta chỉ cần chọn xâu con dài nhất của và , do đó độ dài xâu con dài nhất của và là .
- Nếu thì xâu con chung dài nhất sẽ là xâu con của và hoặc và .
Từ đó có công thức quy hoạch động như sau:
- nếu
- nếu .
Cài đặt:
Lưu ý do và có thể lớn đến nên mảng phải là mảng động (ví dụ std::vector trong c++).
Nếu đề bài yêu cầu phải in ra xâu con dài nhất thì phải thực hiện truy vết. Dưới đây là một cách cài đặt tham khảo:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// Struct dùng để truy vết
struct Trace
{
// Vị trí của kí tự trước đó trong A và B
int i;
int j;
// Kí tự cần thêm vào xâu kết quả
// (có thể là kí tự NULL)
char c;
Trace(int ii = 0, int jj = 0, char cc = '\0')
: i(ii), j(jj), c(cc)
{ };
};
int m, n;
string a, b;
vector<vector<int>> L;
vector<vector<Trace>> Tr;
int main()
{
cin >> a >> b;
m = a.length();
n = b.length();
L.resize(m + 1);
Tr.resize(m + 1);
for (auto& i : L)
i.resize(n + 1);
for (auto& i : Tr)
i.resize(n + 1);
// Vì a và b bắt đầu từ chỉ số 1 nên
// chèn thêm 1 kí tự vào đầu 2 xâu
a = "_" + a;
b = "_" + b;
for (int i = 0; i <= m; i++)
L[i][0] = 0;
for (int j = 0; j <= n; j++)
L[0][j] = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
{
if (a[i] == b[j])
{
L[i][j] = L[i - 1][j - 1] + 1;
Tr[i][j] = Trace(i - 1, j - 1, a[i]);
}
else if (L[i - 1][j] > L[i][j - 1])
{
L[i][j] = L[i - 1][j];
Tr[i][j] = Trace(i - 1, j);
}
else
{
L[i][j] = L[i][j - 1];
Tr[i][j] = Trace(i, j - 1);
}
}
// Truy vết xâu con chung dài nhất từ Tr[m][n]
Trace t = Tr[m][n];
string ans = "";
while (true)
{
if (t.c != '\0')
ans = t.c + ans;
if (t.i == 0 && t.j == 0)
break;
else
t = Tr[t.i][t.j];
}
cout << ans;
}
Như vậy độ phức tạp bộ nhớ của bài toán là , độ phức tạp thời gian là .
Có một phương pháp cài đặt tốt hơn, chỉ với độ phức tạp bộ nhớ dựa trên nhận xét ở ví dụ đầu:
Để tính , ta chỉ cần 3 ô , và .
Tức là để tính hàng thì chỉ cần hàng và . Do đó ta chỉ cần 2 mảng 1 chiều để lưu hàng vừa tính và hàng đang tính . Cách cài đặt mới như sau:
vector<int> P(n + 1), L(n + 1);
for (int i = 1; i <= m; i++)
{
L[0] = 0;
for (int j = 1; j <= n; j++)
if (a[i] == b[j])
L[j] = P[j - 1] + 1;
else
L[j] = max(L[j - 1], P[j]);
P = L;
}
¶ 1.4.2. Bắc cầu
Hai nước Alpha và Beta nằm ở hai bên bờ sông Omega, Alpha nằm ở bờ bắc và có thành phố được đánh số từ đến , Beta nằm ở bờ nam và có thành phố được đánh số từ đến (theo vị trí từ tây sang đông).
Mỗi thành phố của nước này thường có quan hệ kết nghĩa với một số thành phố của nước kia. Để tăng cường tình hữu nghị, hai nước muốn xây các cây cầu bắc qua sông, mỗi cây cầu sẽ là nhịp cầu nối 2 thành phố kết nghĩa. Với yêu cầu là các cây cầu không được cắt nhau và mỗi thành phố chỉ là đầu cầu cho nhiều nhất là một cây cầu, hãy đếm số cây cầu nhiều nhất có thể xây dựng.
Điều kiện: .
Lời giải:
Bài toán có thể được phát biểu lại như sau: Cho đồ thị hai phía . Các đỉnh của là . Tương tự, các đỉnh của là . Cần tìm lớn nhất để có hai dãy đỉnh và sao cho: với mọi .
Ý tưởng tương tự như các bài trên, ta xét mảng là số lượng cầu nhiều nhất có thể bắc từ các thành phố đến .
Khi đó công thức QHĐ sẽ là:
- nếu và là hai thành phố kết nghĩa
- nếu và không là hai thành phố kết nghĩa
Nhận xét: Không mất tổng quát, giả sử thứ tự xây các cây cầu là tăng dần theo mút ở thành phố . Khi đó, nếu ta đã chọn xây cầu giữa hai thành phố và thì cây cầu tiếp theo, giả sử là cây cầu nối và sẽ phải thỏa mãn . Do đó, bài toán có thể giải như bài toán tìm xâu con dài nhất, với và được xem là "bằng nhau" khi và chỉ khi chúng là hai thành phố kết nghĩa.
¶ 1.4.3. Palindrome (IOI 2000)
Link nộp bài: SPOJ - IOIPALIN
Cho một xâu . Ở mỗi bước, bạn An có thể chèn kí tự tùy ý vào bất kì vị trí nào trong xâu . Hãy tính số bước ít nhất cần thực hiện để biến thành xâu đối xứng.
Xâu được gọi là xâu đối xứng nếu , với mọi .
Điều kiện: .
Lời giải:
Cách 1:
Công thức QHĐ của bài này như sau:
Gọi là số kí tự ít nhất cần thêm vào xâu con của để xâu đó trở thành đối xứng. Nhận xét đầu tiên là xâu thu được sau khi thêm một số kí tự vào phải có kí tự đầu tiên và cuối cùng là hoặc .
- Nếu thì xâu đối xứng thu được từ cũng có kí tự đầu tiên là và kí tự cuối cùng là . Do đó, chỉ cần tìm số kí tự ít nhất để thêm vào để tạo thành xâu đối xứng.
- Nếu thì trước tiên ta cần thêm kí tự vào đầu hoặc vào cuối xâu . Do đó, chỉ cần tìm số kí tự ít nhất cần thêm vào để hoặc trở thành xâu đối xứng.
Tóm lại, công thức QHĐ là:
- nếu
- nếu và
- nếu và
Đáp số của bài toán sẽ là với là số kí tự của .
Cài đặt: Ta có thể cài đặt trực tiếp thuật toán trên mà không cần quan tâm đến thứ tự tính như sau:
#include <iostream>
#include <string>
using namespace std;
const int N = 5010;
int n, d[N][N];
string s;
int calc(int i, int j)
{
// Nếu L[i, j] chưa được tính thì lưu giá trị vào d[i][j]
if (d[i][j] == -1)
{
if (i >= j)
d[i][j] = 0;
else
{
if (s[i] == s[j])
d[i][j] = calc(i + 1, j - 1);
else
d[i][j] = 1 + min(calc(i, j - 1), calc(i + 1, j));
}
}
return d[i][j];
}
int main()
{
cin >> s;
n = s.length();
s = "_" + s;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
d[i][j] = -1;
cout << calc(1, n) << '\n';
}
Nhận xét: Đây là phương pháp đệ quy có nhớ (memoization). Độ phức tạp bộ nhớ của thuật toán là . Có một phương pháp cài đặt tiết kiệm hơn như sau:
Để ý để tính được mảng thì ta chỉ cần mảng . Do đó ta sẽ dùng hai mảng một chiều và để lưu giá trị mảng đã tính và cần tính. Ở mỗi vòng lặp ta có . Đáp án bài toán là .
Cách 2:
Từ ý tưởng của bài xâu con chung dài nhất, ta có thuật toán sau:
- Gọi là xâu đảo của và là xâu con chung dài nhất của và . Khi đó các kí tự của không thuộc cũng là các kí tự cần thêm vào để trở thành đối xứng. Đáp số của bài toán sẽ là , với là độ dài của .
Ví dụ: , xâu đảo của là . Xâu con chung dài nhất của và là . Như vậy cần thêm kí tự vào để trở thành xâu đối xứng. Ví dụ, ta có thể thêm kí tự e và c vào và thu được xâu .
¶ 2. Xếp vali không giới hạn (Unbounded Knapsack)
¶ 2.1. Mô hình
Có đồ vật, vật thứ có trọng lượng và giá trị . Hãy chọn ra một số các đồ vật để xếp vào vali có trọng lượng tối đa sao cho tổng giá trị của vali là lớn nhất (Chú ý mỗi vật có thể chọn nhiều lần).
Điều kiện: .
Chú ý: Bài toán này khác với bài toán Xếp Vali ở phần trước ở chỗ mỗi vật không phải là duy nhất và có thể được chọn vào vali nhiều lần.
¶ 2.2. Lời giải
Trạng thái của bài toán phụ thuộc vào hai yếu tố: số vật đang được chọn và tổng khối lượng của chúng. Ta có thể gọi là giá trị lớn nhất có thể có khi ta chọn các vật từ đến sao cho khối lượng của chúng không vượt quá . Khi đó, đáp số bài toán sẽ là .
Ta đi tìm công thức truy hồi của :
- nếu
- nếu
Trong đó, là giá trị có được nếu không được đưa vật vào balô, là giá trị có được nếu được phép đưa vật vào balô.
¶ 2.3. Code tham khảo
Tương tự như các ví dụ trước, ta có thể dùng mảng hai chiều để lưu kết quả bài toán. Khi tính, ta có thể tính theo từng hàng hoặc đệ quy có nhớ. Cả hai cách đểu có độ phức tạp thời gian và bộ nhớ .
Để giảm độ phức tạp bộ nhớ xuống , ở mỗi bước ta chỉ cần lưu kết quả của hai hàng vừa tính ( và ). Ta có thể cài đặt như sau:
#include <iostream>
#include <vector>
using namespace std;
long long n, w;
vector<long long> a, b, L, P;
int main()
{
cin >> n >> w;
a.resize(n + 1);
b.resize(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i] >> b[i];
P = L = vector<long long>(w + 1);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= w; j++)
{
if (a[i] > j)
L[j] = P[j];
else
L[j] = max(P[j], L[j - a[i]] + b[i]);
}
P = L;
}
cout << L[w];
}
Lưu ý rằng đoạn chương trình trên mới chỉ cài đặt y nguyên công thức QHĐ chứ chưa tối ưu. Ví dụ với các , ta gán nhưng sau đó lại gán . Bạn đọc có thể rút gọn đoạn code lại để chương trình tối ưu hơn.
¶ 2.4. Một số bài toán khác
¶ 2.4.1. Đổi tiền
Ở đất nước Omega người ta chỉ tiêu tiền xu. Có loại tiền xu, loại thứ có mệnh giá là đồng. Một người khách du lịch đến Omega du lịch với số tiền đồng. Ông ta muốn đổi số tiền đó ra tiền xu Omega để tiện tiêu dùng. Ông ta cũng muốn số đồng tiền sau khi đổi là ít nhất (cho túi tiền đỡ nặng khi đi đây đi đó). Bạn hãy giúp ông ta tìm cách đổi tiền.
Điều kiện: .
Input: Hai số và .
Output: Nếu không thể đổi được, in ra . Ngược lại, in ra hai dòng:
- Dòng đầu tiên in ra số đồng tiền ít nhất có thể.
- Dòng thứ hai in ra số, số thứ là số đồng xu của mệnh giá thứ .
Lời giải:
Nếu xem "khối lượng" là mệnh giá và "giá trị" bằng , bài toán này sẽ được phát biểu lại thành: xếp các vật có tổng khối lượng đúng bằng vào vali sao cho tổng giá trị của chúng là nhỏ nhất. Lưu ý trong mô hình bài toán gốc thì tổng giá trị phải là lớn nhất, và tổng khối lượng có thể bé hơn .
Ta xây dựng mảng là số đồng xu (giá trị) nhỏ nhất có thể khi đổi đồng (khối lượng) ra tiền xu bằng loại tiền . Công thức truy hồi của mảng như sau:
- nếu
- nếu
Kết quả của bài toán là hoặc nếu . Để truy vết các đồng tiền được đổi, ta có thể dùng mảng là chỉ số của đồng tiền được thêm vào khi tính .
Cài đặt:
#include <iostream>
#include <vector>
using namespace std;
// Struct để truy vết
struct Trace
{
int coin; // Chỉ số đồng tiền được thêm vào
int i; // i và j dùng để truy vết trong bảng QHĐ
int j;
Trace(int c = 0, int row = 0, int col = 0)
: coin(c), i(row), j(col) {};
};
const int N = 1e6 + 10;
int n, m, A[N];
vector<int> L, P;
vector<vector<Trace>> d;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> A[i];
// Quy ước inf = -1
P = vector<int>(m + 1, -1);
L.resize(m + 1);
d = vector<vector<Trace>>(n + 1, vector<Trace>(m + 1));
// Bước QHĐ
for (int i = 1; i <= n; i++)
{
L[0] = 0;
for (int j = 1; j <= m; j++)
if (A[i] > j)
{
L[j] = P[j];
d[i][j] = Trace(0, i - 1, j);
}
else
{
// L[j] = min(P[j], L[j - A[i]]);
// Nếu P[j] và L[j - A[i]] khác inf
if (P[j] != -1 && L[j - A[i]] != -1)
{
if (P[j] < L[j - A[i]] + 1)
{
L[j] = P[j];
d[i][j] = Trace(0, i - 1, j);
}
else
{
L[j] = L[j - A[i]] + 1;
d[i][j] = Trace(i, i, j - A[i]);
}
}
// Chỉ L[j - A[i]] là inf
else if (P[j] != -1)
{
L[j] = P[j];
d[i][j] = Trace(0, i - 1, j);
}
// Chỉ P[j] là inf
else if (L[j - A[i]] != -1)
{
L[j] = L[j - A[i]] + 1;
d[i][j] = Trace(i, i, j - A[i]);
}
// Cả hai số là inf
else
L[j] = -1;
}
P = L;
}
cout << L[m] << '\n';
// Truy vết
if (L[m] != -1)
{
vector<int> cnt(n + 1);
Trace t = d[n][m];
while (t.coin != 0 && t.j != 0)
{
cnt[t.coin]++;
t = d[t.i][t.j];
}
for (int i = 1; i <= n; i++)
cout << cnt[i] << ' ';
}
}
¶ 3. Nhân ma trận
¶ 3.1. Mô hình
Khi nhân một ma trận kích thước với một ma trận , số phép nhân phải thực hiện là . Mặt khác phép nhân các ma trận có tính kết hợp, tức là:
Do đó khi tính tích nhiều ma trận, ta có thể thực hiện theo các trình tự khác nhau, mỗi trình tự tính sẽ quyết định số phép nhân cần thực hiện.
Cho số và ma trận , ma trận thứ có kích thước là . Hãy xác định trình tự nhân ma trận sao cho số phép nhân cần thực hiện là ít nhất.
Điều kiện: .
Input: Số và số .
Output: Số nguyên duy nhất là số phép nhân ít nhất.
¶ 3.2. Lời giải
Gọi là số phép nhân nhỏ nhất cần dùng để tính tích các ma trận từ đến .
Xét tích với Khi tính tích trên, phép nhân ma trận cuối cùng sẽ có dạng , sao cho tồn tại một số nguyên thỏa mãn:
Nói cách khác, tích được tính theo trình tự sau: .
Để số phép nhân là nhỏ nhất thì số phép nhân cần dùng khi tính và cũng là nhỏ nhất. Giá trị của sẽ là kết quả nhỏ nhất nếu chạy từ đến . Từ đó, ta có công thức truy hồi như sau:
- , trong đó nếu
¶ 3.3. Code tham khảo
Để tính các giá trị , ta có thể dùng hai cách: đệ quy có nhớ và tính theo thứ tự.
Nếu tính theo thứ tự, để tính được ta cần các giá trị và sao cho . Do đó, không thể tính theo thứ tự tăng dần của hoặc . Thay vào đó, ta sẽ tính theo thứ tự tăng dần của như sau: đầu tiên tính các số thỏa mãn , sau đó tính giá trị các số tiếp theo với . Như vậy, khi tính thì các giá trị đã được tính, với .
Đệ quy có nhớ:
#include <iostream>
using namespace std;
const int N = 310;
int d[N], L[N][N], n;
int calc(int i, int j)
{
if (L[i][j] == -1)
{
if (i == j)
L[i][j] = 0;
else
{
L[i][j] = calc(i + 1, j) + d[i - 1] * d[i] * d[j];
for (int k = i; k < j; k++)
L[i][j] = min(L[i][j], calc(i, k) + calc(k + 1, j) + d[i - 1] * d[k] * d[j]);
}
}
return L[i][j];
}
int main()
{
cin >> n;
for (int i = 0; i <= n; i++)
cin >> d[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
L[i][j] = -1;
cout << calc(1, n);
}
Tính theo thứ tự:
#include <iostream>
using namespace std;
const int N = 310;
int d[N], L[N][N], n;
int main()
{
cin >> n;
for (int i = 0; i <= n; i++)
cin >> d[i];
for (int dis = 1; dis < n; dis++)
for (int i = 1; i + dis <= n; i++)
{
int j = i + dis;
L[i][j] = L[i + 1][j] + d[i - 1] * d[i] * d[j];
for (int k = i; k < j; k++)
L[i][j] = min(L[i][j], L[i][k] + L[k + 1][j] + d[i - 1] * d[k] * d[j]);
}
cout << L[1][n];
}
Với hai cách cài đặt trên, độ phức tạp bộ nhớ là , độ phức tạp thời gian là .
¶ 3.4. Một số bài toán khác
¶ 3.4.1. Chia đa giác
Cho một đa giác lồi đỉnh được đánh số từ đến theo chiều kim đồng hồ. Bằng các đường chéo không cắt nhau, ta có thể chia đa giác thành tam giác. Hãy xác định cách chia có tổng các đường chéo ngắn nhất.
Điều kiện: (với là tọa độ của đỉnh thứ ).
Input: Một số tự nhiên và bộ .
Output: In ra tổng các đường chéo của cách chia ngắn nhất.
Lời giải:
Để đơn giản ta coi mọi đoạn thẳng nối hai đỉnh bất kì đều là “đường chéo” (nếu nối hai đỉnh trùng nhau hoặc hai đỉnh liên tiếp thì có độ dài bằng ).
Gọi là tổng độ dài bé nhất có thể của các đường chéo dùng để chia đa giác gồm các đỉnh từ đến thành các tam giác.
- Nếu thì đa giác đó có ít hơn 4 đỉnh, không cần phải chia nên .
- Ngược lại ta xét cách chia đa giác đó bằng cách chọn một đỉnh nằm giữa , và nối , với . Khi đó