-
更相减损术
-
璇玑观彩
339
2025-06-06 09:59
更相减损术出自《九章算术》，是一种求最大公约数的经典算法，既可用于约分，亦适用于其他需公约数的场景。其核心步骤如下：
算法流程
1步骤一：
-若两数均为偶数，则持续以2约简；
-若无法约简，进入步骤二。
2步骤二：
-用较大数减较小数，差值再与较小数比较，循环相减至两数相等；
-最终结果=约简的2的乘积×等数（即最大公约数）。
应用案例
用更相减损术求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。
例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。
更相减损法有点类似于求 最大公约数的 Stein算法。在更相减损法中，若两个是偶数则同除以2，结果乘以2。如果增加一个判断，若为一奇一偶则偶数除以2，结果不变，若为两个奇数才相减，这样就变成了目前计算大整数最大公约数的非常好的一个算法，Stein算法。
在上面的实例中，下面是更相减损法与Stein算法的比较，从中可以发现两种算法的相似性。
Stein算法：
98为甲数63为乙数
98是偶数，除以2等于49乙数63
都是奇数，63-49=14甲数49乙数14
14是偶数，除以2等于7甲数49乙数7
49-7=42甲数42乙数7
42是偶数，除以2等于21乙数7
21-7=14乙数14乙数7
14是偶数，除以2等于7乙数7
所以98和63最大公约数是7
算法对比
方法：更相减损术，操作：减法，时间复杂度：O(N)，优化方向：适合小数计算。
方法：辗转相除法，操作：除法，时间复杂度：O(logN)，优化方向：大数效率高。
方法：Stein算法，操作：位运算，时间复杂度：O(logN)，优化方向：大整数优化方案。
“辉理法则”的映射：更相减损原则
1组与组之间间协作策略：
-分组：当多组数据相同数据不多时，独立操作多组以降低风险；
-并组：当数据存在相同数据比较多时，组和组之间选择并组以达到重点突破的效果；
-合组：当多组数据相同的数据特别多时，那么就要采取合组的方式来解决问题，因为一样的数据太多，没有必要分成两组拆分多次操作，合为单一组简化流程。
总结：当然上面说的方式是在正常情况下解决问题时，当有特殊需求时完全是可以反向操作的。
2决策逻辑：
-通过差异度评估（类比更相减损的"约简次数"）动态选择协作模式；
-优先确保系统稳定性，再追求收益最大化。
