GCD

GCD(最大公约数):

欧几里得算法据说是最早的算法,用于计算最大公约数,也是数论的基础算法之一。
这里给出使用欧几里得算法求最大公约数的递归和非递归的程序,同时给出穷举法求最大公约数的程序。
从计算时间上看,递推法计算速度最快。
程序中包含条件编译语句用于统计分析计算复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
代码:

递归算法:

ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
循环算法:
/* 迭代法(递推法):欧几里得算法,计算最大公约数 */
int gcd(int m, int n)
{
while(m)
{
int c = n % m;
n = m;
m = c;
}
return n;
}
---------------- The End ----------------
0%