题目

以下函数fun用于求两个整数a和b的最大公约数.填空
以下函数fun用于求两个整数a和b的最大公约数.
fun(a,b)
int a,b;
{int i,j,m,n;
if(a>b)
{m=a;a=b;_____;}
i=a;j=b;
while((n=______)!=0)
{j=i;i=_____;}
return(i);
}
在线坐等回复

提问时间：2021-10-14

答案

这种方法是数学里面的辗转相除法.
具体思路为：
假设a=15,b=9 那么r=a%b 则r=15%9=6,由于余数不为0,
所有9不是最大公约数
现在令a=b,b=r,那么a=9,b=6,继续求r=a%b则r=9%6=3 由于余数不为0,
所以6不是最大公约数
现在令a=b,b=r,那么a=6,b=3,继续求r=a%b,则r=6%3=0.
余数为0,循环结束,b就是最大公约数,即15和9的最大公约数为3
所以第一个空是 b=m.if的功能是a>b的话,交换ab
第二个空是n=j%i实现求余数
第三个空是i=n,余数不为0的话所做循环操作.