gcd(a,b)，求两个数最大公约数
5星 · 超过95%的资源 需积分: 50 182 浏览量
2011-03-30
00:18:41
上传
评论 2
收藏 28KB DOC 举报 
gcd （greatest common divisor）求两个数的最大公约数
几点补充：
1、来自王敏妙的解法：
var
m,n,t:integer;
begin
readln(m,n);
t:=n;
while (m mod t<>0)or(n mod t<>0) do dec(t);
writeln(t);
end.
2、欧几里得算法 P34（必修 3）
辗转相除法，这种算法是由欧几里得在公元前 300 年左右首先提出的，因而又叫《欧几里
得算法》
分析与证明：用辗转相除法求 8251 和 6105 的最大公约数，我们可以考虑用两数中较大的
数除以较小的数，求得商和余数：
8251＝6105*1+2146（所求的最大公约数要被 6105 整除，当然会被 6105*k 整除，
与此同时也必须被其余数 2146 整除，否则就不是公约数！）
由此可得，6105 与 2146 的公约数也是 8251 和 6105 的公约数！
借助于两个等价问题进行递推，但问题规模上起到了很大变化！
如：gcd(m,n) gcd(n,m mod n)
在递推程序设计过程中，问题规模快速变小，直到有解，m mod n=0；
因而，程序重点考虑：是问题边界处理，用循环结构实现时，即循环结束条件的设置！
var
m,n,t:integer;
begin
readln(m,n);
while (m mod n<>0) do
begin
t:=m;
m:=n;
n:=t mod n;
end;
writeln(n);
end.
分析并比较以上两个算法的优劣！时间复杂度 O（n）与○（ ）。
其中：O（k）<=○（ ）
评论5
最新资源