Решење са највећим кружним троуглом са трокутом


Ниво тешкоће Лако
Често питани у Ц3 ИоТ
Математика сортирање

Изјава о проблему

У проблему ”Највећи Периметар Троугао “добијамо низ са н вредности. Све вредности су позитивни цели бројеви. Поставите питање да бисте пронашли максимални опсег троугла који можемо конструисати из ових вредности. У случају да није могуће конструисати троугао, тада морамо исписати 0.

Пример

arr = [3,2,3,4]
10

objašnjenje: Највећи обим троугла који се може формирати помоћу ових вредности је 10, а странице троуглова су 4,3,3.

Приступ рјешењу највећег периметралног трокута са кодом

Ово је основни математички проблем. Да бисмо је решили, морамо знати ову теорему да је у троуглу сума дужине било које две странице увек већа од треће стране. У супротном, они неће формирати троугао. Рецимо да су странице троугла а, б и ц. Слике показују како није могуће конструисати троугао ако не задовољава ову теорему.

леетцоде решење највећег периметралног троугла

Како питање тражи проналажење највећег периметралног троугла, тако од свих могућих тројки које задовољавају услове а + б> ц, б + ц> а и а + ц> б морамо пронаћи тројку за коју а + б + ц је максимум.

Дакле, желимо да вредности а, б и ц буду што веће да бисмо добили највећи опсег. Сортираћемо низ, а затим ћемо почети са највеће три вредности ако задовољавају теорему. ако се догоди, онда је њихов збир потребна вредност. у супротном, проверићемо следеће три највеће вредности.

ако такав триплет не постоји онда је највећи опсег троугла 0.

 Имплементација

Ц ++ код за највећи периметарски троугао

#include <bits/stdc++.h> 
using namespace std; 
    int largestPerimeter(vector<int>&  arr) {
        int n=arr.size();
        sort(arr.begin(),arr.end());
       for (int i =n - 1; i > 1; --i)
            if (arr[i] < arr[i - 1] + arr[i - 2])
                return arr[i] + arr[i - 1] + arr[i - 2];
        return 0;
    }
int main() 
{ 
 vector<int> arr = { 3,2,3,4 }; 
 cout<<largestPerimeter(arr)<<endl; 
 return 0;
}
10

Јава код за највећи периметарски троугао

import java.util.Arrays; 
public class Tutorialcup {
    public static int largestPerimeter(int[] arr) {
        Arrays.sort(arr);
        int n= arr.length;
        for (int i =n - 1; i > 1; --i)
            if (arr[i] < arr[i - 1] + arr[i - 2])
                return arr[i] + arr[i - 1] + arr[i - 2];
        return 0;
    }
  public static void main(String[] args) {
    int [] arr = {3,2,3,4}; 
    int ans= largestPerimeter(arr);
    System.out.println(ans);
  }
}

 

10

Анализа сложености решења са највећим бројем кружних троуглова са троуглом

Временска сложеност

Временска сложеност горњег кода је О (нлогн) јер сортирамо низ. Овде је н величина низа.

Свемирска сложеност

Сложеност простора горњег кода је О (1) јер користимо само променљиву за чување одговора.

Референце