資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用給定線段長度在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<N，並檢查if (Arr[i] > L)，在if語句中設定L=Arr[i]。在迴圈外部，將L的大小增加1。
然後初始化頻率陣列int Freq[L] = {0}。從i=0迴圈到i<N，並將每個線段的出現次數增加1。
初始化計數器count = 0（int型別），用於儲存最終的平行四邊形數量。
從i=0迴圈到i<L，並檢查可以用4條相似邊構造的平行四邊形，如果找到則相應地增加count的值。
初始化left=0（int型別），用於儲存可以用2條相似邊形成的平行四邊形的數量。
最後，從i=0迴圈到i<L，並檢查if(Freq[i] >= 2)，如果是，則將1新增到left。
設定count+= left/2並返回count。
示例
#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
更新於：2020年8月17日
99 次瀏覽
廣告