Số lượng hình bình hành tối đa có thể được tạo bằng cách sử dụng độ dài đã cho của các đoạn thẳng trong C ++

Nhiệm vụ được giao là tìm số lượng hình bình hành tối đa có thể được tạo ra bằng cách sử dụng N số đoạn thẳng cho trước nếu mỗi đoạn thẳng có thể được sử dụng nhiều nhất trong một hình bình hành.

Bây giờ chúng ta hãy hiểu những gì chúng ta phải làm bằng cách sử dụng một ví dụ -

Đầu vào - Arr [] ={8, 3, 1, 3, 8, 7, 1, 3, 5, 3}

Đầu ra - 2

Giải thích - Với đoạn thẳng đã cho ở trên, hai hình bình hành có thể tạo thành có các cạnh lần lượt là 8, 1, 8, 1 và 3, 3, 3, 3.

Đầu vào - Arr [] ={7, 9, 9, 7}

Đầu ra - 1

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Số hình bình hành tối đa có thể được tạo thành =Hình bình hành có thể tạo thành 4 cạnh bằng nhau hoặc giống nhau cộng với các hình bình hành có thể tạo ra bằng 2 cạnh giống nhau.

• Trong hàm MaxParr (), hãy khởi tạo một biến L =Arr [0] sẽ được sử dụng làm kích thước của mảng sẽ được sử dụng để lưu trữ tần số của các đoạn thẳng.

• Lặp lại từ i =1 cho đến khi i L), và bên trong câu lệnh if đặt L =Arr [i]. Bên ngoài vòng lặp, tăng kích thước của L lên 1.

• Sau đó khởi tạo mảng tần số int Freq [L] ={0}. Lặp lại từ i =0 đến i

• Số khởi tạo =0 của kiểu int để lưu trữ số cuối cùng của các hình bình hành.

• Lặp lại từ i =0 cho đến i

• Khởi tạo left =0 kiểu int để lưu trữ số lượng hình bình hành có thể được tạo thành bằng cách sử dụng 2 cạnh giống nhau.

• Cuối cùng lặp lại từ i =0 cho đến i =2) và nếu có thì thêm 1 vào bên trái.

• Đặt số đếm + =trái / 2 và số đếm trả về.

Ví dụ

#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);
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -

2