• 中文
    • English
  • 注册
  • 查看作者
  • 《算法第四版》课后练习题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
  • 0
  • 4k
  • 请登录之后再进行评论

    登录
    单栏布局 侧栏位置: