用更相减损术求156与72的最大公约数

来源：学生作业帮编辑：搜狗做题网作业帮分类：数学作业时间：2024/07/07 10:18:40

用更相减损术求156与72的最大公约数

156-72=84
84-72=12
72-12=60
60-12=48
48-12=36
36-12=24
24-12=12
再问：那辗转相除法和更相减损术有什么不同啊？
再答：更相减损术和辗转相除法的主要区别在于前者所使用的运算是“减”，后者是“除”。从算法思想上看，两者并没有本质上的区别，但是在计算过程中，如果遇到一个数很大，另一个数比较小的情况，可能要进行很多次减法才能达到一次除法的效果，从而使得算法的时间复杂度退化为O(N)，其中N是原先的两个数中较大的一个。相比之下，辗转相除法的时间复杂度稳定于O(logN)。

用更相减损术求333和24的最大公约数用更相减损术求459与357的最大公约数是______．用更相减损术求459与357的最大公约数需做多少次减法分别用辗转相除法与更相减损术求161与253的最大公约数用辗转相除法或更相减损术求1890与462的最大公约数分别用辗转相除法、更相减损术求204与85的最大公约数．用辗转相除法求228与1995的最大公约数，并用更相减损术检验你的结果．分别用辗转相除法和更相减损术求282与470的最大公约数,快, 用辗转相除法或更相减损术怎么求三个数的最大公约数分别用辗转相除法、更相减损术求288、1995的最大公约数. 利用辗转相除法或更相减损术求406,232,145的最大公约数用辗转相除法或更相减损术求下列两数的最大公约数 612,396的最大公约数