求最大公约，最小公倍算法，小弟驽钝，望指教。(80分)

  • 主题发起人 主题发起人 gxlnew
  • 开始时间 开始时间
G

gxlnew

Unregistered / Unconfirmed
GUEST, unregistred user!
求最大公约，最小公倍算法，小弟驽钝，望指教。
 
求最小公倍数一般用大数翻番法，
即将大数不断自加，直到能整除小数为止

求最大公约数嘛，
把小数不断减一，直到大数，小数都能整除为止

如果数字多于两个，则两两计算，可得结果
 
最大公约数：
辗转相减法：
比如 12 、32：
大的减小的： 32-12=20
从32、12中选一个小的：12 ，来和 20 计算
20-12=8 剩下 12和8
12-8=4 （4是12和8的...）所以4就是了
 
最小功倍数：
比如 12 、32：
刚才找到了他们的最大公约数是4

12x(32/4（最大公约数是）)=96

或者

32x(12/4（最大公约数是）)=96

 
最大公约数递推程序
Program GCD
var
x,y: integer;
begin
read(x,y);
while x<>y do
begin
while x>y do x:=x-y;
while Y<x do Y:=Y-x;
end;
writeln(y)
end;

最小公倍数自然就得到了。
 
呵呵，被吃了……

最大公约数递推程序
Program GCD
var
x,y: integer;
begin
read(x,y);
while x&amp;lt;>y do
begin
while x>y do x:=x-y;
while Y&amp;lt;x do Y:=Y-x;
end;
writeln(y)
end;

最小公倍数自然就得到了。
 
怎么回事？我的发言只有一半？
 
呵呵，被吃了……

&amp;lt
被当作HTML语法
 
原来如此。你怎么知道我写的后面是什么东西的？你看得到吗？
 
呵呵，右键，查看源文件……
 
哦，我倒没想到。Thank U.
 
最大公约数的算法叫辗转相除法，
to pipi:
找最小公倍数不能那么找，如果溢出了怎么办？
 
同wrench.
BTW,wrench,"四川"那边的分还没给我呢! :-p


beta
 
如果真正的最小公倍数是能用你的数据类型表示的就不会溢出

再说最小工倍数就是 一个数 * （另一个数 / 他们的最大公约数）
 
我用C，程序如下：
main()
{int a,b,num1,num2,temp;
scanf("%d,%d",&amp;num1,num2);
if (num1<num2)
{temp=num1;
num1=num2;
num2=temp;
}
a=num1,b=num2;
while (b!=0)
{temp=a%b;
a=b;
b=temp;
}
printf("%d/n",a);
printf("%d",b);
}
 
谢谢各位！尤其感谢wjiachun
 
您必须登录或注册才可回复。

Similar threads

I
最小公倍数和最大公约数!
回复
0
查看
420
import
I
D
[原]希望OrangeUI有个好的开始
回复
0
查看
1K
DelphiTeacher的专栏
D
I
最大约数算法
回复
0
查看
405
import
I
S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
后退
顶部