题目:随机输入两个数,求其最大公约数
在此展示三种常用解题思路
1.首先展示第一种思路
#include <stdio.h>
int main()
{
int a,b,c; //先定义变量
printf("请输入:\n");
scanf("%d%d",&a,&b); //输入两个整型数字
if(a<b)
{
c=a;
a=b;
b=c; //保证a≥b
}
int i = 0;
for(i = b;i>0;i--)
{
if(a%i == 0 && b%i == 0)
{
printf("gcd(%d,%d) = %d\n",a,b,i);
break;
}
}
return 0;
}
2.辗转相除法
这里涉及到一个公式:GCD(a,b) = GCD(b,a%b)
#include <stdio.h>
int main()
{
int a,b,c;
printf("请输入:");
scanf("%d%d",&a,&b);
if(a<b)
{
c = a;
a = b;
b = c; //确保a≥b
}
while(b != 0)
{
c = b;
b = a%b; //辗转相除:相比第一种思路大大提高了代码的效率
a = c;
}
printf("最大公约数为:%d",a);
return 0;
}
还有一种运用递归的思想
#include <stdio.h>
int Gcd(int a,int b)
{
if(a > b)
{
if(a % b == 0)
{
return b;
}
else
{
return Gcd(b,a%b);
}
}
else
{
if(b % a == 0)
{
return a;
}
else
{
return Gcd(a,b%a);
}
}
}
int main()
{
int a, b;
int c = 0;
printf("请输入两个整数:");
scanf("%d%d",&a, &b);
c = Gcd(a, b);
printf("GCD(%d,%d)=%d\n",a,b,c);
}
3.更相减损术
定义:(如果需要对分数进行约分,那么)可以折半的话,就折半(也就是用2来约分)。如果不可以折半的话,那么就比较分母和分子的大小,用大数减去小数,互相减来减去,一直到减数与差相等为止,用这个相等的数字来约分。
#include <stdio.h>
main()
{
int a,b;
printf("请输入两个正整数:");
scanf("%d%d",&a,&b);
while(a%2==0)
{
a/=2;
}
while(b%2==0)
{
b/=2;
} //让两个数都为奇数
while(a!=b)
{
if(a>b) a=a-b;
else b=b-a; //更相减损术:当差值等于减数的值时即为最大公约数
}
printf("GCD=%d\n",a);
return 0;
}
本文结束,感谢阅览!
今天的文章C语言求最大公约数代码分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/26805.html