求最大公约数（更相减损法）

爱疯

最大公约数_百度百科
http://baike.baidu.com/view/47637.htm




翻译成现代语言如下：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
例1、用更相减损术求98与63的最大公约数。
解：由于63不是偶数，把98和63以大数减小数，并辗转相减：
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以，98和63的最大公约数等于7。
这个过程可以简单的写为：
（98，63）=（35，63）=（35，28）=（7，28）=（7，21）=（7，14）=（7，7）=7.
例2、用更相减损术求260和104的最大公约数。
解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。
此时65是奇数而26不是奇数，故把65和26辗转相减：
65-26=39
39-26=13
26-13=13
所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即13*2*2=52。








这是对照链接里的《更相减损法》写的。
由于想不出别的办法，只好用f的第3个参数c存放变量的值。
请问：2楼有没有错的地方，怎样修改更好？谢谢！

爱疯

Sub test5()
    Dim a&, b&
    a = 260
    b = 104
    MsgBox f(a, b, 1)
End Sub


'求最大公约数（更相减损法）
Function f&(a&, b&, c%)
    If a = b Then
        f = b * c
        Exit Function
    Else
        If a Mod 2 <> 0 Or b Mod 2 <> 0 Then
            '不都是偶数
            If a < b Then swap a, b
            If a < a - b Then swap a, a - b
            f = f(b, a - b, c)
        Else
            '都是偶数就用2约简
            a = a / 2
            b = b / 2
            c = c * 2
            f = f(a, b, c)
        End If
    End If
End Function


'a,b互换
Sub swap(a&, b&)
    Dim t&
    t = a: a = b: b = t
End Sub

sliang28

好久前老师讲过这个，就是这么算，不知道原理。求余法，等待群子讲解{:3912:}

1. Sub sliang28()
   
2.     a1 = 24: a2 = 15
   
3.     n1 = Application.Max(a1, a2)
   
4.     n2 = Application.Min(a1, a2)
   
5.     Do While n2 <> 0
   
6.         temp = n1 Mod n2
   
7.         n1 = n2
   
8.         n2 = temp
   
9.     Loop
   
10.     MsgBox n1
    
11. End Sub

复制代码

香川群子

你这是要求【最大公约数】吧。

为啥要把 偶数因子 2 排除掉呢？

3楼代码是正确的。
如果保证第1参数大于第2参数，那么代码还可以简化：

Function f&(t1&, t2&)
    Do
        t = t1 Mod t2: t1 = t2: t2 = t
    Loop While t
    f = t1
End Function


如果不保证，前面可以加一句：
If t1 < t2 Then t = t1: t1 = t2: t2 = t


Function f&(t1&, t2&)
    If t1 < t2 Then t = t1: t1 = t2: t2 = t
    Do
        t = t1 Mod t2: t1 = t2: t2 = t
    Loop While t
    f = t1
End Function

香川群子

这个叫做【辗转相余法】，和你说的“更相减损”法本质上是一样的，计算效率高一些而已。

爱疯

谢谢群子老师！


1）我是看了这个后：http://www.excelpx.com/forum.php?mod=redirect&goto=findpost&ptid=13767&pid=61243，
于是看看怎么求最大公约数。去1楼链接后，发现“更相减损法”是另一种方法，
于是按它的规则来写，看能否求出最大公约数，
于是有了2楼。


2）百科说：
比较辗转相除法与更相减损术的区别
（1）都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。

【辗转相余法】步骤少，更简单更好记些。
发2楼的目的是，想学习【更损相减法】的正确方法。


3）“为啥要把 偶数因子 2 排除掉呢？”
是说2楼有此错误吗？我是按它的规则，一步步做的呀   ....  从哪儿起，开始错的呢？
   

香川群子

原理很简单。

两个数，想象为以【最大公约数】为一个单位（一块砖），堆成两堆。

然后每次把多的一堆中，和少的一堆相同的部分拿走，剩余的肯定都还是整数单位。

这个过程反复进行，就能逐步删减两堆的高度，直至最后两者的高度差为一个单位时停止。

香川群子

还可以这样来理解：

两个数t1、t2相除，余数t总是比除数t2小。

那么，如果我再把【除数t2】除以【余数t】，就能得到一个比【余数t】更小的整数。

这样反复递减，到余数=1时就可以停止了。
因为，任何数除以1得到余数就是=0了。

香川群子

如果写成递归函数就更简单了:

1. Function f&(t1&, t2&)
   
2.     If t1 Mod t2 Then f = f(t2, t1 Mod t2) Else f = t2
   
3. End Function
   

复制代码

下面是Sub调用：

Sub test()
    Dim t1&, t2&
    t1 = 260: t2 = 104
    MsgBox f(t1, t2)
End Sub

直接在工作表中使用也毫无问题。

并且，此函数的特点是，不需要事先进行大小数判断，也能得出正确结果。
（因为mod 过程可以自动交换大小数）

爱疯

Sub test()
MsgBox f(6, 3)
End Sub

Function f&(t1&, t2&)
' If t1 Mod t2 Then f = f(t2, t1 Mod t2) Else f = t2
f = IIf(t1 Mod t2, f(t2, t1 Mod t2), t2) '运行时错误11:除数为零
End Function






原以为两句等效，实际上IIF函数出错了。

1）既然参数 number2不可以是0，为什么帮助没说啊？



2）为什么条件 3 mod 0，在IF语句中就对，在IIF函数里就错呢？