NỘI DUNG
BÀI TOÁN
Một dãy số có độ dài (số phần tử) là m được gọi là dãy hình nón nếu nó là một dãy gồm các số nguyên và cáo các đặc điểm sau:
- Số lượng phần tử của dãy là một số lẻ (hay m = 2*x +1)
- Không có hai số nào đứng cạnh nhau trong dãy có giá trị bằng nhau.
- x + 1 là số đầu tiên của một dãy tăng
- x + 1 số cuối cùng của dãy là một dãy giảm
Ví dụ: Dãy 3 6 9 5 2 là một dãy hình nón có độ dài bằng 5; dãy 1 8 3 6 9 không phải là dãy hình nón.
Cho dãy A gồm n số nguyên dương a1, a2, … an. Một dãy con của A là một dãy được tạo ra bằng cách lấy ra một số phần tử A nhưng giữ nguyên thứ tự (các phần tử có thể không liên tiếp nhau). Yêu cầu: Trong các dãy con của A hãy tìm độ dài của dãy con hình nón dài nhất?
LỜI GIẢI
Với bài toán trên, chúng ta có rất nhiều cách giải khác nhau. Cụ thể là có thể sử dụng thuật toán tìm kiếm nhị phân, thuật toán quy hoạch động, thuật toán tham lam, thuật toán tìm kiếm đầy đủ,… Dưới đây chúng ta cùng nhau nghiên cứu và code cho bài toán trên với các thuật toán đã nêu.
Thuật toán quy hoạch động
Để giải bài toán trên bằng thuật toán quy hoạch động, ta có thể sử dụng một mảng dp lưu lại độ dài của dãy hình nón dài nhất kết thúc tại mỗi phần tử trong dãy A.
Cụ thể, giả sử dp[i] là độ dài của dãy hình nón dài nhất kết thúc tại phần tử a[i]. Ta có thể tính dp[i] dựa trên các giá trị dp[j] với j < i và a[j] < a[i]. Điều kiện a[j] < a[i] đảm bảo rằng dãy hình nón kết thúc tại phần tử a[i] sẽ bắt đầu từ một phần tử a[j]. Điều kiện không có hai phần tử nào đứng cạnh nhau trong dãy hình nón có giá trị bằng nhau đảm bảo rằng các phần tử được chọn vào dãy hình nón sẽ không trùng nhau.
Sau khi tính được tất cả các giá trị dp[i], độ dài của dãy con hình nón dài nhất sẽ là giá trị lớn nhất trong mảng dp.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> dp(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
int res = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0 && dp[i] > res && dp[i] == 2 * (i / 2) + 1) {
bool is_valid = true;
for (int j = i - dp[i] + 2; j <= i; j++) {
if (a[j] == a[j - 1]) {
is_valid = false;
break;
}
}
if (is_valid) {
res = dp[i];
}
}
}
cout << res << endl;
return 0;
}
Thuật toán tìm kiếm nhị phân
Để giải bài toán trên bằng thuật toán tìm kiếm nhị phân, ta cần sắp xếp lại dãy A và thực hiện tìm kiếm nhị phân trên dãy đã sắp xếp để tìm các dãy con hình nón.
Cụ thể, ta sắp xếp dãy A theo thứ tự tăng dần. Sau đó, với mỗi phần tử trong dãy A, ta tìm kiếm các phần tử có giá trị lớn hơn nó trong dãy A bằng cách sử dụng thuật toán tìm kiếm nhị phân. Với mỗi phần tử lớn hơn, ta xác định độ dài của dãy con hình nón bắt đầu từ phần tử hiện tại đến phần tử lớn hơn đó. Nếu độ dài của dãy con này lớn hơn độ dài của dãy con hình nón dài nhất đã tìm thấy, ta cập nhật lại độ dài của dãy con hình nón dài nhất.
#include <iostream>
#include <algorithm>
using namespace std;
bool is_valid(int x, int y, int z) {
return y > x && y > z;
}
int find_cone_sequence_length(int A[], int n) {
int max_length = 0;
for (int i = 0; i < n; i++) {
int left = i-1, right = i+1, count = 1;
while (left >= 0 && right < n && is_valid(A[left], A[i], A[right])) {
left--;
right++;
count += 2;
}
max_length = max(max_length, count);
}
return max_length;
}
int main() {
int A[] = {3, 6, 9, 5, 2};
int n = sizeof(A) / sizeof(A[0]);
sort(A, A+n);
int result = find_cone_sequence_length(A, n);
cout << "Day con hinh non dai nhat co do dai la: " << result << endl;
return 0;
}
Trong đó, hàm is_valid kiểm tra xem ba số x, y, z có thỏa mãn điều kiện của dãy hình nón không. Hàm find_cone_sequence_length tìm độ dài của dãy hình nón dài nhất trong dãy đã sắp xếp. Cuối cùng, ta sử dụng hàm sort để sắp xếp lại dãy A theo thứ tự tăng dần và in kết quả tìm được ra màn hình.
Thuật toán tham lam
Để giải bài toán trên bằng thuật toán tham lam, ta có thể thực hiện các bước sau:
- Với mỗi phần tử trong mảng A, ta xét xem nó có thể là số đầu tiên của dãy hình nón hay không.
- Nếu có thể, ta xác định được độ dài của dãy hình nón bắt đầu từ phần tử đó và lưu lại giá trị đó.
- Tìm độ dài lớn nhất trong các giá trị đã lưu lại.
Dưới đây là code minh họa cho thuật toán tham lam:
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int max_len = 0;
for (int i = 0; i < n; i++) {
// Xét từng phần tử trong mảng làm số đầu tiên của dãy hình nón
int x = a[i];
int len = 1;
bool increasing = true;
bool decreasing = false;
for (int j = i + 1; j < n; j++) {
if (a[j] == x) { // Nếu có 2 phần tử giống nhau liên tiếp thì không phải là dãy hình nón
break;
} else if (a[j] > x && increasing) { // Nếu phần tử tiếp theo lớn hơn phần tử trước đó và dãy đang tăng
x = a[j];
len++;
} else if (a[j] < x && increasing) { // Nếu phần tử tiếp theo nhỏ hơn phần tử trước đó và dãy đang tăng
x = a[j];
increasing = false;
decreasing = true;
len++;
} else if (a[j] < x && decreasing) { // Nếu phần tử tiếp theo nhỏ hơn phần tử trước đó và dãy đang giảm
x = a[j];
len++;
} else {
break; // Nếu không thỏa mãn các điều kiện trên thì không phải là dãy hình nón
}
}
if (decreasing && len > max_len) {
max_len = len;
}
}
cout << max_len << endl;
return 0;
}
Độ phức tạp của thuật toán này là O(n^2) trong trường hợp xấu nhất, khi toàn bộ mảng A đều là dãy hình nón.
Thuật toán tìm kiếm đầy đủ
Thuật toán tìm kiếm đầy đủ (Brute Force) sẽ duyệt qua tất cả các dãy con có độ dài lẻ của dãy số A, kiểm tra xem dãy con đó có phải là dãy hình nón hay không và lấy độ dài của dãy con hình nón dài nhất.
Độ phức tạp của thuật toán này là O(n^3), vì phải duyệt qua tất cả các cặp (i, j) để lấy được các dãy con, và với mỗi dãy con cần kiểm tra xem có phải là dãy hình nón hay không.
Dưới đây là mã giả của thuật toán:
int maxOddLenConeSubseq(vector<int>& A) {
int n = A.size();
int maxLen = 0;
for (int len = 1; len <= n; len += 2) { // Duyệt qua tất cả các độ dài lẻ
for (int i = 0; i <= n - len; i++) { // Duyệt qua tất cả các dãy con có độ dài len
bool isCone = true;
int mid = i + len/2;
for (int j = i; j < mid; j++) { // Kiểm tra tính chất tăng
if (A[j] >= A[j+1]) {
isCone = false;
break;
}
}
for (int j = mid; j < i + len - 1; j++) { // Kiểm tra tính chất giảm
if (A[j] <= A[j+1]) {
isCone = false;
break;
}
}
if (isCone) {
maxLen = max(maxLen, len);
}
}
}
return maxLen;
}
Lưu ý rằng trong đoạn kiểm tra tính chất tăng và giảm của dãy hình nón, ta cần sử dụng toán tử >= và <= để đảm bảo không có hai phần tử cạnh nhau trong dãy có giá trị bằng nhau.
ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA CÁC THUẬT TOÁN
Dựa trên độ phức tạp tính toán và độ hiệu quả của thuật toán, ta có thể đánh giá các thuật toán đã thực hiện như sau:
- Thuật toán Quy hoạch động: Đây là thuật toán tối ưu nhất trong các thuật toán đã được đề cập ở trên với độ phức tạp tính toán O(n^2). Thuật toán này đảm bảo tìm được đáp án chính xác và nhanh chóng.
- Thuật toán Tìm kiếm nhị phân: Đây là thuật toán có độ phức tạp thấp nhất với O(n log n), nhưng đây chỉ là độ phức tạp trong trường hợp dãy số đã được sắp xếp. Nếu dãy số chưa được sắp xếp, độ phức tạp của thuật toán này sẽ là O(n^2). Do đó, thuật toán này không tối ưu nhất.
- Thuật toán Tham lam: Đây là thuật toán có độ phức tạp thấp với O(n), nhưng không đảm bảo tìm được đáp án chính xác. Thuật toán này chỉ đưa ra một giải pháp gần đúng nhất. Do đó, nếu độ chính xác là yếu tố quan trọng thì thuật toán này không phải là tối ưu nhất.
- Thuật toán Tìm kiếm đầy đủ: Đây là thuật toán đảm bảo tìm được đáp án chính xác, nhưng độ phức tạp của thuật toán này rất cao với O(2^n). Vì vậy, thuật toán này chỉ phù hợp với các bài toán có số lượng phần tử nhỏ.
Tóm lại, thuật toán Quy hoạch động là thuật toán tối ưu nhất để giải bài toán trên./.