Chúng ta được cung cấp với một mảng số Arr []. Mục đích là đếm số bộ ba có tích bằng tích nhỏ nhất của tất cả các bộ ba có thể có. Đếm bộ ba nếu (i
Chúng ta sẽ làm điều này bằng cách tìm tích nhỏ nhất trong đó (i
Hãy cùng hiểu với các ví dụ.
Đầu vào - arr [] ={1,2,3,2,4,1,5}
Đầu ra - Số lượng sinh ba - 2
Giải thích -
Đầu vào - arr [] ={1,1,2,1,2,2}
Đầu ra - Số sinh ba - 1
Giải thích -
Chúng tôi lấy một mảng số nguyên Arr [] được khởi tạo với các số ngẫu nhiên.
Lấy một biến N lưu trữ độ dài của Arr [].
Hàm countTriplets (int arr [], int n) nhận một mảng, độ dài của nó làm đầu vào và trả về các bộ ba có tích bằng tích tối thiểu.
Lấy biến số ban đầu là 0 cho số lượng bộ ba.
Lấy tiền biến ban đầu là tích của mỗi bộ ba. Ban đầu là 1.
Lấy biến minprod ban đầu là tích tối thiểu có thể có của tất cả các bộ ba. Ban đầu là 999.
Traverse mảng sử dụng ba vòng lặp for cho mỗi phần tử của bộ ba.
Vòng ngoài cùng từ 0 <=i
Tính prod =arr [i] * arr [j] * arr [k]. Nếu prod <=minprod thì hãy cập nhật minprod bằng sản phẩm.
Bây giờ minprod có giá trị là tích ít nhất trong tất cả các bộ ba.
Một lần nữa duyệt mảng bằng cách sử dụng ba vòng lặp for cho mỗi phần tử của bộ ba.
Vòng ngoài cùng từ 0 <=i
Tính prod =arr [i] * arr [j] * arr [k]. Nếu prod ==minprod thì số gia tăng. Vì cặp này có sản phẩm tối thiểu.
Ở cuối tất cả các vòng đếm sẽ có tổng số bộ ba đáp ứng điều kiện.
Trả về kết quả là số lượng.
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau - 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.
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.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Ví dụ
#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;
} Đầu ra
Number of triplets : 2
