හැකි ත්රිකෝණ ගණන් කරන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් LinkedIn විෙප්රෝ
අරා ගණිතය

ගැටළු ප්රකාශය

හැකි ත්‍රිකෝණ ගැටලුවක් ලෙස අපි ලබා දී ඇත අරාව ධනාත්මක පූර්ණ සංඛ්‍යා. ත්රිකෝණයක පැති ලෙස අරාවෙහි විවිධ මූලද්රව්ය තුනක් භාවිතා කරමින් සෑදිය හැකි ත්රිකෝණ ගණන සොයා ගන්න.

සටහන: ත්රිකෝණයේ තත්වය ත්රිකෝණයක පැති දෙකක එකතුව තුන්වන පැත්තට වඩා වැඩිය.

උදාහරණයක්

ආදාන

arr [] = {2, 3, 4, 5, 6, 7}

ප්රතිදාන

13

පැහැදිලි කිරීම

හැකි සෑම ත්‍රිත්වයක්ම-

{2, 3, 4}, {2, 4, 5}, {2, 5, 6}, {2, 6, 7}, {3, 4, 5}, {3, 4, 6}, {3 , 5, 6}, {3, 5, 7}, {3, 6, 7}, {4, 5, 6}, {4, 5, 7}, {4, 6, 7}, {5, 6 , 7}

හැකි ත්රිකෝණ ගණනය කිරීම සඳහා ඇල්ගොරිතම

දැන් අපට ගැටළු ප්‍රකාශය පැහැදිලිව වැටහෙයි. එබැවින්, න්‍යායට වැඩි කාලයක් නාස්ති නොකර අපි අරාවෙහි ත්‍රිකෝණ ගණන සොයා ගැනීම සඳහා භාවිතා කරන ඇල්ගොරිතම වෙත කෙලින්ම ගමන් කරමු.

a. දී ඇති අරාව වැඩි වන අනුපිළිවෙලට වර්ග කරන්න.

b. I, j, සහ k යන ස්ථාන තුනක් ගන්න

  • i පළමු අංගය සඳහා. i 0 සිට n - 3 දක්වා වේ.
  • j දෙවන මූලද්‍රව්‍යය සඳහා. i i + 1 සිට n - 2 දක්වා වේ.
  • k තෙවන මූලද්‍රව්‍යය සඳහා. k යනු i + 2 සිට n -1 දක්වා වේ.

c. K චලනය කිරීමෙන් වත්මන් i සහ j හි එකතුවට වඩා කුඩා වන දකුණු කෙළවරේ මූලද්‍රව්‍යය සොයා ගන්න.
d. K - j - 1 යනු ත්‍රිකෝණ ගණනකි, වත්මන් i සහ j සඳහා.
e. එය ගණන් කිරීමට එකතු කර i, j වැඩි කරන්න.

ක්රියාත්මක කිරීම

ගණනය කළ හැකි ත්‍රිකෝණ සඳහා C ++ වැඩසටහන

#include <bits/stdc++.h>
using namespace std;
 
int compare(const void* a, const void* b)
{  
    return *(int*)a > *(int*)b; 
}
int TrianglesCount(int array[], int n)
{
    qsort(array,n,sizeof(array[0]),compare);
    int count = 0;
    for(int i = 0; i < n-2; ++i)
    {
        for (int j = i+1; j < n; ++j)
        {
            int k = j+1;
            while (k < n && array[i] + array[j] > array[k])
            {
               k = k + 1;
            }
            count=count+k-j-1;
        }
    }
    return count;
}
//Main function
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<"Total number of Triangles can be formed is = "<<TrianglesCount(input_array,n);
    return 0;
}

හැකි ත්රිකෝණ ගණනය කිරීම සඳහා ජාවා වැඩසටහන

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int TrianglesCount(int arr[], int n) 
    { 
        Arrays.sort(arr);
        int count = 0; 
        for (int i = 0; i < n - 2; ++i) { 
            int k = i + 2; 
            for (int j = i + 1; j < n; ++j) { 
                while (k < n && arr[i] + arr[j] > arr[k]) 
                    ++k; 
                if (k > j) 
                    count += k - j - 1; 
            } 
        } 
        return count; 
    } 
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int ans = TrianglesCount(arr,n);
        System.out.println("Total number of Triangles can be formed is = " + ans);
    } 
}
5
2 3 4 5 6
Total number of Triangles can be formed is = 7

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (n ^ 2) මෙහි n යනු දී ඇති අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. කැදැලි ලූප 3 ක් නිසා කාල සංකීර්ණතාව වැඩියෙන් පෙනේ. K ආරම්භ කරනු ලබන්නේ පිටත කෙළවරේ එක් වරක් පමණක් බව නිරීක්ෂණය කළ හැකිය. අභ්‍යන්තර ලූපය පිටත O ලූපයේ සෑම පුනරාවර්තනයක් සඳහාම බොහෝ විට O (n) ක් ක්‍රියාත්මක වේ, මන්ද k i i + 2 සිට ආරම්භ වන අතර j හි සියලු අගයන් සඳහා n දක්වා ඉහළ යයි. එබැවින් කාල සංකීර්ණතාව O (n ^ 2) වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1) මක්නිසාද යත් අප නිරන්තර අවකාශ සංකීර්ණතාවයට මඟ පෙන්වන විචල්‍යයන් කිහිපයක් නිර්මාණය කරන බැවිනි.

ආශ්රිත