Chúng ta được cung cấp một mảng chứa độ dài các cạnh của hình tam giác. Mục đích là để tìm số lượng hình tam giác có thể được tạo ra bằng cách lấy ba cạnh bất kỳ từ mảng đó.
Chúng tôi sẽ làm điều này bằng cách kiểm tra xem tổng của hai bất kỳ luôn luôn> cạnh thứ ba. Nếu có, ba cạnh này có thể tạo thành một tam giác. Số lượng tăng dần các hình tam giác có thể được tạo ra.
Hãy cùng hiểu với các ví dụ.
Đầu vào - arr [] ={1,2,4,5}
Đầu ra - Đếm số hình tam giác có thể có - 1
Giải thích - Các cạnh (2,4,5) chỉ có thể tạo thành một tam giác là 2 + 4> 5 &4 + 5> 2 &2 + 5> 4
Đầu vào - arr [] ={4,5,6,3,2}
Đầu ra - Đếm số hình tam giác có thể có - 7
Giải thích - Mặt (4,5,6), (4,5,2), (4,5,3), (4,3,2), (5,6,3), (5,6,2) có thể tạo hình tam giác.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi lấy một mảng số nguyên arr [] được khởi tạo với các số dương ngẫu nhiên.
-
Hàm đếm Hình tam giác (int arr [], int n) nhận mảng và độ dài của nó và trả về các hình tam giác có thể tạo được.
-
Lấy số lượng tam giác ban đầu là 0.
-
Lấy ba vòng lặp cho ba cạnh.
-
Vòng ngoài cùng 0 <=i
-
Đối với các cạnh arr [i], arr [j], arr [k], hãy kiểm tra xem chúng có tạo thành các cạnh của tam giác không.
-
Kiểm tra arr [i] + arr [j]> arr [k] &&arr [i] + arr [k]> arr [j] &&arr [k] + arr [j]> arr [i] nếu số gia tăng đúng.
-
Kết quả là số lượt trả lại.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int countTriangles(int arr[], int n){
// Count of triangles
int count = 0;
for (int i = 0; i < n-2; i++){
for (int j = i + 1; j < n-1; j++){
for (int k = j + 1; k < n; k++){
//any two sides have sum > third
if ( arr[i] + arr[j] > arr[k] && arr[i] + arr[k] > arr[j] && arr[k] + arr[j] > arr[i])
{ count++; }
}
}
}
return count;
}
int main(){
int Arr[] = { 1,2,5,3,6,8,10 };
int len = sizeof(Arr) / sizeof(Arr[0]);
cout << "count of Triangles possible : "<< countTriangles(Arr, len);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
count of Triangles possible : 8