习题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] 百度百科：公倍数
请登录之后再进行评论