基于辗转相除法求最大公约数
(1)p=0,q=0 无最大公约数
(2)p=0,q≠0 最大公约数为q
(3)p≠0,q=0 最大公约数为p
(4)p≠0,q≠0 最大公约数可通过辗转相除取余数转化为(2)(3)这样的情况来求解
//递归版，非递归用循环
public class Euclid {
public static void main(String[] args) {
System.out.println(euclid(16,8));
}
public static int euclid(int p,int q) {
int r=0,min=0;
if(p==0||q==0) {
if(p==0&&q==0)
return -1;
else if(p==0)
return q;
else if(q==0) {
return p;
}
}
else {
if(p<q)
{
r = q % p;
min = p;
}
else
{
r = p % q;
min =q;
}
}
return euclid(min,r);
}
}
//非递归
public class Euclid {
public static void main(String[] args) {
System.out.println(euclid(16,8));
}
public static int euclid(int p,int q) {
int r=0,min=0;
while(p!=0&&q!=0) {
if(p<q)
{
r = q % p;
min = p;
}
else
{
r = p % q;
min =q;
}
p=min;
q=r;
}
if(p==0&&q==0)
return -1;
else if(p==0)
return q;
else if(q==0)
return p;
return -1; //为了返回值强行加，突然感觉返回值好烦人
}
}
