იპოვნეთ პითაგორას სამეული სამი მასივიდან  


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon LinkedIn MakeMyTrip მიტრა Oracle
Array

პრობლემის განცხადება  

ჩვენ მივეცით მასივი რომელიც შეიცავს n მთლიან რიცხვს. ჩვენ უნდა ვიპოვოთ პითაგორას სამმაგი ნაკრები მოცემული მასივიდან.
შენიშვნა: პითაგორას სამეულის მდგომარეობა: a ^ 2 + b ^ 2 = c ^ 2.

მაგალითი  

შეყვანის

6

[3, 4, 6, 5, 7, 8]

გამოყვანის

პითაგორას სამეული: 3, 4, 5

მიდგომა 1  

ჩვენ ვიყენებთ უხეში ძალის ალგორითმს აქ:

ალგორითმი

ნაბიჯი 1: ჩვენ ვიყენებთ 3 მარყუჟს, რომ მასივიდან ავიღოთ 3 განსხვავებული ელემენტის ნაკრები.
ა ჩვენ ვაწარმოებთ 3 მარყუჟს. ისეთი, რომ ყველასთვის ვიღებთ ყველა მნიშვნელობას b, გარდა საკუთარი თავისა. ყოველი b- სთვის ვიღებთ a- ს ყველა მნიშვნელობას.
ბ a, b, c არის მასივის ელემენტები.

ნაბიჯი 2: ჩვენ ვაწარმოებთ პითაგორას პირობას, რომელიც არის a * a + b * b = c * c, (a, b, c) –ს სიმრავლეებისათვის. ჩვენ ვბეჭდავთ მათ, როდესაც ეს სიმართლეა.
ა თუ a ^ 2 + b ^ 2 = c ^ 2, დაბეჭდეთ a, b, c.

განხორციელება

C ++ პროგრამა მასივიდან პითაგორას სამეულის პოვნისთვის

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int N;
  cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  int a,b,c;
  for(int i = 0; i < N-2; i++)//select an element
  {
    for(int j=i+1;j <N-1; j++)//select an element in front of the considered element
      {
        for(int k =i+2; k<N;k++)// this element will be one ahead of the previously selected element in the jus touter loop
        {
          a = arr[i];
          b = arr[j];
          c = arr[k];
          if(a*a + b*b == c*c) // if the chosen elements satisfy the pythagoras theorem then simply print the three values.
            cout << a <<"  "<<b<<"  "<<c<<endl;
            
        }
      }
  }  
  return 0;
}

ჯავას პროგრამა მასივიდან პითაგორას სამეული

import static java.lang.Integer.max;
import java.util.Scanner;

class sum
{
    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 a,b,c;
        for(int i=0;i<n-2;i++)//select an element
        {
            for(int j=i+1;j<n-1;j++)//select an element in front of the considered element
            {
                for(int k=i+2;k<n;k++)// this element will be one ahead of the previously selected element in the jus touter loop
                {
                  a = arr[i];
                  b = arr[j];
                  c = arr[k];
                  if(a*a + b*b == c*c) // if the chosen elements satisfy the pythagoras theorem then simply print the three values.
                    System.out.println(a +"  "+b+"  "+c);
                }
              }
          }
    }
}
6
3 4 6 5 7 8
3  4  5

სირთულის ანალიზი მასივიდან პითაგორას სამეულის მოსაძებნად

დროის სირთულე

O (n ^ 3) სადაც n არის მასივის ზომა. აქ ჩვენ ვამოწმებთ ყველა შესაძლო ტრიპლეტის მდგომარეობას.

იხილეთ ასევე
ლოგიკური პარენტეზის პრობლემა

სივრცის სირთულე

O (1) რადგან პასუხის გამოსათვლელად რამდენიმე ცვლადს ვიყენებთ.

მიდგომა 2  

ალგორითმი

  1.   მოცემული მასივის დალაგება ჯერ ფუნქციის დალაგების გამოყენებით.
  2.  ციფრების შენახვის ნაცვლად შეინახეთ თითოეული ელემენტის კვადრატი, რათა პირდაპირ შეამოწმოთ პითაგორას თეორემა.
  3. მიიღეთ უმცირესი მხარე, ყოველი შემოწმებისას მასივის ელემენტები, რომლებიც აკმაყოფილებენ პირობას (a = c - b). თუ ისინი აკმაყოფილებენ ამ პირობას, ისინი ქმნიან პითაგორას სამეულს, რადგან ისინი აკმაყოფილებენ პირობას a ^ 2 + b ^ 2 = c ^ 2
    ა მასივის ყველა ელემენტისთვის თავიდანვე შეინახეთ პირველი ელემენტი როგორც "a".
    ბ შეინახეთ ბოლო ორი ელემენტი შესაბამისად "b" და "c".
    გ შეამოწმეთ მდგომარეობა "a = c - b". თუ ჭეშმარიტი ბეჭდეთ a, b, c კვადრატები, როგორც პითაგორას სამეული სამი.
    დ თუ "c - b" მეტია "a" - ზე, შეამცირეთ ცვლადი უფრო დიდ ელემენტზე (c), რომ შევამოწმოთ ყველა "c", არის თუ არა ეს პირობა სიმართლე. თუ ”c - b” შემცირებაზე ნაკლებია, ცვლადი მიუთითებს პატარა ელემენტებზე, ისე რომ ჩვენ ვამოწმებთ ყველა b- ს, ეს მდგომარეობა მართალია თუ არა.
    ე გააგრძელეთ ეს მარყუჟი ყველასთვის
    ვ. თუ ვერ იპოვნეს, სამეული არ დაბეჭდეთ.

განხორციელება

C ++ პროგრამა: იპოვნეთ პითაგორას სამეული სამი მასივიდან

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N;
  cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  int a,b,c;
  sort(arr,arr+N); //sort the array 
  for(int i=0; i < N; i++)
  arr[i] = (arr[i] * arr[i]); //store the square of each element to directly check the pythagoras theorem
  
  for(int i=0; i<N; i++)
  {
    int left = N-2 , right = N-1;
    a = arr[i]; // first side of the triangle
    
    while(left > i) 
    {
      b = arr[left];
      c = arr[right];
      
      int calculated_side = c - b; //if a*a + b*b = c*c then obviously c*c - b*b = a*a , we utilize this to check the condition
      if(calculated_side == a)
        {
          cout << sqrt(a) << "  "  << sqrt(b) << "  " << sqrt(c) << endl;
          left++; right--; 
        }
      else if (calculated_side > a) //if side is larger than expected then decrease  the variable pointing at the larger element
        right--;
      else // if side is smaller than expected then decrease the variable pointing at the smaller element
        left--;
    }
  }
  return 0;
}

ჯავას პროგრამა მასივიდან პითაგორას სამეული

import static java.lang.Math.sqrt;
import java.util.Arrays;
import java.util.Scanner;

class sum
{
    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 a,b,c;
        Arrays.sort(arr); //sort the array 
        for(int i=0;i<n;i++)
        arr[i] = (arr[i] * arr[i]); //store the square of each element to directly check the pythagoras theorem
        for(int i=0;i<n;i++)
        {
          int left = n-2 , right = n-1;
          a = arr[i]; // first side of the triangle
          while(left > i) 
          {
            b = arr[left];
            c = arr[right];
            int calculated_side = c - b; //if a*a + b*b = c*c then obviously c*c - b*b = a*a , we utilize this to check the condition
            if(calculated_side == a)
              {
                System.out.println((int)sqrt(a) + "  "  + (int)sqrt(b) + "  " + (int)sqrt(c));
                left++; right--; 
              }
            else if (calculated_side > a) //if side is larger than expected then decrease  the variable pointing at the larger element
              right--;
            else // if side is smaller than expected then decrease the variable pointing at the smaller element
              left--;
          }
        }
    }
}
25
3 8 4 10 6 5 12 13 27 117 165 19 176 169 44 113 24 145 143 51 149 52 173 181 125
3  4  5
5  12  13
6  8  10
24  143  145
44  117  125
52  165  173

სირთულის ანალიზი მასივიდან პითაგორას სამეულის მოსაძებნად

დროის სირთულე

O (n ^ 2) სადაც n არის მასივის ზომა. აქ ვიყენებთ მაჩვენებლის ორ მეთოდს თითოეული I მნიშვნელობისთვის. ეს O (N * N) დროის სირთულემდე მიგვიყვანს.

იხილეთ ასევე
სიმების შესატყვისი მასივში Leetcode Solution

სივრცის სირთულე

O (1) რადგან პასუხის გამოსათვლელად რამდენიმე ცვლადს ვიყენებთ.

ლიტერატურა