问题描述

求两个数最大公约数，欧几里得算法

求两个数最大公约数，欧几里得算法，这两种方法除第一种可以避免除数为零的情况，两者有什么区别？谢谢
public static int gcd(int p, int q)
{
if (q == 0) return p;
int r = p % q;
return gcd(q, r) ;
}

public static int gcd(int p, int q)
{
int r = p % q;
if (r == 0)
return q;
return gcd(q, r);
}

解决方案

第一种和第二种的区别就像
Do{ }While{}和Loop{}Until{}的区别一样
前者至少执行一次循环
而你这两个算法前者至少执行一次递归
比如说两个相同的非零数字 24和24
第二次可以直接得出r=0，然后return
第一次还要把r=0这个判断留到下次递归再进行

解决方案二：

第二种最大公约数包括自身

解决方案三：

第二个方法比第一个少一次递归调用，个人愚见。

解决方案四：

第二段代码是尾递归，换言之可以不用递归了。

解决方案五：

第1个除了第一次会避免除0外，其它都一样

解决方案六：

• 第一种方法上来就判断除数是否为零。所以可以直接避免q=0的情况，但是当q=0的时候， p不是所需的解。
• 第二种方法在取完余数后判断余数是否为零，一方面获得了解，另一方面也间接的解除了下一次辗转相除的除数为0的情况（因为下一次实际做的是q%r）。但是这种方法无法避免第一次的除数为0的情况。