สามารถสร้างสามเหลี่ยมจากค่าอาร์เรย์ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็ม งานของเราคือตรวจสอบว่าการสร้างสามเหลี่ยมที่ไม่เสื่อมโดยเอาองค์ประกอบของอาร์เรย์เป็นด้านของสามเหลี่ยมหรือไม่

สามเหลี่ยมไม่เสื่อม − เป็นรูปสามเหลี่ยมที่มีพื้นที่บวก เงื่อนไขสำหรับรูปสามเหลี่ยมไม่เสื่อมที่มีด้าน a, b, c คือ −

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

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากันดีกว่า −

ป้อนข้อมูล − arr[2, 5 ,9, 4, 3]

ผลผลิต - ใช่

คำอธิบาย − สามเหลี่ยมที่เกิดขึ้นคือ 2 3 4

ในการแก้ปัญหานี้ เราจะตรวจสอบว่าค่าของอาร์เรย์เป็นไปตามเงื่อนไขข้างต้นหรือไม่

วิธีแก้ปัญหาแบบกองทัพเรือจะเกี่ยวข้องกับการตรวจสอบ Triplet ทุกตัวในอาร์เรย์โดยตรง

โซลูชันที่มีประสิทธิภาพมากขึ้นจะเกี่ยวข้องกับการจัดเรียงองค์ประกอบอาร์เรย์และการตรวจสอบสามส่วนติดต่อกันของอาร์เรย์ สำหรับ sorted array ถ้าผลรวมของสององค์ประกอบไม่เกินค่าถัดไป ตรวจสอบค่าหลังจากนั้นไม่คุ้มค่า (พวกมันมีขนาดใหญ่อยู่แล้ว)

ตัวอย่าง

โปรแกรมแสดงการใช้งานโซลูชันของเรา

#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;
}
int main() {
   int arr[] = {5, 12, 13, 65, 6, 1};
   int N = sizeof(arr) / sizeof(int);
   cout<<"Creation of triangle from elements of array ";
   isTrianglePossible(arr, N)?cout<<"is Possible": cout<<"is not Possible";
   return 0;
}

ผลลัพธ์

Creation of triangle from elements of array is Possible