นับจำนวนสามเหลี่ยมที่เป็นไปได้ใน C++

เราได้อาร์เรย์ที่มีด้านยาวของสามเหลี่ยม เป้าหมายคือการหาจำนวนสามเหลี่ยมที่เป็นไปได้ซึ่งสามารถทำได้โดยนำสามด้านใดๆ จากอาร์เรย์นั้นมา

เราจะทำสิ่งนี้โดยตรวจสอบว่าผลรวมของสองอันใดเป็น> ด้านที่สามเสมอ ถ้าใช่ ด้านทั้งสามนี้สามารถสร้างสามเหลี่ยมได้ จำนวนที่เพิ่มขึ้นของสามเหลี่ยมที่เป็นไปได้ที่สามารถสร้างได้

มาทำความเข้าใจกับตัวอย่างกัน

ป้อนข้อมูล − arr[]={1,2,4,5}

ผลผลิต − จำนวนสามเหลี่ยมที่เป็นไปได้ − 1

คำอธิบาย − ด้าน (2,4,5) สามารถสร้างสามเหลี่ยมได้เพียง 2+4>5 &4+5>2 &2+5>4

ป้อนข้อมูล − arr[]={4,5,6,3,2}

ผลผลิต − จำนวนสามเหลี่ยมที่เป็นไปได้ − 7

คำอธิบาย − ด้าน (4,5,6), (4,5,2),(4,5,3),(4,3,2),(5,6,3),(5,6,2) กระป๋อง ทำสามเหลี่ยม

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• เราใช้อาร์เรย์จำนวนเต็ม arr[] ที่เริ่มต้นด้วยตัวเลขสุ่มบวก

• ฟังก์ชัน countTriangles(int arr[], int n) ใช้อาร์เรย์และความยาวและคืนค่าสามเหลี่ยมที่เป็นไปได้ที่สามารถสร้างได้

• นับสามเหลี่ยมเริ่มต้นเป็น 0

• ใช้สามห่วงสำหรับสามด้าน

• วงนอกสุด 0<=i

• สำหรับด้าน arr[i],arr[j],arr[k] ตรวจสอบว่าเป็นด้านของสามเหลี่ยมหรือไม่

• ตรวจสอบ arr[i] + arr[j]> arr[k] &&arr[i] + arr[k]> arr[j] &&arr[k] + arr[j]> arr[i] ถ้านับการเพิ่มขึ้นจริง

• ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง

#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;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

count of Triangles possible : 8