数据结构
网络
关系数据库管理系统(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 次浏览
广告