《算法第四版》课后练习题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] 维基百科：断言