นับวิธีสร้างผลิตภัณฑ์แฝดสามขั้นต่ำใน 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[] ที่เริ่มต้นด้วยตัวเลขสุ่ม

• ใช้ตัวแปร N ซึ่งเก็บความยาวของ Arr[].

• ฟังก์ชัน countTriplets(int arr[], int n) รับอาร์เรย์ความยาวเป็นอินพุตและส่งกลับ triplets ที่มีผลิตภัณฑ์เท่ากับผลิตภัณฑ์ขั้นต่ำ

• นำตัวแปรเริ่มต้นนับเป็น 0 สำหรับจำนวนแฝดสาม

• ใช้ตัวแปรเริ่มต้นเป็นผลคูณของแฝดสามแต่ละตัว เริ่มแรก 1.

• ใช้ตัวแปรตั้งต้น minprod เป็นผลิตภัณฑ์ขั้นต่ำที่เป็นไปได้ของแฝดสามทั้งหมด เริ่มต้น 999.

• Traverse array ใช้สาม for loops สำหรับแต่ละองค์ประกอบของ triplet

• วงนอกสุดจาก 0<=i

• คำนวณ prod=arr[i]*arr[j]*arr[k] หาก prod<=minprod ให้อัปเดต minprod ด้วย prod

• ตอนนี้ minprod มีค่าผลิตภัณฑ์น้อยที่สุดของแฝดทั้งหมด

• ข้ามอาร์เรย์อีกครั้งโดยใช้สามลูปสำหรับแต่ละองค์ประกอบของแฝด

• วงนอกสุดจาก 0<=i

• คำนวณ prod=arr[i]*arr[j]*arr[k] ถ้า prod==minprod ให้นับเพิ่ม เนื่องจากคู่นี้มีสินค้าขั้นต่ำ

• เมื่อสิ้นสุดการวนซ้ำทั้งหมดจะนับจำนวน triplets ทั้งหมดที่ตรงตามเงื่อนไข

• คืนค่าการนับเป็นผลลัพธ์

ตัวอย่าง

#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