首页 > 综合动态 >

辗转相除法c语言代码函数(辗转相除法c语言)

发布时间:2024-06-06 12:34:55来源:

哈喽,大家好~~~我是小编田甜,关于辗转相除法c语言代码函数,辗转相除法c语言这个很多人还不知道,那么现在让田甜带着大家一起来看看吧!

1、用辗转相除法(即欧几里得算法)求两个正整数的最大公约数。

2、 解析: 设两个数m,n,假设m>=n,用m除以n,求得余数q。

3、若q为0,则m为最大公约数;若q不等于0,则进行如下迭代: m=n,n=q,即原除数变为新的被除数,原余数变为新的除数重复算法,直到余数为0为止。

4、余数为0时的除数n,即为原始m、n的最大公约数。

5、 迭代初值:m,n的原始值; 迭代过程:q=m%n; m=n; n=q; 迭代条件:q!=0 例如:m=8;n=6 q=m%n(8%6==2) m=n(m==6) n=q(n==2) 因为:(q==2)!=0,重复算法: q=m%n(6%2==0) m=n(m==2)余数为0时的除数n为最大公约数,n值赋给了m,所以输出m的值 n=q(n==0) 因为:q==0 所以最大公约数为m的值 源程序: #include void main() { int m,n,q,a,b; printf("Enter two integers:"); scanf("%d%d",&a,&b); m=a; n=b; if(n>m) { int z; z=m;m=n;n=z;//执行算法前保证m的值比n的值大 } do { q=m%n; m=n; n=q; }while(q!=0); printf("The greatest common divisor of"); printf("%d,%d is %d",a,b,m); } 希望对你有所帮助!。

本文分享完毕,希望对大家有所帮助哦。

免责声明:本文为转载,非本网原创内容,不代表本网观点。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。