นับวิธีเลือกคู่ที่มีความแตกต่างสูงสุดใน C++

เราได้รับอาร์เรย์ของตัวเลข Arr[] เป้าหมายคือการนับจำนวนคู่ที่มีผลต่างเท่ากับผลต่างสูงสุดของคู่ที่เป็นไปได้ทั้งหมด นับคู่ (i!=j) และ arr[x]- arr[y] เป็นไปได้สูงสุด

เราจะทำสิ่งนี้โดยค้นหาความแตกต่างสูงสุดก่อน โดยที่ (i!=j) และเก็บเป็น maxdiff จากนั้นนับคู่ทั้งหมดที่มีความแตกต่าง=maxdiff

มาทำความเข้าใจกับตัวอย่างกัน

ป้อนข้อมูล − arr[]={ 1,2,3,2,4,1,5 }

ผลผลิต − จำนวนวิธีเลือกคู่ที่มีความแตกต่างสูงสุด − 2

คำอธิบาย −

Here minimum no. is 1 and maximum number is 5, maximum difference =5-1=4
Pair 1 [ 1,2,3,2,4,1,5 ] → (1,5) difference=4
Pair 2 [ 1,2,3,2,4,1,5 ] → (1,5) difference=4
Number of pairs with difference which is maximum=2.

ป้อนข้อมูล − arr[]={ 2,4,2,4 }

ผลผลิต − จำนวนวิธีเลือกคู่ที่มีความแตกต่างสูงสุด − 4

คำอธิบาย −

Here minimum no. is 2 and maximum number is 4, maximum difference =4-2=2
Pair 1 [ 2,4,2,4 ] → (2,4) difference=2
Pair 2 [ 2,4,2,4 ] → (2,4) difference=2
Pair 3 [ 2,4,2,4 ] → (4,2) difference=2
Pair 4 [ 2,4,2,4 ] → (2,4) difference=2
Number of pairs with difference which is maximum=4.

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• เราใช้อาร์เรย์จำนวนเต็ม Arr[] ที่เริ่มต้นด้วยตัวเลขสุ่ม

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

• ฟังก์ชัน countPairs(int arr[],int n) รับอาร์เรย์ความยาวเป็นอินพุตและส่งกลับวิธีการเลือกคู่ที่มีความแตกต่างเท่ากับผลต่างสูงสุด

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

• ใช้ค่าต่างของตัวแปรเป็นค่าส่วนต่างของแต่ละคู่

• ใช้ตัวแปร maxdiff เป็นค่าความแตกต่างสูงสุดของทุกคู่

• ค้นหาค่าสูงสุดและต่ำสุดจากอาร์เรย์และเก็บไว้ใน maxx และ mini ตามลำดับ

• ตอนนี้ maxdiff จะเป็น maxx-mini

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

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

• คำนวณ diff=arr[i]-arr[j] หรือ arr[j]-arr[i] ให้นับแยกกัน หากการเพิ่มขึ้น diff==maxdiff นับเนื่องจากคู่นี้มีความแตกต่างสูงสุด

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

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int countWays(int arr[],int n){
   int count = 0;
   int diff;
   int maxdiff=0; //making minimum as larger than any product in array
   int mini,maxx;
   mini=maxx=arr[0];
   for (int i = 0; i < n; i++) //find minimum and maximum values{
      if(arr[i]<mini)
         {mini=arr[i];}
      if(arr[i]>maxx)
         { maxx=arr[i]; }
   }
   maxdiff=maxx-mini; //this is maximum difference
   //cout<<maxx<<" "<<mini;
   for (int i = 0; i < n-1; i++){
      for (int j = i+1; j < n; j++){
         diff=arr[i]-arr[j]; //pair 1
         if ( diff==maxdiff ){
            count++;
            //cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; //to print
         }
         diff=arr[j]-arr[i]; //pair 2
         if ( diff==maxdiff ){
            count++;
            //cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; //to print
         }
      }
   }
   return count;
}
int main(){
   int Arr[]={ 3, 2, 1, 1, 3 };
   int N=5; //length of array
   cout <<endl<< "No. of ways of choosing pair with maximum difference : "<<countWays(Arr,N);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

No. of ways of choosing pair with maximum difference : 4