Question

求两个正整数的最大公约数的算法思想是

Answer 1

在“求两个正整数的最大公约数”问题的算法的问题解决中，除了辗转相除求最大公约数和更相减损之术，是否还有其它的算法。
5
标签:
求两个正整数的最大公约数,
两个
公约数,
公约数
在“求两个正整数的最大公约数”问题的算法的问题解决中，除了辗转相除求最大公约数和更相减损之术，是否还有其它的算法。
辗转相除求最大公约数：
假设求两个正整数m和n的最大公约数。
以下是辗转的算法：
分别用m,n,r表示被除数、除数、余数
①若m<n，则交换m和n
的值
②求m除以n的余数r.
③若r=0,则n为最大公约数.，结束。若r≠0,执行第③步.
④将n的值放在m中,将r的值放在n中.
⑤返回重新执行第②步。
更相减损之术求最大公约数的本质是将辗转相除变为辗转相减。
假设求两个正整数m和n的最大公约数。
以下是更相减损之术的算法：
分别用m,n,r表示被减数、减数、差
①若m<n，则交换m和n
的值
②求m减去n的差值r.
③若r=0,则n为最大公约数.，结束。若r≠0,执行第④步.
④若r<n，则令m=n,n=r。否则m=r，n的值不变。
⑤返回重新执行第②步。