我正在编写一个混合数字类,并需要一个快速简单的“最大公约数”功能。有人能给我提供代码或代码链接吗?
我正在编写一个混合数字类,并需要一个快速简单的“最大公约数”功能。有人能给我提供代码或代码链接吗?
我正在编写一个混合数字类,并需要一个快速简单的“最大公约数”功能。有人能给我提供代码或代码链接吗?
我正在编写一个混合数字类,并需要一个快速简单的“最大公约数”功能。有人能给我提供代码或代码链接吗?
libstdc++算法库有一个隐藏的gcd函数(我正在使用g++ 4.6.3)。
#include <iostream>
#include <algorithm>
int main()
{
std::cout << std::__gcd(100,24); // print 4
return 0;
}
欢迎您 :)
更新:正如@chema989所指出的,C++17中有<numeric>
头文件提供了std::gcd()
函数。
我倾向于投票关闭此问题 - 看起来很难相信找不到一个实现,但谁知道呢。
template <typename Number>
Number GCD(Number u, Number v) {
while (v != 0) {
Number r = u % v;
u = v;
v = r;
}
return u;
}
在C++17或更新版本中,您只需包含#include <numeric>
,然后使用std::gcd
(如果您关心最大公约数,那么很可能您也会对新增的std::lcm
感兴趣)。
一个快速的递归版本:
unsigned int gcd (unsigned int n1, unsigned int n2) {
return (n2 == 0) ? n1 : gcd (n2, n1 % n2);
}
或者,如果您非常反对递归,可以使用其等价的迭代版本(a):
unsigned int gcd (unsigned int n1, unsigned int n2) {
unsigned int tmp;
while (n2 != 0) {
tmp = n1;
n1 = n2;
n2 = tmp % n2;
}
return n1;
}
只需用自己的数据类型、零比较、赋值和取模方法(如果您正在使用一些非基本类型,例如bignum
类),就可以替换此函数。
这个函数实际上来自于我以前为屏幕尺寸计算整数宽高比的 回答中,但最初的来源是我很久以前学过的欧几里得算法,详细资料可在 维基百科 上查看。
(a) 一些递归解决方案的问题在于它们接近答案的速度如此之慢,以至于你在到达目的地之前就会耗尽堆栈空间,例如下面这个极其糟糕的伪代码:
def sum (a:unsigned, b:unsigned):
if b == 0: return a
return sum (a + 1, b - 1)
像 sum(1, 1000000000)
这样的计算会在使用超过数十亿个栈帧时非常昂贵。递归的理想用例是二分查找,每次迭代将解决方案空间减少一半。最大公约数也是这样,其解决方案空间迅速缩小,因此对于巨大的栈使用的担忧是没有必要的。
template<class Integral>
来替换 int
,在函数前加上 constexpr
关键字,这样你就有了一个漂亮的编译时/运行时通用函数。 - authchirreturn n1
吗?此时 n2 的定义总是为零。 - Jim Blackler如果你使用C++17,你可以使用在头文件<numeric>
中定义的std::gcd
:
auto res = std::gcd(10, 20);
欧几里得算法在C语言中编写起来非常简单。
int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}