சாத்தியமான முக்கோணங்களை எண்ணுங்கள்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் லின்க்டு இன் விப்ரோ
அணி கணித

சிக்கல் அறிக்கை

சாத்தியமான முக்கோண சிக்கலில் நாம் ஒரு கொடுத்திருக்கிறோம் வரிசை இன் நேர்மறை முழு எண். ஒரு முக்கோணத்தின் பக்கங்களாக வரிசையின் மூன்று வெவ்வேறு கூறுகளைப் பயன்படுத்தி உருவாக்கக்கூடிய முக்கோணங்களின் எண்ணிக்கையைக் கண்டறியவும்.

குறிப்பு: முக்கோணத்தின் நிலை என்பது ஒரு முக்கோணத்தின் இரண்டு பக்கங்களின் கூட்டுத்தொகை மூன்றாம் பக்கத்தை விட அதிகமாகும்.

உதாரணமாக

உள்ளீடு

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 ஆகிய மூன்று நிலைகளை எடுத்துக் கொள்ளுங்கள்

  • முதல் உறுப்புக்கு நான். நான் 0 முதல் n - 3 வரை.
  • இரண்டாவது உறுப்புக்கு j. நான் i + 1 முதல் n - 2 வரை.
  • மூன்றாவது உறுப்புக்கு k. k என்பது i + 2 முதல் n -1 வரை.

c. K ஐ நகர்த்துவதன் மூலம் தற்போதைய i மற்றும் j இன் தொகையை விட சிறியதாக இருக்கும் வலதுபுற உறுப்பைக் கண்டறியவும்.
d. K - j - 1 என்பது முக்கோணங்களின் எண்ணிக்கை, தற்போதைய i மற்றும் j க்கு.
e. அதை எண்ணிக்கையில் சேர்க்கவும் மற்றும் அதிகரிப்பு i, j.

நடைமுறைப்படுத்தல்

சாத்தியமான முக்கோணங்களுக்கான சி ++ திட்டம்

#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 (n) நேரத்தில் இயங்குகிறது, ஏனெனில் k i + 2 இலிருந்து தொடங்கி j இன் அனைத்து மதிப்புகளுக்கும் n வரை செல்கிறது. எனவே, நேர சிக்கலானது O (n ^ 2) ஆகும்.

விண்வெளி சிக்கலானது

ஓ (1) ஏனென்றால் நிலையான மாறிலி சிக்கலுக்கு இட்டுச்செல்லும் சில மாறிகளை நாங்கள் உருவாக்குகிறோம்.

குறிப்புகள்