• 中文
    • English
  • 注册
  • 查看作者
  • 《算法第四版》课后练习题1.2.16答案

    习题1.2.16

    有理数。为有理数实现一个不可变数据类型 Rational,支持加减乘除操作。

    《算法第四版》课后练习题1.2.16答案

    无需测试溢出(请见练习1.2.17),只需使用两个long型实例变量表示分子和分母来控制溢出的可能性。使用欧几里得算法来保证分子和分母没有公因子。编写一个测试用例检测你实现的所有方法。

    要点分析

    1.  欧几里得算法

    在课本的第一页曾经介绍过欧几里得算法,欧几里得算法用于计算两个数的最大公约数。这里再次给出该算法的实现。

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

    2.  有理数

    有理数是正整数、负整数、正分数、负分数以及零的统称。而无理数是无限不循环小数,注意区分两者。

    3.  公约数

    公约数,亦称“公因数”。它是一个能被若干个整数同时均整除的整数。如果一个整数同时是几个整数的约数,称这个整数为它们的“公约数”;公约数中最大的称为最大公约数。比如18和30的最大公约数是16。对任意的若干个正整数,1总是它们的公因数。[1] 

    4.  公倍数

    公倍数(common multiple)是指在两个或两个以上的自然数中,如果它们有相同的倍数,这些倍数就是它们的公倍数。[2]

    参考答案

    import java.util.Objects;
    
    /**
     * @description: 有理数的加减乘除
     * @author: ZhangJia
     * @create: 2018-09-07 11:30
     **/
    
    public class Rational {
        private final long numerator;  //分子
        private final long denominator; //分母
    
        public Rational(long numerator, long denominator) {
            if (denominator == 0) {
                throw new ArithmeticException("分母不能为0");
            }
            long gcd = gcd(numerator, denominator);//获取分子和分母的最大公约数
            //保证分子和分母没有公因子
            this.numerator = numerator / gcd;
            this.denominator = denominator / gcd;
    //        System.out.println(this.numerator + " " + this.denominator);
        }
    
        public static long gcd(long p, long q) {
            if (q == 0) return p;
            long r = p % q;
            return gcd(q, r);
        }
    
        public Rational plus(Rational b) {
            //通分
            long this_deno = this.denominator * b.denominator;  //该数的分母
            long this_nume = this.numerator * b.denominator; //该数的分子
            long b_nume = b.numerator * this.denominator; //b的分子
            return new Rational(this_nume + b_nume, this_deno); //该数和b相加
        }
    
        public Rational minus(Rational b) {
            //通分
            long this_deno = this.denominator * b.denominator;  //该数的分母
            long this_nume = this.numerator * b.denominator; //该数的分子
            long b_nume = b.numerator * this.denominator; //b的分子
            return new Rational(this_nume - b_nume, this_deno); //该数和b相减
        }
    
        public Rational times(Rational b) {
            return new Rational(this.numerator * b.numerator, this.denominator * b.denominator); //该数和b相乘
        }
    
        public Rational divides(Rational b) {
    
           return this.times(new Rational(b.denominator,b.numerator)); //除以一个数,等于乘以这个数的倒数。
        }
    
        @Override
        public String toString() {
            if (denominator == 1) return numerator + "";
            else return numerator + "/" + denominator;
        }
    
        public long getNumerator() {
            return numerator;
        }
    
        public long getDenominator() {
            return denominator;
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Rational)) return false;
            Rational rational = (Rational) o;
            return getNumerator() == rational.getNumerator() &&
                    getDenominator() == rational.getDenominator();
        }
    
        @Override
        public int hashCode() {
    
            return Objects.hash(getNumerator(), getDenominator());
        }
    
        public static void main(String[] args) {
            Rational a = new Rational(1, 2);
            Rational b = new Rational(1, 3);
            Rational c = new Rational(1, 3);
            System.out.println(a.plus(b));
            System.out.println(a.minus(b));
            System.out.println(a.times(b));
            System.out.println(a.divides(b));
            System.out.println(b.equals(c));
        }
    
    
    }
    
    
    输出:
    5/6
    1/6
    1/6
    3/2
    true

    官方答案

    public class Rational implements Comparable<Rational> {
        private static Rational zero = new Rational(0, 1);
    
        private long num;   // the numerator
        private long den;   // the denominator
    
        // create and initialize a new Rational object
        public Rational(long numerator, long denominator) {
    
            // deal with x/0
            if (denominator == 0) {
                throw new ArithmeticException("denominator is zero");
            }
    
            // reduce fraction
            long g = gcd(numerator, denominator);
            num = numerator   / g;
            den = denominator / g;
    
            // only needed for negative numbers
            if (den < 0) {
                den = -den;
                num = -num;
            }
        }
    
        // return the numerator and denominator of this rational number
        public long numerator()   { return num; }
        public long denominator() { return den; }
    
        // return double precision representation of this rational number
        public double toDouble() {
            return (double) num / den;
        }
    
        // return string representation of this rational number
        public String toString() { 
            if (den == 1) return num + "";
            else          return num + "/" + den;
        }
    
        // return { -1, 0, +1 } if this < that, this = that, or this > that
        public int compareTo(Rational that) {
            long lhs = this.num * that.den;
            long rhs = this.den * that.num;
            if (lhs < rhs) return -1;
            if (lhs > rhs) return +1;
            return 0;
        }
    
        // is this Rational object equal to other?
        public boolean equals(Object other) {
            if (other == null) return false;
            if (other.getClass() != this.getClass()) return false;
            Rational that = (Rational) other;
            return this.compareTo(that) == 0;
        }
    
        // hashCode consistent with equals() and compareTo()
        public int hashCode() {
            return this.toString().hashCode();
        }
    
    
        // create and return a new rational (r.num + s.num) / (r.den + s.den)
        public static Rational mediant(Rational r, Rational s) {
            return new Rational(r.num + s.num, r.den + s.den);
        }
    
        // return gcd(|m|, |n|)
        private static long gcd(long m, long n) {
            if (m < 0) m = -m;
            if (n < 0) n = -n;
            if (0 == n) return m;
            else return gcd(n, m % n);
        }
    
        // return lcm(|m|, |n|)
        private static long lcm(long m, long n) {
            if (m < 0) m = -m;
            if (n < 0) n = -n;
            return m * (n / gcd(m, n));    // parentheses important to avoid overflow
        }
    
        // return this * that, staving off overflow as much as possible by cross-cancellation
        public Rational times(Rational that) {
    
            // reduce p1/q2 and p2/q1, then multiply, where a = p1/q1 and b = p2/q2
            Rational c = new Rational(this.num, that.den);
            Rational d = new Rational(that.num, this.den);
            return new Rational(c.num * d.num, c.den * d.den);
        }
    
    
        // return this + that, staving off overflow
        public Rational plus(Rational that) {
    
            // special cases
            if (this.compareTo(zero) == 0) return that;
            if (that.compareTo(zero) == 0) return this;
    
            // Find gcd of numerators and denominators
            long f = gcd(this.num, that.num);
            long g = gcd(this.den, that.den);
    
            // add cross-product terms for numerator
            Rational s = new Rational((this.num / f) * (that.den / g)
                                    + (that.num / f) * (this.den / g),
                                      this.den * (that.den / g));
    
            // multiply back in
            s.num *= f;
            return s;
        }
    
        // return -this
        public Rational negate() {
            return new Rational(-num, den);
        }
    
        // return |this|
        public Rational abs() {
            if (num >= 0) return this;
            else return negate();
        }
    
        // return this - that
        public Rational minus(Rational that) {
            return this.plus(that.negate());
        }
    
    
        public Rational reciprocal() { return new Rational(den, num);  }
    
        // return this / that
        public Rational dividedBy(Rational that) {
            return this.times(that.reciprocal());
        }
    
    
        // test client
        public static void main(String[] args) {
            Rational x, y, z;
    
            // 1/2 + 1/3 = 5/6
            x = new Rational(1, 2);
            y = new Rational(1, 3);
            z = x.plus(y);
            StdOut.println(z);
    
            // 8/9 + 1/9 = 1
            x = new Rational(8, 9);
            y = new Rational(1, 9);
            z = x.plus(y);
            StdOut.println(z);
    
            // 1/200000000 + 1/300000000 = 1/120000000
            x = new Rational(1, 200000000);
            y = new Rational(1, 300000000);
            z = x.plus(y);
            StdOut.println(z);
    
            // 1073741789/20 + 1073741789/30 = 1073741789/12
            x = new Rational(1073741789, 20);
            y = new Rational(1073741789, 30);
            z = x.plus(y);
            StdOut.println(z);
    
            //  4/17 * 17/4 = 1
            x = new Rational(4, 17);
            y = new Rational(17, 4);
            z = x.times(y);
            StdOut.println(z);
    
            // 3037141/3247033 * 3037547/3246599 = 841/961 
            x = new Rational(3037141, 3247033);
            y = new Rational(3037547, 3246599);
            z = x.times(y);
            StdOut.println(z);
    
            // 1/6 - -4/-8 = -1/3
            x = new Rational(1, 6);
            y = new Rational(-4, -8);
            z = x.minus(y);
            StdOut.println(z);
        }
    
    }

    参考资料

    [1] 百度百科:公约数

    [2] 百度百科:公倍数

  • 0
  • 0
  • 0
  • 4k
  • 请登录之后再进行评论

    登录
    单栏布局 侧栏位置: