最大公约数循环与递归版本
2023-09-14 09:14:24 时间
简介: 本文讲解,求最大公约数循环与递归版本。
最大公约数介绍:最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数,a,b的最小公倍数记为[a,b]。
循环版本:
方法辗转相除法
#include <stdio.h>
int main()
{
int a, b, t;
scanf("%d%d", &a, &b);
// 我们需要保证的是a不能比b小
if(a < b)
{
t = a;
a = b;
b = t;
}
while(b != 0)
{
t = b;
b = a % b; //辗转相除:相比第一种思路大大提高了代码的效率
a = t;
}
printf("最大公约数为:%d",a);
return 0;
}
递归版本:
方法辗转相除法
#include <stdio.h>
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
int a, b, t;
scanf("%d%d", &a, &b);
// 我们需要保证的是a不能比b小
if(a < b)
{
t = a;
a = b;
b = t;
}
printf("最大公约数为:%d",gcd(a, b));
return 0;
}
相关文章
- JS实现图片循环滚动
- 【说站】python for循环的本质探究
- 批处理的for循环_bat脚本for循环
- SQL递归实现循环判断
- SQL Server 树形表非循环递归查询的实例详解
- android 自定义Viewpager实现无限循环详解手机开发
- MySQL中的循环控制:优雅简明(mysqlloop)
- shell循环
- 使用 Oracle 构建循环语句的实战技巧(oracle使用循环语句)
- oracle中应用循环语句快速插入数据(oracle 中循环插入)
- 循环在Oracle中使用While循环的实践与技巧(oracle中while)
- Redis实现自增长循环打破数据库局限性(redis 自增长循环)
- 详细讲解ASP脚本循环语句