ដំណោះស្រាយត្រីកោណដែលមានទំហំធំជាងគេបំផុតនៅលើត្រីកោណ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ស៊ី ៣ អ៊ីយ៉ូត
គណិតវិទ្យា តម្រៀប

សេចក្តីថ្លែងការណ៍បញ្ហា

នៅក្នុងបញ្ហា” ធំបំផុត បរិវេណ ត្រីកោណ” យើងត្រូវបានផ្តល់អារេដែលមានតំលៃ n ។ តម្លៃទាំងអស់គឺជាចំនួនគត់វិជ្ជមាន។ សំណួរសួរដើម្បីរកបរិមាត្រអតិបរិមានៃត្រីកោណដែលយើងអាចសង់ចេញពីតម្លៃទាំងនេះ។ ក្នុងករណីដែលមិនអាចសាងសង់ត្រីកោណបានទេនោះយើងត្រូវបោះពុម្ព ០ ។

ឧទាហរណ៍

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

ការពន្យល់: បរិវេណធំបំផុតនៃត្រីកោណដែលអាចត្រូវបានបង្កើតឡើងដោយប្រើតម្លៃទាំងនេះគឺ ១០ និងជ្រុងត្រីកោណគឺ ៤,៣,៣ ។

វិធីសាស្រ្តសម្រាប់ដំណោះស្រាយត្រីកោណដែលមានទំហំធំបំផុត Leetcode

នេះគឺជាបញ្ហាគណិតវិទ្យាមូលដ្ឋាន។ ដូច្នេះដើម្បីដោះស្រាយវាយើងត្រូវស្គាល់ទ្រឹស្តីបទនេះថាក្នុងផលបូកត្រីកោណនៃប្រវែងនៃជ្រុងទាំងពីរគឺធំជាងផ្នែកទីបីជានិច្ច។ បើមិនដូច្នោះទេពួកគេនឹងមិនបង្កើតជាត្រីកោណទេ។ ចូរយើងនិយាយថាជ្រុងនៃត្រីកោណគឺ a, b, និងគ។ រូបភាពបង្ហាញពីរបៀបដែលមិនអាចបង្កើតត្រីកោណបានប្រសិនបើវាមិនពេញចិត្តទ្រឹស្តីបទនេះ។

ដំណោះស្រាយ leetcode ចំពោះត្រីកោណបរិវេណធំបំផុត

ដូចដែលសំណួរសួរដើម្បីរកត្រីកោណដែលធំជាងគេដូច្នេះក្នុងចំណោមត្រីកោណដែលអាចធ្វើបានដែលបំពេញលក្ខខណ្ឌ a + b, c, b + c> a, និង a + c </b> b យើងត្រូវរកកន្លែងណាដែល a b + c គឺអតិបរមា។

ដូច្នេះយើងចង់បានតម្លៃនៃ a, b, និង c ធំតាមដែលអាចធ្វើទៅបានដើម្បីទទួលបានបរិវេណធំបំផុត។ យើងនឹងតំរៀបជួរហើយបន្ទាប់មកយើងនឹងចាប់ផ្តើមជាមួយតំលៃធំជាងគេបីប្រសិនបើពួកគេពេញចិត្តទ្រឹស្តីបទ។ ប្រសិនបើវាកើតឡើងនោះផលបូករបស់ពួកគេគឺជាតម្លៃដែលត្រូវការ។ បើមិនដូច្នោះទេយើងនឹងពិនិត្យមើលតម្លៃធំបំផុតបីបន្ទាប់។

ប្រសិនបើមិនមានជើងហោះហើរបែបនេះទេនោះបរិវេណធំបំផុតនៃត្រីកោណគឺ ០ ។

 ការអនុវត្តន៍

កូដ 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

ការវិភាគស្មុគស្មាញនៃដំណោះស្រាយត្រីកោណដែលមានទំហំធំជាងគេបំផុត Leetcode

ភាពស្មុគស្មាញពេលវេលា

ពេលវេលាស្មុគស្មាញនៃលេខកូដខាងលើគឺ O (nlogn) ពីព្រោះយើងកំពុងតំរៀបជួរ។ នៅទីនេះ n គឺជាទំហំនៃអារេ។

ភាពស្មុគស្មាញនៃលំហ

ភាពស្មុគស្មាញចន្លោះនៃលេខកូដខាងលើគឺ ឱ (១) ពីព្រោះយើងកំពុងប្រើតែអថេរដើម្បីរក្សាទុកចម្លើយ។

ឯកសារយោង