极客笔记C++ 数组分数（有理数）的最大公因数（HCF）
HCF或两个或多个数的最大公因数指的是能够整除它们的最大数。
有理数是两个数的商p/q，其中q不等于0。
问题描述
给定一个带有分数的数组，找出这些数字的最大公因数。
示例1
输入
[{4, 5}, {10, 12}, {24, 16}, {22, 13}]
输出
{2, 3120}
解释
给定的分数是：4/5，10/12，24/16和22/13
2/3120是能整除所有这些分数的最大数。
示例2
输入
[{18, 20}, {15, 12}, {27, 12}, {20, 6}]
输出
{3, 1400}
解释
给定的分数是：18/20，15/12，27/12和20/6。
1/60是可以整除所有这些分数的最大数。
方法
要找到分数的最大公约数（HCF），可以执行以下步骤：
- 计算分子的最大公约数。
-
计算分母的最小公倍数。
-
计算最大公约数/最小公倍数。
-
如果可能，将分数化简为最简分数。
让我们将上述方法分为两个部分：
找到分子的最大公约数
为了找到两个数的最大公约数，使用欧几里得算法。
算法使用以下事实：
- 两个数的最大公约数不变，如果从较大的数中减去较小的数。因此，如果我们不断从其中一个数中减去较小的数，最终得到的数就是最大公约数。
-
我们可以使用除法代替减法。如果我们除以较小的数，算法停止时余数变为0。
用于找到两个数最大公约数的C++函数
//Function to find HCF of two numbers
int HCF(int a, int b)
{
if (a % b == 0)
return b;
else
return (HCF(b, a % b));
}
现在，我们可以迭代地找到整个数组（多于两个数字）的分子的最大公约数。
//Function to find HCF of the numerator series
int findHcf(vector<pair<int,int>>v)
{
int hcf = v[0].first;
for (int i = 1; i < v.size(); i++)
hcf = HCF(hcf, v[i].first);
// return hcf of the numerators
return (hcf);
}
寻找分母的最小公倍数
要找到两个数a和b的最小公倍数，可以使用以下公式 –
LCM(a,b) * HCF (a,b) = a*b
Hence, LCM(a,b) = (a*b) / HCF(a,b)
现在，我们可以迭代地找到整个数组（超过两个数字）的分子的最小公倍数。
用于找到分母最小公倍数的C++函数
//Function to find lcm of the denominator series
int findLcm(vector<pair<int,int>>v)
{
// ans contains LCM of arr[0][1], ..arr[i][1]
int lcm = v[0].second;
for (int i = 1; i < v.size(); i++)
lcm = (((v[i].second * lcm)) /
(HCF(v[i].second, lcm)));
// return lcm of the denominator
return (lcm);
}
- 步骤1 - 初始化一对向量： **vector <pair<int,int>>vec **
-
步骤2 - 输入分数到 vec
-
步骤3 - ans -> 找到vec的最大公约数
-
步骤4 - 打印ans
伪代码
Function find_hcf_of_fraction(vec):
HCF_of_num -> findHCF(vec)
LCM_of_denom -> findLCM(vec)
Initialize vector ans: vectorans;
ans -> [Hcf_of_num, Lcm_of_num]
For i = ans[0]/2 to 2:
if (ans[1] % i == 0) and (ans[0] % i == 0):
ans[1] -> ans[1]/i
ans[0] -> ans[0]/i
return ans
Function find_HCF(vec):
hcf -> vec[0].first
For i=0 to vec.size()-1:
hcf -> HCF(ans, vec[i].first)
return ans
Function HCF(a,b):
if a%b->0:
return a
else:
return HCF(b , a%b)
Function findLCM(vec):
lcm -> vec[0].second
For i=0 to vec.size()-1:
lcm-> (lcm* vec[i].second) / (hcf (vec[i].second, lcm))
return lcm
示例（C++程序）
下面是一个用于找到有理数（分数）数组的最大公因数的CPP程序。
#include <bits/stdc++.h>
using namespace std;
//Function to find HCF of two numbers
int HCF(int a, int b){
if (a % b == 0)
return b;
else
return (HCF(b, a % b));
}
//Function to find HCF of the numerator series
int findHcf(vector<pair<int,int>>v){
int hcf = v[0].first;
for (int i = 1; i < v.size(); i++)
hcf = HCF(hcf, v[i].first);
// return hcf of the numerators
return (hcf);
}
//Function to find lcm of the denominator series
int findLcm(vector<pair<int,int>>v){
// ans contains LCM of arr[0][1], ..arr[i][1]
int lcm = v[0].second;
for (int i = 1; i < v.size(); i++)
lcm = (((v[i].second * lcm)) /
(HCF(v[i].second, lcm)));
// return lcm of the denominator
return (lcm);
}
//Function to get the answer
vector<int> find_hcf_of_fraction(vector<pair<int,int>>v){
//HCF of the numerator series
int hcf_of_num = findHcf(v);
// lcm of the denominator series
int lcm_of_deno = findLcm(v);
vector<int>ans(2);
ans[0] = hcf_of_num;
ans[1] = lcm_of_deno;
for (int i = ans[0] / 2; i > 1; i--) {
if ((ans[1] % i == 0) && (ans[0] % i == 0)) {
ans[1] /= i;
ans[0] /= i;
}
}
// return answer
return (ans);
}
//main code
int main(){
int size = 4;
vector<pair<int,int>>vec;
//Inserting the fractions in the vector
vec.push_back({4,5});
vec.push_back({10,12});
vec.push_back({24,16});
vec.push_back({22,13});
//Function call to calculate the HCF of the fractions
vector<int>ans;
ans = find_hcf_of_fraction(vec);
//Print the answer
cout << "HCF of given array of fractions: ";
cout << "{" << ans[0] << ", " << ans[1] << "}"<< endl;
return 0;
}
输出
对于输入 – [{4, 5}, {10, 12}, {24, 16}, {22, 13}]，上面的C++程序将产生以下输出：
HCF of given array of fractions: {2, 3120}
结论
本文讨论了寻找分数最大公约数的问题。文章涉及的内容包括方法、伪代码和C++程序。