Array-dan Pisagor üçlülərini tapın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon LinkedIn MakeMyTrip Mintra Kahin
GeyimBaxılıb 610

Problem bəyanat

Biz verdik array n tam ədədi ehtiva edir. Verilmiş massivdən Pifaqor üçqatının çoxluğunu tapmalıyıq.
Qeyd: Pifaqor üçəmlərinin vəziyyəti: a ^ 2 + b ^ 2 = c ^ 2.

misal

Input

6

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

Buraxılış

Pisagor üçlüləri: 3, 4, 5

Yanaşma 1

Burada kobud güc alqoritmindən istifadə edirik:

Alqoritm

1 Adım: 3 döngədən istifadə edirik ki, massivdən 3 fərqli element dəsti götürək.
a. Döngələr üçün 3 işləyirik. Elə ki, hər biri üçün özündən başqa bütün dəyərləri alırıq b. Hər b üçün a-nın bütün dəyərlərini alırıq.
b. a, b, c massivdəki elementlərdir.

2 Adım: (a, b, c) bütün dəstləri üçün a * a + b * b = c * c olan Pifaqor şərtini yerinə yetiririk. doğru olduqda onları çap edirik.
a. A ^ 2 + b ^ 2 = c ^ 2 olarsa, a, b, c yazdırın.

Həyata keçirilməsi

Dizidən Pifaqor üçlülərini tapmaq üçün C ++ proqramı

#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;
}

Dizidən Pifaqor üçlülərini tapmaq üçün Java Proqramı

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

Dizidən Pifaqor üçlülərini tapmaq üçün mürəkkəblik analizi

Zaman mürəkkəbliyi

O (n ^ 3) hara n massivin ölçüsüdür. Burada mümkün olan hər üçqatın vəziyyətini yoxlayırıq.

Kosmik Mürəkkəblik

O (1) çünki cavabı hesablamaq üçün bir neçə dəyişəndən istifadə edirik.

Yanaşma 2

Alqoritm

  1.   Verilən massivi əvvəlcə sıralama funksiyasından istifadə edərək sırala.
  2.  Rəqəmləri saxlamaq əvəzinə Pifaqor teoremini birbaşa yoxlamaq üçün hər elementin kvadratını saxlayır.
  3. Ən kiçik tərəf kimi a götürün, hər bir yoxlama üçün massivdən şərtləri təmin edən elementləri yoxlayın (a = c - b). bu şərti təmin etsələr a ^ 2 + b ^ 2 = c ^ 2 şərtini təmin etdikləri üçün Pifaqor üçlüyü əmələ gətirirlər.
    a. massivdəki bütün elementlər üçün ilk elementi “a” kimi saxlayın.
    b. son iki elementi müvafiq olaraq “b” və “c” kimi saxlayın.
    c. “A = c - b” şərtini yoxlayın. doğru olduqda a, b, c kvadratlarını Pisaqor üçlüləri dəsti kimi çap edin.
    d. Əgər “c - b” “a” dan böyükdürsə, daha böyük elementə (c) yönələn dəyişəni azaldır ki, bütün “c” -ləri yoxlayırıq, bu şərt doğrudur ya yox. Əgər “c - b” azalmadan azdırsa, kiçik elementləri göstərən dəyişən, beləliklə bütün b-ləri yoxlayırıq, bu şərt doğrudur ya yox.
    e. bu döngəni hamı üçün davam etdirin
    f. Heç bir şey tapmasanız, üçük yazdırmayın.

Həyata keçirilməsi

C ++ proqramı Array-dan Pisagor üçlülərini tapın

#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;
}

Dizidən Pifaqor üçlülərini tapmaq üçün Java Proqramı

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

Dizidən Pifaqor üçlülərini tapmaq üçün mürəkkəblik analizi

Zaman mürəkkəbliyi

O (n ^ 2), burada n massivin ölçüsüdür. Burada hər I dəyəri üçün iki göstərici metodundan istifadə edirik. Bu, bizi O (N * N) zaman mürəkkəbliyinə aparır.

Kosmik Mürəkkəblik

O (1), çünki cavabı hesablamaq üçün bir neçə dəyişən istifadə edirik.

References

Translate »