本文目录一览:
辗转相除法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");
}
运行结果:
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 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语言里面的辗转相除法
用辗转相除法(即欧几里得算法)求两个正整数的最大公约数。
解析:
设两个数m,n,假设m=n,用m除以n,求得余数q。若q为0,则m为最大公约数;若q不等于0,则进行如下迭代:
m=n,n=q,即原除数变为新的被除数,原余数变为新的除数重复算法,直到余数为0为止。余数为0时的除数n,即为原始m、n的最大公约数。
迭代初值: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的值
源程序:
#includestdio.h
void main()
{
int m,n,q,a,b;
printf("Enter two integers:");
scanf("%d%d",a,b);
m=a;
n=b;
if(nm)
{
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\n",a,b,m);
}
希望对你有所帮助!
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语言
这是求最大公约数的,没有问题啊,是不是你输入出错了,示例运行结果如下:
12,8
gcd=4
16,36
gcd=4
中间的逗号不能少的哦,否则就会出错了,因为scanf("%d,%d",a,b);的%d,%d中间是有都逗号的呀。