最大公因数求法详解：辗转相除法与更相减损法
最大公因数求法详解：辗转相除法与更相减损法
本文详细介绍了最大公因数的求法，包括辗转相除法和更相减损法，并通过杭州电子科技大学的ACM入门题进行实际应用演示。文章内容适合编程初学者学习和参考。
前言
本篇博客对：最大公因数，辗转相除法，更相减损法等专有名词进行了详细的介绍，分享了两种求解最大公因数的算法代码，以杭州电子科技大学的ACM入门题作为索引，借助实际代码，对上面介绍的两种算法求解最大公因数进行初级应用，粗略地介绍了递归思想对算法的优化。
一、名称定义
1.最大公约数
定义：最大公因数是指两个或多个整数共有约数中最大的一个。
示例：12、16的公约数有1、2、4，其中最大的一个是4，4是12与16的最大公约数。
2.辗转相除法
定义：辗转相除法是求两个自然数的最大公约数的一种方法。
示例：求319，377的最大公约数
319÷377=0（余319）
377÷319=1（余58）
319÷58=5（余29）
58÷29=2（余0）
当余数为0时，除数即为最大公约数：29
- while循环
int fun(int m,int n)
{
int r; //余数，当余数为0的时候，m即为最大公约数
while(n!= 0)//先取余，再用余数对较小的数求余，直到余数为零
{
r = m % n;
m = n;
n = r;
}
return m; //将结果返回
}
- 调用递归
int fun(int m,int n)
{
if(n！=0) return fun(n,m%n);
return m;
}
- 简化递归
int fun(int m, int n)
{
return n ? fun(n, m % n) : m;
}
3.更相减损法
定义：更相减损法是出自《九章算术》的一种求最大公约数的算法。
示例：求98与63的最大公约数。
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
7-7=0
当差为0时，除数即为最大公约数：7
while循环
int fun(int m,int n)
{
while(m!=n) //当差为0的时候，n即为最大公约数
{
if(m>n)
m=m-n;
else
n=n-m;
}
return n;
}
二、ACM杭电入门题
先来看一个杭电的水题，看看有有没有解题思路
ACM编程题（请根据下列各题目的描述、输入和输出要求，分别写出相应正确的代码）
----------------------------------第11题（hdu2503）--------------------------------
（1）题目
a/b + c/d
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
给你2个分数，求他们的和，并要求和为最简形式。
Input
输入首先包含一个正整数T（T<=1000），表示有T组测试数据，然后是T行数据，每行包含四个正整数a,b,c,d（0<a,b,c,d<1000），表示两个分数a/b 和 c/d。
Output
对于每组测试数据， 输出两个整数e和f，表示a/b + c/d的最简化结果是e/f，每组输出占一行。
Sample Input
2
1 2 1 3
4 3 2 3
Sample Output
5 6
2 1
- 本题在ACM中并不难，主要考察是否掌握最大公约数的求法
1.解题思路
- 先求解出未化简的e,f
- 再求出最大公因数z（两种方法）
- 最后输出e=e/z, f=f/z
三、解题参考代码(C语言，C++)
0.最优算法（C++）
一个优秀的acmer总是寻求最优算法（辗转相除法时间复杂度优于更相减损法）
本段代码为c++语言编写，新手小白看不懂可以看下面的C语言解题
#include<iostream> //头文件
using namespace std;
int fun(int m,int n) //定义函数 辗转相除法
{
return n?fun(n,m%n):m; //求解最大公因数n,返回其值
}
int main()
{
int n,a,b,c,d,e,f,z; //n行数，z最大公约数
cin>>n;
while(n--){
cin>>a>>b>>c>>d;
e=a*d+b*c;
f=b*d;
z=fun(e,f); //调用函数返回最大公约数
cout<<e/z<<f/z; //输出最简答案
}
return 0;
}
1.辗转相除求解（C语言）
（1）参考代码：
#include<stdio.h>
int main()
{
int t,e,f,m,n,tmp,r;
scanf("%d",&t);
for(int i=0;i<t;i++)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
e=a*d+b*c;
f=b*d;
///进行最大公约数的求解(f,e) <==> (m,n)
m=f;
n=e;
///辗转相除
r=m%n;
while(r!=0)
{
m=n;
n=r;
r=m%n;
}
///经过上面的辗转过程，所求的最大公约数就是n//
printf("%d %d\n", e/n, f/n);
}
return 0;
}
2.更相减损法求解（C语言）
（2）参考代码：
#include<stdio.h>
int main()
{
int t,e,f,m,n;
scanf("%d",&t);
for(int i=0;i<t;i++)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
e=a*d+b*c;
f=b*d;
///进行最大公约数的求解(f,e) <==> (m,n)
m=f;
n=e;
//辗转相减
while(m!=n)
{
if(m>n)
m=m-n;
else
n=n-m;
}
///经过上面的辗转过程，所求的最大公约数就是n//
printf("%d %d\n",e/n,f/n);
}
return 0;
}