• 注册
  • 赞助本站

    • 微信
    • 支付宝
    • Q Q

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

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

      习题1.2.17

      有理数实现的健壮性。在 Rational(请见练习1.2.16)的开发中使用断言来防止溢出。

      要点分析

      1.  断言

      在程序设计中,断言(assertion)是一种放在程序中的一阶逻辑(如一个结果为真或是假的逻辑判断式),目的是为了标示与验证程序开发者预期的结果-当程序运行到断言的位置时,对应的断言应该为真。若断言不为真时,程序会中止运行,并给出错误消息。[1] 

      关于断言的具体使用方法,这里不再赘述,不了解的同学可以点击java断言assert初步使用:断言开启、断言使用一文查看。

      2.  溢出

      在联系1.2.16中,我们暂时使用long类型来控制溢出,在本题中,我们将上题的long类型,都改回int,然后利用断言来防止溢出。

      Java中如何用float和double指数记数法表示的最大和最小的数字 一文中,我曾经提到过如果输出float和double类型的最大和最小的数字,其实int类型也是同样的道理:

      public class Test {
          public static void main(String[] args) {
              System.out.println("MIN: " + Integer.MIN_VALUE);
              System.out.println("MAX: " + Integer.MAX_VALUE);
              System.out.println();
          }
      }
      
      输出:
      MIN: -2147483648
      MAX: 2147483647

      3.  处理溢出

      我们在处理溢出的时候,只需要判断加减乘除操作后得出的结果是否溢出即可,不需要理会输入的数字是否溢出,因为如果输入的数字过大溢出的话,编译器会主动报出InputMismatchException异常。

      那么我们如何处理结果溢出呢?如果直接用result > 2147483647这样比较是不行的,原因如下:

      public class Test {
          public static void main(String[] args) {
              int a = 2147483647 + 1; //结果并不是2147483648,而是-2147483648
              System.out.println(a > 2147483647);
          }
      }
      
      输出:
      false

      那么我们应该如何处理呢?Java8在Math类中,为我们提供了三个非常好的方法,供我们处理溢出:

      //加法
      public static int addExact(int x, int y) {
          int r = x + y;
          // HD 2-12 Overflow iff both arguments have the opposite sign of the result
          if (((x ^ r) & (y ^ r)) < 0) {
              throw new ArithmeticException("integer overflow");
          }
          return r;
      }
      //减法
      public static int subtractExact(int x, int y) {
          int r = x - y;
          // HD 2-12 Overflow iff the arguments have different signs and
          // the sign of the result is different than the sign of x
          if (((x ^ y) & (x ^ r)) < 0) {
              throw new ArithmeticException("integer overflow");
          }
          return r;
      }
      
      //乘法
      public static int multiplyExact(int x, int y) {
          long r = (long)x * (long)y;
          if ((int)r != r) {
              throw new ArithmeticException("integer overflow");
          }
          return (int)r;
      }

      除法的我们可以利用乘以倒数来操作,所以只需要上面的三个方法并将其修改为断言的方式即可:

      //加法溢出判断
      public static void addExact(int x, int y) {
          int r = x + y;
          assert (!(((x ^ r) & (y ^ r)) < 0)) : "加法溢出";
      
      }
      
      //减法溢出判断
      public static void subtractExact(int x, int y) {
          int r = x - y;
      
          assert (!(((x ^ y) & (x ^ r)) < 0)):"减法溢出";
      }
      
      //乘法溢出判断
      public static void multiplyExact(int x, int y) {
          long r = (long) x * (long) y;
          assert (!((int) r != r)):"乘法溢出";
      }

      参考答案

      import java.util.Objects;
      import java.util.Scanner;
      
      public class Rational {
          private int numerator;  //分子
          private int denominator; //分母
      
          public Rational(int numerator, int denominator) {
      
              if (denominator == 0) {
                  throw new ArithmeticException("分母不能为0");
              }
              int gcd = gcd(numerator, denominator);//获取分子和分母的最大公约数
              //保证分子和分母没有公因子
              this.numerator = numerator / gcd;
              this.denominator = denominator / gcd;
      
             /* if (this.numerator < 0 | this.denominator < 0) {
                  this.numerator = -this.numerator;
                  this.denominator = -this.denominator;
              }*/
          }
      
          //欧几里得算法
          public static int gcd(int p, int q) {
              if (q == 0) return p;
              int r = p % q;
              return gcd(q, r);
          }
      
      
          //加法
          public Rational plus(Rational b) {
      
              multiplyExact(this.denominator, b.denominator);
              multiplyExact(this.numerator, b.denominator);
              multiplyExact(this.denominator, b.numerator);
      
              //通分
              int this_deno = this.denominator * b.denominator;  //该数的分母
              int this_nume = this.numerator * b.denominator; //该数的分子
              int b_nume = b.numerator * this.denominator; //b的分子
      
              addExact(this_nume, b_nume);
              addExact(this_nume + b_nume, this_deno);
      
              Rational temp = new Rational(this_nume + b_nume, this_deno);
      
              return temp;//该数和b相加
          }
      
          //减法
          public Rational minus(Rational b) {
      
              multiplyExact(this.denominator, b.denominator);
              multiplyExact(this.numerator, b.denominator);
              multiplyExact(this.denominator, b.numerator);
              //通分
              int this_deno = this.denominator * b.denominator;  //该数的分母
              int this_nume = this.numerator * b.denominator; //该数的分子
              int b_nume = b.numerator * this.denominator; //b的分子
      
              subtractExact(this_nume, b_nume);
              subtractExact(this_nume - b_nume, this_deno);
              Rational temp = new Rational(this_nume - b_nume, this_deno);
              return temp; //该数和b相减
          }
      
          //乘法
          public Rational times(Rational b) {
              multiplyExact(this.numerator, b.numerator);
              multiplyExact(this.denominator, b.denominator);
              multiplyExact(this.numerator * b.numerator, this.denominator * b.denominator);
              Rational temp = new Rational(this.numerator * b.numerator, this.denominator * b.denominator); //该数和b相乘
      
              return temp;
          }
      
          //除法
          public Rational divides(Rational b) {
              Rational temp = new Rational(b.denominator, b.numerator);//除以一个数,等于乘以这个数的倒数。
              this.times(temp);
              return temp;
          }
      
          public int getNumerator() {
              return numerator;
          }
      
          public int getDenominator() {
              return denominator;
          }
      
      
          //加法溢出判断
          public static void addExact(int x, int y) {
              int r = x + y;
              assert (!(((x ^ r) & (y ^ r)) < 0)) : "加法溢出";
      
          }
      
          //减法溢出判断
          public static void subtractExact(int x, int y) {
              int r = x - y;
      
              assert (!(((x ^ y) & (x ^ r)) < 0)):"减法溢出";
          }
      
          //乘法溢出判断
          public static void multiplyExact(int x, int y) {
              long r = (long) x * (long) y;
              assert (!((int) r != r)):"乘法溢出";
          }
      
      
      
          @Override
          public String toString() {
              if (denominator == 1) return numerator + "";
              else return numerator + "/" + 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) {
              Scanner input = new Scanner(System.in);
              int nume = input.nextInt();
              int deno = input.nextInt();
              int nume2 = input.nextInt();
              int deno2 = input.nextInt();
              Rational a = new Rational(nume, deno);
              Rational b = new Rational(nume2, deno2);
              Rational c = new Rational(1, 3);
              //2147483647 最大,最小:-2147483648
              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));
          }
      
      
      }

      参考资料

      [1] 维基百科:断言

    • 0
    • 0
    • 1.4k
    • 单栏布局 侧栏位置: