Chương trình kiểm tra mảng Bitonic trong C++

Cho mảng arr[N] gồm N số nguyên, nhiệm vụ là kiểm tra xem mảng có phải là bitonic hay không. In "Là mảng bitonic" nếu đúng, ngược lại in "Không phải mảng bitonic".

Mảng bitonic là mảng tăng chặt trước rồi giảm chặt sau.

Ví dụ: arr[] = {1, 2, 3, 4, 2, -1, -5} là mảng bitonic vì tăng đến 4 rồi giảm.

Đầu vào 1

arr[] = {1, 3, 5, 4, 2, 0}

Đầu ra 1

Là mảng bitonic

Giải thích − 1 < 3 < 5 > 4 > 2 > 0

Đầu vào 2

arr[] = {1, 2, 3, 4, 5, 0, -1, -2, 6, -4}

Đầu ra 2

Không phải mảng bitonic

Phương pháp tiếp cận

• Duyệt mảng, kiểm tra phần tử trước nhỏ hơn phần tử hiện tại (giai đoạn tăng)
• Khi không còn tăng nữa thì dừng
• Kiểm tra giai đoạn giảm: phần tử trước lớn hơn phần tử hiện tại
• Nếu duyệt hết mảng và thỏa mãn → mảng bitonic

Thuật toán

int kiemTraBitonic(int arr[], int size) {
    int i, j;
    // Giai đoạn tăng
    for (i = 1; i < size; i++) {
        if (arr[i] > arr[i-1]) continue;
        if (arr[i] <= arr[i-1]) break;
    }
    if (i == size - 1) return 1; // Chỉ tăng không giảm
    
    // Giai đoạn giảm
    for (j = i + 1; j < size; j++) {
        if (arr[j] < arr[j-1]) continue;
        if (arr[j] >= arr[j-1]) break;
    }
    i = j;
    if (i != size) return 0;
    return 1;
}

Ví dụ mã nguồn

#include <bits/stdc++.h>
using namespace std;

int kiemTraBitonic(int arr[], int size) {
    int i, j;
    for (i = 1; i < size; i++) {
        if (arr[i] > arr[i-1]) continue;
        if (arr[i] <= arr[i-1]) break;
    }
    if (i == size - 1) return 1;
    for (j = i + 1; j < size; j++) {
        if (arr[j] < arr[j-1]) continue;
        if (arr[j] >= arr[j-1]) break;
    }
    i = j;
    if (i != size) return 0;
    return 1;
}

int main() {
    int arr[] = {-3, 9, 11, 20, 17, 5, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    (kiemTraBitonic(arr, size) == 1) ? cout << "Là mảng bitonic" : cout << "Không phải mảng bitonic";
    return 0;
}

Kết quả chạy chương trình

Là mảng bitonic