Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 최소 곱 삼중항을 형성하는 방법 세기


Arr[] 숫자 배열이 제공됩니다. 목표는 곱이 가능한 모든 삼중항의 가장 작은 곱과 같은 삼중항의 수를 계산하는 것입니다. (i

우리는 먼저 (i

예를 들어 이해합시다.

입력 - arr[]={ 1,2,3,2,4,1,5 }

출력 − 세 쌍의 수 − 2

설명 -

Here minimum product is 2
Triplet 1[ 1,2,3,2,4,1,5 ] → (1,2,1) product=2
Triplet 2 [ 1,2,3,2,4,1,5 ] → (1,2,1) product=2
Number of triplets with product 2 which is minimum is 2.

입력 - arr[]={ 1,1,2,1,2,2 }

출력 − 세 쌍의 수 − 1

설명 -

Here minimum product is 1
Triplet 1 [ 1,1,2,1,2,2 ] → (1,1,1) product=1
Number of triplets with product 1 which is minimum is 1.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

  • 임의의 숫자로 초기화된 정수 배열 Arr[]을 사용합니다.

  • Arr[]의 길이를 저장하는 변수 N을 사용합니다.

  • countTriplets(int arr[], int n) 함수는 배열의 길이를 입력으로 받아 곱이 최소 곱과 같은 트리플렛을 반환합니다.

  • 세 쌍의 수에 대해 초기 변수 개수를 0으로 취합니다.

  • 초기 변수 prod를 각 삼중항의 곱으로 취합니다. 처음에는 1.

  • 초기 변수 minprod를 모든 삼중항의 가능한 최소 곱으로 취합니다. 처음에는 999.

  • 트리플렛의 각 요소에 대해 세 개의 for 루프를 사용하여 배열을 탐색합니다.

  • 0<=i

  • prod=arr[i]*arr[j]*arr[k]를 계산합니다. prod<=minprod이면 minprod를 prod로 업데이트합니다.

  • 이제 minprod는 모든 삼중항 중 최소 곱의 값을 갖습니다.

  • 다시 트리플렛의 각 요소에 대해 세 개의 for 루프를 사용하여 배열을 탐색합니다.

  • 0<=i

  • prod=arr[i]*arr[j]*arr[k]를 계산합니다. prod==minprod이면 카운트를 증가시킵니다. 이 쌍에는 최소 제품이 있습니다.

  • 모든 루프가 끝나면 조건을 충족하는 총 3중항 수가 계산됩니다.

  • 카운트를 결과로 반환합니다.

예시

#include <bits/stdc++.h>
using namespace std;
int countTriplets(int arr[],int n){
   int count = 0;
   int prod=1;
   int minprod=9999; //making minimum as larger than any product in array
   for (int i = 0; i < n-2; i++){
      for (int j = i+1; j < n-1; j++){
         for (int k = j+1; k < n; k++){
            prod=arr[i]*arr[j]*arr[k];
            if ( prod<=minprod )
               { minprod=prod; }
         }
      }
   }
   // cout<<"minproduct :"<<minprod; //to print minimum product
   for (int i = 0; i < n-2; i++){
      for (int j = i+1; j < n-1; j++){
         for (int k = j+1; k < n; k++){
            prod=arr[i]*arr[j]*arr[k];
            if ( prod==minprod ){
               count++;
               //cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]<<" c :"<<arr[k]; //to print
            }
         }
      }
   }
   return count;
}
int main(){
   int Arr[]={ 1,2,3,1,2,6};
   int N=5; //length of array
   cout <<endl<< "Number of triplets : "<<countTriplets(Arr,N);
   return 0;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

Number of triplets : 2