如何写一个小优雅的gcd功能？ [英] How to write a small graceful gcd function?

问题描述

我的小功能有效，但我有一些问题。我想

听听你如何实现？


1.该函数不检查参数x是大于还是小于

参数y。


2.使用unsigned int或unsigned long作为

参数x和y的类型是否更好？此更改可能会删除if语句。


仍然欢迎更多评论。


/ *最大公约数，简称GCD两个正整数

可以用Euclid的除法算法计算。让给定数字

为a和b，a> = b。 Euclid的除法算法有以下步骤：
步骤：

1.计算除以b的余数c。

2.如果余数c为零，b是最大公约数。

3.如果c不为零，则用b和b替换余数为c。返回步骤（1）。

http://www.cs.mtu.edu/~shene/COURSES...hap04/gcd.html * /


/ *通过Euclid的算法计算正整数x和
$ b $的GCD（最大公约数）。返回GCD，或-1表示失败。 - jhl，

2006年7月* /


int gcd（int x，int y）{

if（x 0& ;& y 0）{

while（x％y）{

y = x + y;

x = y - x;

y =（y - x）％x;

}

}否则{

y = -1; / *输入无效* /

}

返回y;

}


lovecreatesbeauty

My small function works, but I have some questions. And I want to
listen to you on How it is implemented?

1. The function does not check if parameter x is larger or smaller than
parameter y.

2. Is it better to use unsigned int or unsigned long as the type of
parameters x and y? This change may remove the if statement.

More comments are still welcome.

/*The Greatest Common Divisor, GCD for short, of two positive integers
can be computed with Euclid''s division algorithm. Let the given numbers
be a and b, a >= b. Euclid''s division algorithm has the following
steps:
1. Compute the remainder c of dividing a by b.
2. If the remainder c is zero, b is the greatest common divisor.
3. If c is not zero, replace a with b and b with the remainder c. Go
back to step (1).

http://www.cs.mtu.edu/~shene/COURSES...hap04/gcd.html */

/*computes the GCD (Greatest Common Divisor) of positive integers x and
y with Euclid''s algorithm. return the GCD, or -1 for failure. - jhl,
Jul 2006*/

int gcd(int x, int y){
if (x 0 && y 0){
while (x % y){
y = x + y;
x = y - x;
y = (y - x) % x;
}
} else {
y = -1; /*input invalid*/
}
return y;
}

lovecreatesbeauty

推荐答案

/ *最大公约数，GCD for简而言之，两个正整数

可以用Euclid的除法算法计算。让给定数字

为a和b，a> = b。 Euclid的除法算法有以下步骤：
步骤：

1.计算除以b的余数c。

2.如果余数c为零，b是最大公约数。

3.如果c不为零，则用b和b替换余数为c。去

回到步骤（1）。

/*The Greatest Common Divisor, GCD for short, of two positive integers
can be computed with Euclid''s division algorithm. Let the given numbers
be a and b, a >= b. Euclid''s division algorithm has the following
steps:
1. Compute the remainder c of dividing a by b.
2. If the remainder c is zero, b is the greatest common divisor.
3. If c is not zero, replace a with b and b with the remainder c. Go
back to step (1).

int gcd（unsigned int a，unsigned int b）

{

unsigned int c;


if（！a&&！b）

返回-1;


if（ab）

{

c = a;

a = b;

b = c;

}

while（（c = a％b）0）

{

a = b;

b = c;

}

返回b;

}


类似的代码在fortran也可用于链接你给了但是我

无法理解你为什么这样做：

int gcd (unsigned int a, unsigned int b)
{
unsigned int c;

if ( !a && !b )
return -1;

if (a b)
{
c = a;
a = b;
b = c;
}
while( (c=a%b) 0 )
{
a = b;
b = c;
}
return b;
}

Similar code in fortran is also available on the link u gave but I
could not understand why you have done this:

y = x + y;

x = y - x;

y =（y - x）％x;

y = x + y;
x = y - x;
y = (y - x) % x;

问候，


Nabeel Shaheen


lovecreatesbeauty写道：

Regards,

Nabeel Shaheen

lovecreatesbeauty wrote:

我的小函数有效，但我有一些问题。我想

听听你如何实现？


1.该函数不检查参数x是大于还是小于

参数y。


2.使用unsigned int或unsigned long作为

参数x和y的类型是否更好？此更改可能会删除if语句。


仍然欢迎更多评论。


/ *最大公约数，简称GCD两个正整数

可以用Euclid的除法算法计算。让给定数字

为a和b，a> = b。 Euclid的除法算法有以下步骤：
步骤：

1.计算除以b的余数c。

2.如果余数c为零，b是最大公约数。

3.如果c不为零，则用b和b替换余数为c。返回步骤（1）。

http://www.cs.mtu.edu/~shene/COURSES...hap04/gcd.html * /


/ *通过Euclid的算法计算正整数x和
$ b $的GCD（最大公约数）。返回GCD，或-1表示失败。 - jhl，

2006年7月* /


int gcd（int x，int y）{

if（x 0& ;& y 0）{

while（x％y）{

y = x + y;

x = y - x;

y =（y - x）％x;

}

}否则{

y = -1; / *输入无效* /

}

返回y;

}


lovecreatesbeauty

My small function works, but I have some questions. And I want to
listen to you on How it is implemented?

1. The function does not check if parameter x is larger or smaller than
parameter y.

2. Is it better to use unsigned int or unsigned long as the type of
parameters x and y? This change may remove the if statement.

More comments are still welcome.

/*The Greatest Common Divisor, GCD for short, of two positive integers
can be computed with Euclid''s division algorithm. Let the given numbers
be a and b, a >= b. Euclid''s division algorithm has the following
steps:
1. Compute the remainder c of dividing a by b.
2. If the remainder c is zero, b is the greatest common divisor.
3. If c is not zero, replace a with b and b with the remainder c. Go
back to step (1).

http://www.cs.mtu.edu/~shene/COURSES...hap04/gcd.html */

/*computes the GCD (Greatest Common Divisor) of positive integers x and
y with Euclid''s algorithm. return the GCD, or -1 for failure. - jhl,
Jul 2006*/

int gcd(int x, int y){
if (x 0 && y 0){
while (x % y){
y = x + y;
x = y - x;
y = (y - x) % x;
}
} else {
y = -1; /*input invalid*/
}
return y;
}

lovecreatesbeauty

lovecreatesbeauty写道：

lovecreatesbeauty wrote:

我的小功能有效，但我有一些问题。我想

听听你如何实现？


1.该函数不检查参数x是大于还是小于

参数y。


2.使用unsigned int或unsigned long作为

参数x和y的类型是否更好？此更改可能会删除if语句。


仍然欢迎更多评论。


/ *最大公约数，简称GCD两个正整数

可以用Euclid的除法算法计算。让给定数字

为a和b，a> = b。 Euclid的除法算法有以下步骤：
步骤：

1.计算除以b的余数c。

2.如果余数c为零，b是最大公约数。

3.如果c不为零，则用b和b替换余数为c。返回步骤（1）。

http://www.cs.mtu.edu/~shene/COURSES...hap04/gcd.html * /


/ *通过Euclid的算法计算正整数x和
$ b $的GCD（最大公约数）。返回GCD，或-1表示失败。 - jhl，

2006年7月* /


int gcd（int x，int y）{

if（x 0& ;& y 0）{

while（x％y）{

y = x + y;

x = y - x;

y =（y - x）％x;

}

}否则{

y = -1; / *输入无效* /

}

返回y;

}


lovecreatesbeauty

My small function works, but I have some questions. And I want to
listen to you on How it is implemented?

1. The function does not check if parameter x is larger or smaller than
parameter y.

2. Is it better to use unsigned int or unsigned long as the type of
parameters x and y? This change may remove the if statement.

More comments are still welcome.

/*The Greatest Common Divisor, GCD for short, of two positive integers
can be computed with Euclid''s division algorithm. Let the given numbers
be a and b, a >= b. Euclid''s division algorithm has the following
steps:
1. Compute the remainder c of dividing a by b.
2. If the remainder c is zero, b is the greatest common divisor.
3. If c is not zero, replace a with b and b with the remainder c. Go
back to step (1).

http://www.cs.mtu.edu/~shene/COURSES...hap04/gcd.html */

/*computes the GCD (Greatest Common Divisor) of positive integers x and
y with Euclid''s algorithm. return the GCD, or -1 for failure. - jhl,
Jul 2006*/

int gcd(int x, int y){
if (x 0 && y 0){
while (x % y){
y = x + y;
x = y - x;
y = (y - x) % x;
}
} else {
y = -1; /*input invalid*/
}
return y;
}

lovecreatesbeauty

int gcd（int m，int n）//递归

{

if（n == 0） {return m; }

else

{int answer = gcd（n，m％n）;

返回答案; }

}


-

Julian V. Noble

名誉教授物理学

弗吉尼亚大学

int gcd( int m, int n ) // recursive
{
if(n==0) { return m; }
else
{ int answer = gcd(n,m%n);
return answer; }
}


--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia

" Julian V. Noble" < jv*@virginia.eduwrites：

[...]

"Julian V. Noble" <jv*@virginia.eduwrites:
[...]

int gcd（int m，int n）//递归

{

if（n == 0）{return m; }

else

{int answer = gcd（n，m％n）;

返回答案; }

}

int gcd( int m, int n ) // recursive
{
if(n==0) { return m; }
else
{ int answer = gcd(n,m%n);
return answer; }
}

临时是不必要的，格式化只是奇数。这是'

我是怎么写的：


int gcd（int m，int n）

{

if（n == 0）{

返回m;

}

else {

返回gcd（n，m％n）;

}

}


-

Keith Thompson（The_Other_Keith） ks***@mib.org < http://www.ghoti.net/ ~kst>

圣地亚哥超级计算机中心< *< http://users.sdsc.edu/~kst>

我们必须做点什么。这是事情。因此，我们必须这样做。

The temporary is unnecessary, and the formatting is just odd. Here''s
how I''d write it:

int gcd(int m, int n)
{
if (n == 0) {
return m;
}
else {
return gcd(n, m % n);
}
}

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

这篇关于如何写一个小优雅的gcd功能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！