的确,按照“古典”的更相减损术求最大公约数时,是要先判断是否为偶数,若均为偶数,则均除以2,直到有奇数为止,这样做的好处是把数据规模减小.但是,如果用计算机来求最大公约数,这一步不仅显得多余(机器计算86-58与43-29是一样的难易程度),而且最后求出最大公约数后,还要乘以刚才约掉的2的因数,显得更加繁琐,因此,用计算机来求最大公约数,往往都直接用大数减去小数,辗转相减.不过,求最大公约数最好的算法还是欧几里德算法(辗转相除法),因为除法比减法效率要高得多.
用更相减损术求最大公约数时,它的步骤不是先判断是否为偶数吗?为什么在程序框图中没有显示出来,而是判断是否相等?
1个回答
相关问题
-
编写用更相减损术求两个正整数a b的最大公约数的程序.
-
更相减损术求440和556的最大公约数
-
用辗转相除法求最大公约数并用更相减损术检验5280,12155
-
用辗转相除法或更相减损术求1890与462的最大公约数
-
分别用辗转相除法、更相减损术求288、1995的最大公约数.
-
用辗转相除法和更相减损术求272与153的最大公约数
-
用辗转相除法或者更相减损术求三个数 324,243,135 的最大公约数.
-
用辗转相除法求80和36的最大公约数,并用更相减损术检验所得结果.
-
求612,396,264的最大公约数.(用辗转相除法或更相减损法,并设计出它的程序.)
-
求下列问题:(1)用“更相减损术”求两数72,168;的最大公约数;并用“辗转相除法”检验.(2)将二进制数101101