编程之美_007最大公约数有关问题

编程之美_007最大公约数问题

// 最大公约数问题
public class Test
{

    public static void main(String[] args)
    {
        System.out.println(isEven(156465489));
        System.out.println("1.辗转相除法:" + commonDivisor1(56, 36));
        System.out.println("2.迭代相减法:" + commonDivisor2(56, 36));
        System.out.println("3.迭代相减法和辗转相除法结合:" + commonDivisor3(56, 36));
    }

    // 1.辗转相除法
    // f(x,y)=f(y,y%x)(y>0)
    // 性能瓶颈：取模运算开销较大
    static int commonDivisor1(int x, int y)
    {
        return (y == 0) ? x : commonDivisor1(y, x % y);
    }

    // 2.迭代相减法
    // f(x,y)=f(x-y,y)(x>y
    // 性能瓶颈：迭代次数增多
    static int commonDivisor2(int x, int y)
    {
        if (x < y)
        {
            return commonDivisor2(y, x);
        }
        if (y == 0)
        {
            return x;
        }
        else
        {
            return commonDivisor2(x - y, y);
        }
    }

    // 3.迭代相减法和辗转相除法结合解最大公约数问题
    static int commonDivisor3(int x, int y)
    {
        if (x < y)
        {
            return commonDivisor3(y, x);
        }
        if (y == 0)
        {
            return x;
        }
        else
        {
            // x为偶数
            if (isEven(x))
            {
                if (isEven(y))
                {
                    return commonDivisor3(x >> 1, y >> 1) << 1;// x偶数,y偶数
                }
                else
                {
                    return commonDivisor3(x >> 1, y);// x偶数,y奇数
                }
            }
            // x为奇数
            else
            {
                if (isEven(y))
                {
                    return commonDivisor3(x, y >> 1);// x奇数,y偶数
                }
                else
                {
                    return commonDivisor3(x - y, y);// x奇数,y奇数
                }
            }
        }
    }

    /**
     * 判断一个数是否是偶数
     * @param x 判断的数字
     * @return true 偶数; false 奇数
     */
    static boolean isEven(int x)
    {
        return (x & 1) == 0 ? true : false;
    }
}

1楼adam_zs昨天 15:44

[code=java]n输出结果：nfalsen1.辗转相除法:4n2.迭代相减法:4n3.迭代相减法和辗转相除法结合:4n[/code]