解题思路:
对于求两个整数的最小公倍数采用辗转相除法:
设两数为a、b(b<a),用gcd(a,b)表示a,b的最大公约数,r=a mod b 为a除以b以后的余数,k为a除以b的商,即a÷b=k.......r。辗转相除法即是要证明gcd(a,b)=gcd(b,r)。
第一步:令c=gcd(a,b),则设a=mc,b=nc
第二步:根据前提可知r =a-kb=mc-knc=(m-kn)c
第三步:根据第二步结果可知c也是r的因数
第四步:可以断定m-kn与n互质【否则,可设m-kn=xd,n=yd,(d>1),则m=kn+xd=kyd+xd=(ky+x)d,则a=mc=(ky+x)cd,b=nc=ycd,故a与b最大公约数成为cd,而非c,与前面结论矛盾】
从而可知gcd(b,r)=c,继而gcd(a,b)=gcd(b,r)。
注意事项:
参考代码:
#include<stdio.h>
int gongyue(int a,int b);
int gongbei(int a,int b);
int main()
{
int m,n;
scanf("%d%d",&m,&n);
printf("%d\n%d",gongyue(m,n),gongbei(m,n));
return 0;
}
int gongyue(int a,int b)
{
if(b==0) return a;
else return gongyue(b,a%b);
}
int gongbei(int a,int b)
{
int i=1;
while((a*i)%b!=0) i++;
return a*i;
}
0.0分
2 人评分
简单的a+b (C语言代码)浏览:537 |
C语言程序设计教程(第三版)课后习题6.11 (C++代码)(有个库函数叫sqrt)浏览:845 |
母牛的故事 (C语言代码)浏览:738 |
C二级辅导-计负均正 (C语言代码)浏览:508 |
永远的丰碑 (C语言代码)浏览:653 |
printf基础练习2 (C语言代码)浏览:591 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:411 |
A+B for Input-Output Practice (C++代码)浏览:605 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:501 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:1030 |