本文目录一览：
- 1、C语言辗转相除法
- 2、C语言辗转相除法问题
- 3、c语言编程,利用辗转相除法求公约数
- 4、c语言辗转相除法
- 5、c语言中，用辗转相除法计算两个数的最大公约数的具体方法是怎样的？
- 6、辗转相除法c语言代码
C语言辗转相除法
例如用辗转相除法求a b 最大公约数（a b谁大谁小无所谓）：
int GCD( int a , int b )
{
int n=a%b;
whie(n != 0) //即： while(n)
{
a = b;
b = n;
n = a % b;
}
return b; //注意这里返回的是b 不是n
}
C语言辗转相除法问题
#include stdio.h
int fun(int a,int b) /* 2个数的公约数 */
{
int t;
while(b)
{
t = a%b;
a = b;
b = t;
}
return a;
}
int main()
{
int a[100];
int n;
int i;
int res;
scanf(“%d”,n); /* 先输入数的总数n */
if(n 2)
{
printf(“n不能小于2\n”);
return 0;
}
for(i=0;in;i++) /* 输入n个数 */
scanf(“%d”,a[i]);
res = fun(a[0],a[1]);
for(i=2;in;i++)
res = fun(res,a[i]);
printf(“%d\n”,res);
return 0;
}
欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。
其计算原理依赖于下面的定理：
定理：gcd(a,b) = gcd(b,a mod b) (ab 且a mod b 不为0)
证明：a可以表示成a = kb + r，则r = a mod b
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
⒈ 若 r 是 a ÷ b 的余数，且r不为0， 则
gcd(a,b) = gcd(b,r)
⒉ a 和其倍数之最大公因子为 a。
另一种写法是：
⒈ 令r为a/b所得余数（0≤r
若 r= 0，算法结束；b 即为答案。
⒉ 互换：置 a←b，b←r，并返回第一步。
c语言编程,利用辗转相除法求公约数
辗转相除法， 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。
其原理如下：
设两数为a、b(ba)，用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 (d1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数成为cd，而非c，与前面结论矛盾】
从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。
证毕。
以上步骤的操作是建立在刚开始时r!=0的基础之上的。即m与n亦互质。
按照其规则，C语言实现如下：
int GCD(int a,int b)
{return b==0？a:GCD(b,a%b)；}
c语言辗转相除法
按照你的改了一下
#include stdio.h
int gcd(int x,int y)
{
int i;
int max,min;
(xy)?(max=x,min=y):(max=y,min=x);
if(i=max%min!=0)
do{
i=min;
min=max%min;
max=i;
}while(min!=0);
return max;
}
int main()
{
int a,b;
scanf(“%d%d”,a,b);
printf(“%d\n”,gcd(a,b));
return 0;
}
再给你一个精简版，二者实质是一样的
#include stdio.h
int gcd(int x,int y)
{
if(y==0) return x;
return gcd(y,x%y);
}
int main()
{
int a,b;
scanf(“%d%d”,a,b);
printf(“%d\n”,gcd(a,b));
return 0;
}
c语言中，用辗转相除法计算两个数的最大公约数的具体方法是怎样的？
#include stdio.h
int gcd(int a, int b) {
int r;
do {
r = a % b;
a = b;
b = r;
} while (r);
return a;
}
int main(void) {
int a, b;
printf(“Input two integers: \n”);
scanf(“%d%d”, a, b);
printf(“The greatest common divisor is: %d\n”, gcd(a, b));
return 0;
}
原理：
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的余数，则
gcd(a,b) = gcd(b,r)
2. a 和其倍数之最大公因子为 a。
另一种写法是：
1. a ÷ b，令r为所得余数（0≤rb）
若 r = 0，算法结束；b 即为答案。
2. 互换：置 a←b，b←r，并返回第一步
辗转相除法c语言代码
辗转相除法用来求两个数的最大公约数，代码如下：
#include stdio.h
#include stdlib.h
int main()
{
int a, b,r;
scanf(“%d %d”, a, b);
while(b!=0)//当其中一个数为0，另一个数就是两数的最大公约数
{
r = a%b;
a = b;
b = r;
}
printf(“Greatest Common Divisor: %d\n”, a);
system(“pause”);
}
运行结果：
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/194609.html
微信扫一扫 
支付宝扫一扫 