• 注册
  • 赞助本站

    • 微信
    • 支付宝
    • Q Q

    感谢一直支持本站的所有人!

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

      习题1.2.16

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

      无需测试溢出(请见练习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
    • 1.4k
    • 单栏布局 侧栏位置: