分数(或有理数)数组的 HCF

HCF 或两个或多个数字的最大共同因子是指除以它们的最大数字。

有理数是两个数字的商 p/q，其中 q 不等于 0。

问题陈述

给定一个包含分数的数组，找到数字的 HCF。

示例 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，请执行以下步骤 -

• 计算分子的 HCF。

• 计算分母的 LCM。

• 计算 HCF/LCM。

• 如果可能，将分数简化为最小分数。

让我们将上述方法分为两部分 -

查找分子的 HCF

要找到两个数字的 HCF，使用欧几里得方法。

该算法使用以下事实−

• 如果我们用较大的数字减去较小的数字，两个数字的 HCF 不会改变。因此，如果我们继续用较大的数字减去较小的数字，我们最终会得到 HCF。

• 我们可以使用除法而不是减法。如果我们除以较小的数字，当余数为 0 时算法就会停止。

用于查找两个数字的 HCF 的 C++ 函数

//用于查找两个数字的 HCF 的函数
int HCF(int a, int b)
{
   if (a % b == 0)
      return b;
   else
      return (HCF(b, a % b));
}

现在，我们可以迭代地找到整个数组(两个以上的数字)的分子的 HCF。

//用于查找分子系列的 HCF 的函数
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);
   // 返回分子的 hcf
   return (hcf);
}

查找分母的 LCM

要查找两个数字 a 和 b 的 LCM，我们可以使用以下公式 −

LCM(a,b) * HCF (a,b) = a*b
因此，LCM(a,b) = (a*b) / HCF(a,b)

现在，我们可以迭代地找到整个数组(两个以上的数字)的分子的 LCM。

用于查找分母 LCM 的 C++ 函数

//用于查找分母系列的 lcm 的函数
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);
}

• 步骤 1 - 初始化一对向量:vector<pair<int,int>>vec

• 步骤 2 - 在 vec

中输入分数

• 步骤 3 - ans -> find_hcf_of_fraction(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 程序，用于查找有理数(分数)数组的 HCF。

#include <bits/stdc++.h>
using namespace std;
//用于查找两个数字的 HCF 的函数
int HCF(int a, int b){
   if (a % b == 0)
      return b;
   else
      return (HCF(b, a % b));
}
//查找分子系列的HCF的函数
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);
   // 返回分子的 hcf
   return (hcf);
}
// 函数求分母系列的最小公倍数
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);
}
//获取答案的函数
vector<int> find_hcf_of_fraction(vector<pair<int,int>>v){
    //分子系列的 HCF
    int hcf_of_num = findHcf(v);
    //分母系列的 lcm
   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);
}
//主代码
int main(){
    int size = 4;
    vector<pair<int,int>>vec;
    //将分数插入向量
    vec.push_back({4,5});
    vec.push_back({10,12});
    vec.push_back({24,16});
    vec.push_back({22,13});
    //函数调用以计算分数的 HCF
    vector<int>ans;
    ans = find_hcf_of_fraction(vec);
    //打印答案
    cout << "给定分数数组的 HCF:";
    cout << "{" << ans[0] << ", " << ans[1] << "}"<< endl;
    return 0;
}

输出

对于输入 - [{4, 5}, {10, 12}, {24, 16}, {22, 13}]，上述 C++ 程序将产生以下输出 -

给定分数数组的 HCF:{2, 3120}

结论

本文讨论了寻找分数的 HCF 问题。本文涵盖的内容包括方法、伪代码和 C++ 程序。

相关文章

• 图中的团
• 无权图的应用、优点和缺点
• 在标记邻居的最短路径后查找图中所有剩余顶点
• 计算给定数字字符串连接 K 次后生成的字符串中 01 的子序列
• 查找字符串字母值的个位数和
• String 可以被视为关键字吗?
• 通过将辅音替换为最接近的元音或将辅音替换为最接近的元音来计算唯一字符串的数量
• 在给定的对中找出平均值刚好大于当前对的对的索引
• 斐波那契数列中每个元素的阶乘
• 斐波那契系数和斐波那契三角形