จำนวนสูงสุดของสี่เหลี่ยมด้านขนานที่สามารถทำได้โดยใช้ความยาวของส่วนของเส้นตรงที่กำหนดใน C++

ภารกิจคือการหาจำนวนสูงสุดของสี่เหลี่ยมด้านขนานที่สามารถทำได้โดยใช้ส่วนของเส้นตรงจำนวน N ที่กำหนด ถ้าแต่ละส่วนของเส้นสามารถใช้ได้มากสุดในหนึ่งรูปสี่เหลี่ยมด้านขนาน

ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง -

ป้อนข้อมูล − Arr[] ={8, 3, 1, 3, 8, 7, 1, 3, 5, 3}

ผลผลิต − 2

คำอธิบาย − ด้วยส่วนของเส้นตรงที่ให้ไว้ข้างต้น สี่เหลี่ยมด้านขนานสองรูปที่สามารถสร้างได้นั้นมีด้าน 8, 1, 8, 1 และ 3, 3, 3, 3 ตามลำดับ

ป้อนข้อมูล − Arr[] ={7, 9, 9, 7}

ผลผลิต − 1

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

• จำนวนสูงสุดของสี่เหลี่ยมด้านขนานที่สามารถทำได้คือ =สี่เหลี่ยมด้านขนานที่สามารถสร้างด้วยด้านที่เท่ากันหรือใกล้เคียงกัน 4 ด้าน บวกกับสี่เหลี่ยมด้านขนานที่สามารถสร้างได้โดยใช้ 2 ด้านที่คล้ายกัน

• ในฟังก์ชัน MaxParr() ให้กำหนดค่าเริ่มต้นของตัวแปร L =Arr[0] ซึ่งจะใช้เป็นขนาดของอาร์เรย์ที่จะใช้เก็บความถี่ของส่วนของเส้นตรง

• วนจาก i=1 ถึง i L) และภายในคำสั่ง if ใส่ L=Arr[i] นอกวงเพิ่มขนาด L ขึ้น 1

• จากนั้นเริ่มต้นอาร์เรย์ความถี่ int Freq[L] ={0} วนจาก i=0 จนถึง i

• การนับเริ่มต้น =0 ของประเภท int เพื่อเก็บการนับสุดท้ายของสี่เหลี่ยมด้านขนาน

• วนจาก i=0 ถึง i

• เริ่มต้น left=0 ของประเภท int เพื่อเก็บจำนวนสี่เหลี่ยมด้านขนานที่สามารถเกิดขึ้นได้โดยใช้ 2 ด้านที่คล้ายกัน

• สุดท้ายวนจาก i=0 ถึง i=2) และถ้าเป็นเช่นนั้นให้เพิ่ม 1 ไปทางซ้าย

• ใส่ count+=left/2 แล้วนับกลับ

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int MaxParr(int N, int Arr[]){
   //Finding length of frequency array
   int L = Arr[0];
   for (int i = 1; i < N; i++){
      if (Arr[i] > L)
         L = Arr[i];
   }
   L = L + 1;
   int Freq[L] = {0};
   for (int i = 0; i < N; i++){
      //Increasing occurrence of each line segment
      Freq[Arr[i]] += 1;
   }
   // To store the number of parallelograms
   int count = 0;
   for (int i = 0; i < L; i++){
      /*parallelograms that can be made using 4 same sides*/
      count += int(Freq[i] / 4);
      Freq[i] = Freq[i] % 4;
   }
   int left = 0;
   for (int i = 0; i < L; i++){
      //Counting segments with 2 or more occurrences left
      if (Freq[i] >= 2)
         left += 1;
   }
   /*Adding parallelograms that can be formed using using 2 similar sides into the final count*/
   count += left / 2;
   return count;
}
int main(){
   int N = 10;
   int Arr[] = { 8, 3, 1, 3, 8, 7, 1, 3, 5, 3};
   cout<< MaxParr(N, Arr);
}

ผลลัพธ์

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

2