Kiểm tra có thể tạo tam giác từ giá trị mảng trong C++

Trong bài toán này, cho mảng số nguyên. Nhiệm vụ kiểm tra xem có thể tạo tam giác không suy biến (non-degenerate) lấy các phần tử mảng làm cạnh.

Tam giác không suy biến - Tam giác có diện tích dương. Điều kiện với ba cạnh a, b, c:

a + b > c 
a + c > b 
b + c > a

Ví dụ minh họa:

Đầu vào - arr[2, 5, 9, 4, 3]

Kết quả - Yes

Giải thích - Tam giác tạo được: 2, 3, 4.

Để giải bài toán, kiểm tra điều kiện trên với các giá trị mảng.

Cách đơn giản: kiểm tra mọi bộ ba của mảng.

Cách hiệu quả hơn: sắp xếp mảng, kiểm tra ba phần tử liên tiếp. Với mảng đã sắp xếp, nếu tổng hai số không lớn hơn số tiếp theo thì các số sau cũng không cần kiểm tra (vì đã lớn hơn).

Chương trình minh họa

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

bool isTrianglePossible(int arr[], int N) { 
    if (N < 3) 
        return false; 
    sort(arr, arr + N); 
    for (int i = 0; i < N - 2; i++) 
        if (arr[i] + arr[i + 1] > arr[i + 2]) 
            return true; 
    return false; 
} 

int main() { 
    int arr[] = {5, 12, 13, 65, 6, 1}; 
    int N = sizeof(arr) / sizeof(int); 
    cout << "Tạo tam giác từ phần tử mảng "; 
    isTrianglePossible(arr, N) ? cout << "có thể" : cout << "không thể"; 
    return 0; 
}

Kết quả

Tạo tam giác từ phần tử mảng có thể