بزرگترین راه حل مثلث محیط مثلث محیط


سطح دشواری ساده
اغلب در اینترنت اشیا C C3
ریاضی مرتب سازی

بیان مسأله

در مسئله ”بزرگترین محیط مثلث »به ما یک آرایه با مقادیر n داده می شود. تمام مقادیر عدد صحیح مثبت هستند. س askال کنید تا حداکثر محیط مثلثی را که می توانیم از این مقادیر بسازیم پیدا کنید. در صورت عدم امکان ساخت مثلث ، باید 0 را چاپ کنیم.

مثال

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

شرح: بزرگترین محیط مثلث که می تواند با استفاده از این مقادیر تشکیل شود 10 و اضلاع مثلث 4,3,3،XNUMX،XNUMX است.

رویکرد برای بزرگترین راه حل مثلث محیط مثلث محیط

این یک مسئله اساسی ریاضی است. بنابراین برای حل آن باید این قضیه را بدانیم که در یک مثلث از طول هر دو ضلع همیشه بیشتر از ضلع سوم است. در غیر اینصورت مثلث تشکیل نخواهند داد. بگذارید بگوییم اضلاع مثلث هستند a ، b و c تصاویر نشان می دهد که اگر این قضیه را برآورده نکند چگونه ساخت مثلث امکان پذیر نیست.

راه حل کد به بزرگترین مثلث محیطی

همانطور که س asksال برای پیدا کردن بزرگترین مثلث محیطی می شود ، بنابراین از بین سه گانه های ممکن که شرایط a + b> c ، b + c> a و a + c> b را برآورده می کنند ، باید سه گانه ای را پیدا کنیم که a + b + c حداکثر است.

بنابراین می خواهیم مقادیر a ، b و c را تا حد ممکن بزرگتر بدست آوریم تا بیشترین محیط را بدست آوریم. ما آرایه را مرتب می کنیم و سپس با بزرگترین سه مقدار شروع به کار می کنیم اگر آنها قضیه را برآورده کنند. اگر چنین باشد ، مجموع آنها مقدار مورد نیاز است. در غیر این صورت ، سه مقدار بزرگ بعدی را بررسی خواهیم کرد.

اگر چنین سه گانه ای وجود نداشته باشد ، بزرگترین محیط مثلث 0 است.

 پیاده سازی

کد ++ C برای بزرگترین مثلث محیط

#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

آنالیز پیچیدگی بزرگترین محلول مثلث محیط مثلث محیط

پیچیدگی زمانی

پیچیدگی زمانی کد فوق است O (nlogn) زیرا ما در حال مرتب سازی آرایه هستیم. در اینجا n اندازه آرایه است.

پیچیدگی فضا

پیچیدگی فضایی کد فوق است O (1) زیرا ما فقط از یک متغیر برای ذخیره پاسخ استفاده می کنیم.

منابع