求两个正整数m和n的最大公约数

求两个正整数m和n的最大公约数
求两个正整数m和n的最大公约数

求两个正整数m和n的最大公约数
用辗转相除法

辗转相除法，没有具体数字不好说。

用短除法

求两个正整数的最大公约数的算法通常使用“辗转相除法”。设有两个正整数m、n，求它们的最大公约数的算法如下：
①若m＜n，则交换m和n（保证m大于n）。
②计算m/n的余数r。
③若r不等于0，则令m＝n、n＝r，转第②步继续执行；
否则，算法结束，n就是最大公约数。
下面就是用“辗转相除法'才出并返回m、n最大公约数的函数fmn（），请填写清单中缺...

全部展开

求两个正整数的最大公约数的算法通常使用“辗转相除法”。设有两个正整数m、n，求它们的最大公约数的算法如下：
①若m＜n，则交换m和n（保证m大于n）。
②计算m/n的余数r。
③若r不等于0，则令m＝n、n＝r，转第②步继续执行；
否则，算法结束，n就是最大公约数。
下面就是用“辗转相除法'才出并返回m、n最大公约数的函数fmn（），请填写清单中缺少的语句。
int fmn（ m, n）
int m， n；
｛ int r；
if（m＜n ）
{r＝m；m＝n；n＝r；}
if（n＝＝0）
return（m）；
do{_________________
if（r!= 0）
{ m＝n； n＝r；}
}while（r!=0）；
return（n）；
}
【分析】由于算法步骤已经给出，按照算法来理解程序就比较简单。函数体开始的单分支语
句是确保m值是大于n值的。接下来的单分支语句是确保算法中的除法“m／n”时的除数n不为0。注意，如果一开始的n就是O，则两个最大公约数就是m，此处利用返回语句返回的函数值就是m。接下来的do－while循环是实现算法步骤中的第②步和第③步的，显然该循环体中的第2条单分支语句是完成算法步骤中的第③步工作的，而空白处应该完成算法步骤中的第②步工作，即r等于m／n的余数。
【答案】r＝m％n；
【说明】求最大公约数和最小公倍数的算法是常用算法；但在教材中并没有给出，希望读者在
学有余力的情况下，能掌握这两个算法。
求两个正整数的最小公倍数的算法在教材中也没有给出，下面给出求最小公倍数的一种算法。设有两个正整数m、n，求它们的最小公倍数的算法如下：
①若m＜n，则交换m和n（保证m大于n）。
②令d＝m。
③若d能被n整除，则算法结束，d就是m和n的最小公倍数。
否则，令d＝d＋m，转第③步，继续执行。
实现算法的程序清单如下：
main（）
{ int m， n， d ；
scanf（"％d，％d"，＆m，＆n）；
if（m＜n）
{ d=m；m＝n；n＝d；}
if（n＝＝0）
d＝0；
else
{ d＝m；
while（d％n!=0）
d＋＝m；
}
printf（”％d＼n”，d）；
}

收起

辗转相除 祥见高等代数第一章

1.转转相除法：例如：求8251与6105的最大公约数
8251=6105*1+2146
6105=2146*2+1813
2146=1813*1+333
1813=333*5+148
333=148*2+37
148=37*4
所以最大公约数为37
2.更相减损术：例如：求98与63的最大公约...

全部展开

1.转转相除法：例如：求8251与6105的最大公约数
8251=6105*1+2146
6105=2146*2+1813
2146=1813*1+333
1813=333*5+148
333=148*2+37
148=37*4
所以最大公约数为37
2.更相减损术：例如：求98与63的最大公约数
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以最大公约数为7

收起

#include
#include
int x1(int m,int n)
{
return m%n==0?n:(n,m%n);
}
int x (int m,int n)
{
if(m<0)
m=-m;
if (n<0)
...

全部展开

#include
#include
int x1(int m,int n)
{
return m%n==0?n:(n,m%n);
}
int x (int m,int n)
{
if(m<0)
m=-m;
if (n<0)
n=-n;
return n==0?m:x1(m,n);
}
int main()
{
int m,n;
printf("请输入m,n：");
scanf("%d%d",&m, &n);
printf("最大公约数是?%d\n",x(m,n));
return 0;
}

收起