求两个正整数的最大公约数
思路：这是一个很基本的问题，最常见的就是两种方法，辗转相除法和辗转相减法。通式分别为 f(x, y) = f(y, x%y), f(x, y) = f(y, x – y) (x >=y > 0)。根据通式写出算法不难，这里就不给出了。这里给出《编程之美》上的算法，主要是为了减少迭代的次数。
对于x和y，如果y = k * y1, x= k * x1，那么f(x, y) = k * f(x1, y1)。另外，如果x = p * x1，假设p为素数，并且y % p != 0，那么f(x, y) = f(p * x1, y) = f(x1, y)。取p = 2。
参考代码：
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
//函数功能: 求最大公约数
//函数参数: x,y为两个数
//返回值: 最大公约数
int gcd_solution1(int x, int y)
{
if(y == 0)
return x;
else if(x < y)
return gcd_solution1(y, x);
else
{
if(x&1) //x是奇数
{
if(y&1) //y是奇数
return gcd_solution1(y, x-y);
else //y是偶数
return gcd_solution1(x, y>>1);
}
else //x是偶数
{
if(y&1) //y是奇数
return gcd_solution1(x>>1, y);
else //y是偶数
return gcd_solution1(x>>1, y>>1) << 1;
}
}
}
|
求最小公倍数：
最常用的是辗转相除法，有两整数a和b：
① a%b得余数c
② 若c=0，则b即为两数的最大公约数
③ 若c≠0，则a=b，b=c，再回去执行①
下面非递归版本：
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
int gcd_solution2(int x, int y)
{
int result = 1;
while(y)
{
int t = x;
if(x&1)
{
if(y&1)
{
x = y;
y = t % y;
}
else
y >>= 1;
}
else
{
if(y&1)
x >>= 1;
else
{
x >>= 1;
y >>= 1;
result <<= 1;
}
}
}
return result * x;
}
|
相关文章
猜你喜欢
- 个人网站搭建：如何挑选具有弹性扩展能力的服务器？ 2025-06-10
- 个人服务器网站搭建：如何选择适合自己的建站程序或框架？ 2025-06-10
- 64M VPS建站：能否支持高流量网站运行？ 2025-06-10
- 64M VPS建站：怎样选择合适的域名和SSL证书？ 2025-06-10
- 64M VPS建站：怎样优化以提高网站加载速度？ 2025-06-10
