更相减损术
更相减损术,又称"等值算法"
关于约分问题,实质是如何求分子,分母最大公约数的问题。《九章算术》中介绍了这个方法,叫做”更相减损术”,数学家刘徽对此法进行了明确的注解和说明,是一个实用的数学方法。
例:今有九十一分之四十九,问约之得几何?
我们用(91,49)表示91和49的最大公约数.按刘徽所说,分别列出分子,分母。
“以少减多,更相减损,求其等也,以等数约之,等数约之,即除也,其所以相减者皆等数之重叠,故以等数约之。”
译文如下:
约分的法则是:若分子、分母均为偶数时,可先被2除,否则,将分子与分母之数列在它处,然后以小数减大数,辗转相减,求它们的最大公约数,用最大公约数去约简分子与分母。
其与古希腊欧几里德所著的《几何原本》中卷七第一个命题所论的相同。列式如下:
91 49
42 49
42 7
35 7
28 7
21 7
14 7
77
这里得到的7就叫做“等数”,91和49都是这等数的重叠(即倍数),故7为其公约数.而7和7的最大公约数就是7,(7,7)=7,所以(91,49)=(42,7)=(7,7)=7
更相减损术在现代仍有理论意义和实用价值.吴文俊教授说:“在我国,求两数最大公约数即等数,用更相减损之术,将两数以小减大累减以得之,如求24与15的等数,其逐步减损如下表所示:(24,15)->(9,15)->(9,6)->(3,6)->(3,3)
每次所得两数与前两数有相同的等数,两数之值逐步减少,因而到有限步后必然获得相同的两数,也即所求的等数,其理由不证自明。
这个寓理于算不证自明的方法,是完全构造性与机械化的尽可以据此编成程序上机实施”.吴先生的话不仅说明了此法的理论价值,而且指明学习和研究的方向.
更相减损法很有研究价值,它奠定了我国渐近分数,不定分析,同余式论和大衍求一术的理论基础.望能仔细品味。
代码如下:
int gcd(int a,int b)
{
while(a != b)
{
if(a>b) a -= b;
else b -=a;
}
return a;
}
分享到:
相关推荐
N1(单) 最大公约数-更相减损法(2).c
117、1627:【例 3】最大公约数--2020.04.13a.pdf
分解质因数,连续整除,欧几里得三种算法求最大公约数
更相减损法:也叫 更相减损术,是出自《 九章算术》的一种求最大公约数的算法,它原本是为 约分而设计的,但它适用于任何需要求最大公约数的场合。 《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来...
有关c++求最大公约数的代码,用的是辗转相除法,很简单的算法过程,主要是求最大公约数
最大公约数,包括3种算法的实现 非常的不错
求两个自然数m和n的最大公约数。 理解这样一个观点:不同的算法能够解决相同的问题,这些算法的解题思路不同,复杂程度不同,解题效率也不同。
求两个数的最大公约数 用的是辗转相除法
基于FPGA开发板的两位数求最大公约数和最小公倍数的设计,该设计中利用辗转相减法求得公约数与公倍数,且两个数的数值可通过按键修改,设计灵活可靠。该设计基于vivado开发,并带有testbench文件,方便仿真学习。
python求最大公约数和最小公倍数 #辗转相除法 def gcd(a,b): #最大公约数函数,且最小公倍数 = 两个数相乘 / 最大公约数 if b == 0: return a else: return gcd(b,a%b) print("请输入两个数:") j,k = input()....
对输入1-100内的两个整数,求其最大公约数,输入一个0-500的整数,判断其能否被3,5,7整除,并输入下列信息之一: (1) 能够同时被3,5,7整除 (2) 能够同时被其中两个数整除(给出这两个数) 进行白盒测试
包含了:1.辗转相除法函数嵌套流程图2.辗转相除法函数递归流程图3.穷举法求最小公倍数流程图4.穷举法求最大公约数流程图5.更相减损术流程图
关于如何求最大公约数和最小公倍数的c语言程序
C语言求最大公约数
用最简单的C++语言实现求最大公约数,而且带有界面,容易理解。
用Verilog编写的求两个数的最大公约数,此为完整的工程文件,是可综合的,注意while语句在Verilog中是不可综合的!
用辗转相除法,计算最大公约数的C语言代码。
用LabVIEW求最大公约数和最小公倍数。可以自行选择数据。
预期目标:想要学习算法的朋友或同学,这是一个最好的入门案例,因为它的逻辑很清楚好理解,求最大公约数大家在初中就学过吧,对,现在要把它的逻辑编程程序。而且用了三种不同的算法实现,大家做题也是可以一题多解...