最高的共同因素 [英] Highest Common Factor
问题描述
任何人都想帮我写一个有效的算法来获得最高的
公因数和最低公倍数？这就是我到目前为止......
警告：我没有详细介绍下面的代码，所以可能会有一些细微的b $ ba臭虫潜伏在某个地方。
无符号HCF（无符号const a，无符号const b）
{
无符号更大，更小;
注册未签名的hcf;
如果（a> b）更大= a，更小= b;
else更大= b，更小= a;
if（！（更小％更小））返回更小;
hcf = smaller-1;
while（a％hcf || b％hcf） - hcf;
返回hcf;
}
任何提高效率的想法？
这就是我最低的共同点：
无符号LCM（无符号const a，无符号const b）
{
无符号大，小，最大;
注册无符号lcm;
如果（a> b）更大= a，更小= b;
其他更大= b，较小= a;
if（ ！（更小％））返回更大;
max =（无符号）-1 - 更大;
if（更大最大值）返回0;
lcm =更大<< 1;
while（lcm％a || lcm％b）
{
if（lcm max）返回0;
lcm + =更大;
}
返回lcm;
}
任何提高效率的想法？
< br $>
-
Frederick Gotham
Anyone want to give me a hand to write efficient algorithms for Highest
Common Factor and Lowest Common Multiple? This is what I have so far...
Caveat: I haven''t gone over the following code in detail, so there might be
a subtle bug lurking somewhere.
unsigned HCF(unsigned const a, unsigned const b)
{
unsigned bigger,smaller;
register unsigned hcf;
if (a>b) bigger=a,smaller=b;
else bigger=b,smaller=a;
if ( !(bigger%smaller) ) return smaller;
hcf = smaller-1;
while (a%hcf || b%hcf) --hcf;
return hcf;
}
Any ideas to make it more efficient?
Here''s what I''ve got for Lowest Common Multiple:
unsigned LCM(unsigned const a,unsigned const b)
{
unsigned bigger,smaller,max;
register unsigned lcm;
if (a>b) bigger=a,smaller=b;
else bigger=b,smaller=a;
if ( !(bigger%smaller) ) return bigger;
max = (unsigned)-1 - bigger;
if (bigger max) return 0;
lcm = bigger<<1;
while(lcm%a || lcm%b)
{
if (lcm max) return 0;
lcm += bigger;
}
return lcm;
}
Any ideas to make it more efficient?
--
Frederick Gotham
推荐答案
10月23日，11： 01 pm，Frederick Gotham< fgotha ... @ SPAM.comwrote：
On Oct 23, 11:01 pm, Frederick Gotham <fgotha...@SPAM.comwrote:
任何人都想帮我写一篇高效的算法来获取最高价格
公因数和最低公倍数？这就是我到目前为止......
警告：我没有详细介绍下面的代码，所以可能会有一些细微的b $ ba臭虫潜伏在某个地方。
无符号HCF（无符号const a，无符号const b）
{
无符号更大，更小;
注册未签名的hcf;
如果（a> b）更大= a，更小= b;
else更大= b，更小= a;
if（！（更小％更小））返回更小;
hcf = smaller-1;
while（a％hcf || b％hcf） - hcf;
返回hcf;
}任何提高效率的想法？
这就是我最低的共同点数：
unsigned LCM（unsigned const a，unsigned const b）
{
无符号更大，更小，最大;
寄存器unsigned lcm;
如果（a> b）更大= a，更小= b;
其他更大= b，更小= a;
如果（！（更大％更小））返回更大;
max =（无符号）-1 - 更大;
if（更大的最大值）返回0;
lcm =更大<< 1;
而（ lcm％a || lcm％b）
{
if（lcm max）返回0;
lcm + =更大;
}
返回lcm;
}任何提高效率的想法？
Anyone want to give me a hand to write efficient algorithms for Highest
Common Factor and Lowest Common Multiple? This is what I have so far...
Caveat: I haven''t gone over the following code in detail, so there might be
a subtle bug lurking somewhere.
unsigned HCF(unsigned const a, unsigned const b)
{
unsigned bigger,smaller;
register unsigned hcf;
if (a>b) bigger=a,smaller=b;
else bigger=b,smaller=a;
if ( !(bigger%smaller) ) return smaller;
hcf = smaller-1;
while (a%hcf || b%hcf) --hcf;
return hcf;
}Any ideas to make it more efficient?
Here''s what I''ve got for Lowest Common Multiple:
unsigned LCM(unsigned const a,unsigned const b)
{
unsigned bigger,smaller,max;
register unsigned lcm;
if (a>b) bigger=a,smaller=b;
else bigger=b,smaller=a;
if ( !(bigger%smaller) ) return bigger;
max = (unsigned)-1 - bigger;
if (bigger max) return 0;
lcm = bigger<<1;
while(lcm%a || lcm%b)
{
if (lcm max) return 0;
lcm += bigger;
}
return lcm;
}Any ideas to make it more efficient?
对于hcf（AKA gcd，最大公约数），请阅读Euclid的
算法（ http://en.wikipedia.org/wiki/Euclidean_algorithm) 。
-
Nachch
For hcf (AKA gcd, greatest common divisor), read about Euclid''s
algorithm (http://en.wikipedia.org/wiki/Euclidean_algorithm).
--
Nachch
Frederick Gotham写道：
Frederick Gotham wrote:
任何人都想帮我写一个有效的算法来获得最高的
公因数和最低公倍数？这就是我到目前为止......
警告：我没有详细介绍下面的代码，所以可能会有一些细微的b $ ba在某处潜伏着的小虫。
Anyone want to give me a hand to write efficient algorithms for Highest
Common Factor and Lowest Common Multiple? This is what I have so far...
Caveat: I haven''t gone over the following code in detail, so there might be
a subtle bug lurking somewhere.
我再也无法访问C编译器，但是当我需要时，我使用了
Knuth的二进制算法函数。
无符号HCF（无符号a，无符号b）
{
int za，zb，zr;
if（a == 0 || b == 0）
返回a + b;
za = zb = 0;
而（（a& 1）== 0）
{
a>> = 1; ++ za;
}
while（（b& 1）== 0）
{
b >> = 1; ++ zb;
}
zr = za zb？ zb：za;
/ *奇数两个奇数的HCF（Knuth）* /
而（a！= b）
{
if（ab）
{
a - = b;
do
a>> = 1;
while（（a& 1）== 0）;
}
else
{
b - = a;
do
b>> = 1;
while（（b& 1）== 0）;
}
} / * end Knuth * /
while（zr）
{
a<< = 1; - zr;
}
返回a;
}
-
I haven''t got access to a C compiler anymore, but I used
Knuth''s binary algorithm when I needed this function.
unsigned HCF (unsigned a, unsigned b)
{
int za, zb, zr;
if (a == 0 || b == 0)
return a + b;
za = zb = 0;
while ((a & 1) == 0)
{
a >>= 1; ++za;
}
while ((b & 1) == 0)
{
b >>= 1; ++zb;
}
zr = za zb ? zb : za;
/* odd HCF of two odd numbers (Knuth) */
while (a != b)
{
if (a b)
{
a -= b;
do
a >>= 1;
while ((a & 1) == 0);
}
else
{
b -= a;
do
b >>= 1;
while ((b & 1) == 0);
}
} /* end Knuth */
while (zr)
{
a <<= 1; --zr;
}
return a;
}
--
na****@gmail.com 写道：
10月23日晚上11点01分，Frederick Gotham< fgotha ... @ SPAM.comwrote：
On Oct 23, 11:01 pm, Frederick Gotham <fgotha...@SPAM.comwrote:
任何人都想帮我写一个有效的算法来获得最高的
公因数和最低公倍数？
Anyone want to give me a hand to write efficient algorithms for Highest
Common Factor and Lowest Common Multiple?
对于hcf（AKA gcd，最大公约数），请阅读Euclid的
算法（ http://en.wikipedia.org/wiki/Euclidean_algorithm) 。
事实上，欧几里得的算法似乎是最好的方法，除非你想要b / b
。请注意，你可以稍微修改算法
，而不是计算一个％b（它将在
0到b-1的范围内），你允许使用负数来结果在
范围-b / 2到b / 2。这个保证b每个时间大小减半，所以在运行时间上设置一个日志。
对于lcm，请注意hcf * lcm = product这两个数字，所以你可以
重新使用hcf例程。
希望这会有所帮助。
保罗。
Indeed, Euclid''s algorithm seems the best way to go, unless you want to
try factorising the numbers. Note that you can modify the algorithm
slightly whereby instead of calculating a%b (which will be in the range
0 to b-1 inclusive) you allow negative numbers to give a result in the
range -b/2 to b/2. This guarentees that b is halving in magnitude each
time so places a log bound on the running time.
For lcm, note that hcf * lcm = product of the two numbers, so you can
re-use the hcf routine.
Hope this helps.
Paul.
这篇关于最高的共同因素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
