6.算法之数学（数论）算法——更相减损术

目录

1.什么是更相减损术？

2.数学推导

3.代码实现

4.最小公倍数计算

---

1.什么是更相减损术？

其使用方法如下

举个例子吧

可见更相减损术和辗转相除法有异曲同工之妙。

其数学原理也是一样的。

2.数学推导

 他是辗转相除法的一种特殊情况，下面我们用代码来实现它。

3.代码实现

#include<stdio.h>//更相减损术 
int main()
{ int a,b;printf("这个程序可以计算两个数的最大公约数！\n"); printf("请输入两个数字,用空格隔开：\n") ;scanf("%d %d",&a,&b);while(a!=b){if(a>b)//如果a不等于b，则大数减小数。 a-=b;elseb-=a;}printf("您输入的两个数字的最大公因数为%d\n",b);} 

我们依然可以用递归函数：

#include<stdio.h>//更相减损术 
int gcd(int m,int n)
{if(m==n) return n;else if(m>n) return gcd(n,m-n);else return gcd(m,n-m);
}
int main()
{ int a,b;printf("这个程序可以计算两个数的最大公约数！\n"); printf("请输入两个数字,用空格隔开：\n") ;scanf("%d %d",&a,&b);printf("您输入的两个数字的最大公因数为%d\n",gcd(a,b));} 

返回值根据二者大小会有区别。

4.最小公倍数计算

我们还可以顺理成章的计算最小公倍数

 根据数学关系可知，知道两个数和他们的最大公因数便可以求出最小公倍数了。

#include<stdio.h>//更相减损术 
int main()
{ int a,b,x,y;printf("这个程序可以计算两个数的最大公约数和最小公倍数！\n"); printf("请输入两个数字,用空格隔开：\n") ;scanf("%d %d",&a,&b);x=a;y=b;while(a!=b){if(a>b)//如果a不等于b，则大数减小数。 a-=b;elseb-=a; }printf("您输入的两个数字的最大公因数为%d\n",b);printf("您输入的两个数字的最小公倍数为%d\n",x*y/b); } 

 我们同样可以对辗转相除法添加运算求得最小公倍数。

两者在数学上是同根同源的。

只不过一个体现了古代西方智慧，一个体现了古代中国智慧。