首页 > 代码库 > Twitter OA prepare: Rational Sum
Twitter OA prepare: Rational Sum
In mathematics, a rational number is any number that can be expressed in the form of a fraction p/q , where p & q are two integers, and the denominator q is not equal to zero. Hence, all integers are rational numbers where denominator, in the most reduced form, is equal to 1.You are given a list of N rational number, {a1/b1, a2/b2, ..., aN/bN}. Print the sum ( = a1/b1 + a2/b2 + ... + aN/bN = num/den) in the most reduced form.InputThe first line of input contains an integer, N, the number of rational numbers. N lines follow. ithline contains two space separated integers, ai bi, where aiis the numerator and bi is the denominator for the ith rational number.OutputYou have to print two space separated integers, num den, where num and den are numerator and denominator of the sum respectively.Constraints1 <= N <= 151 <= ai <= 101 <= bi <= 10NotesMake sure the sum displayed as output is in the most reduced form.If sum is an integer, you have to print 1 as denominator.Sample Input44 22 42 42 3Sample Output11 3ExplanationSum is 4/2 + 2/4 + 2/4 + 2/3 = (24 + 6 + 6 + 8)/12 = 44/12 = 11/3. So you have to print "11 3", which is the most reduced form.
Below is the syntax highlighted version of Rational.java from §9.2 Symbolic Methods. 摘自http://introcs.cs.princeton.edu/java/92symbolic/Rational.java.html
1 /************************************************************************* 2 * Compilation: javac Rational.java 3 * Execution: java Rational 4 * 5 * Immutable ADT for Rational numbers. 6 * 7 * Invariants 8 * ----------- 9 * - gcd(num, den) = 1, i.e, the rational number is in reduced form 10 * - den >= 1, the denominator is always a positive integer 11 * - 0/1 is the unique representation of 0 12 * 13 * We employ some tricks to stave of overflow, but if you 14 * need arbitrary precision rationals, use BigRational.java. 15 * 16 *************************************************************************/ 17 18 public class Rational implements Comparable<Rational> { 19 private static Rational zero = new Rational(0, 1); 20 21 private int num; // the numerator 22 private int den; // the denominator 23 24 // create and initialize a new Rational object 25 public Rational(int numerator, int denominator) { 26 27 // deal with x/0 28 //if (denominator == 0) { 29 // throw new RuntimeException("Denominator is zero"); 30 //} 31 32 // reduce fraction 33 int g = gcd(numerator, denominator); 34 num = numerator / g; 35 den = denominator / g; 36 37 // only needed for negative numbers 38 if (den < 0) { den = -den; num = -num; } 39 } 40 41 // return the numerator and denominator of (this) 42 public int numerator() { return num; } 43 public int denominator() { return den; } 44 45 // return double precision representation of (this) 46 public double toDouble() { 47 return (double) num / den; 48 } 49 50 // return string representation of (this) 51 public String toString() { 52 if (den == 1) return num + ""; 53 else return num + "/" + den; 54 } 55 56 // return { -1, 0, +1 } if a < b, a = b, or a > b 57 public int compareTo(Rational b) { 58 Rational a = this; 59 int lhs = a.num * b.den; 60 int rhs = a.den * b.num; 61 if (lhs < rhs) return -1; 62 if (lhs > rhs) return +1; 63 return 0; 64 } 65 66 // is this Rational object equal to y? 67 public boolean equals(Object y) { 68 if (y == null) return false; 69 if (y.getClass() != this.getClass()) return false; 70 Rational b = (Rational) y; 71 return compareTo(b) == 0; 72 } 73 74 // hashCode consistent with equals() and compareTo() 75 public int hashCode() { 76 return this.toString().hashCode(); 77 } 78 79 80 // create and return a new rational (r.num + s.num) / (r.den + s.den) 81 public static Rational mediant(Rational r, Rational s) { 82 return new Rational(r.num + s.num, r.den + s.den); 83 } 84 85 // return gcd(|m|, |n|) 86 private static int gcd(int m, int n) { 87 if (m < 0) m = -m; 88 if (n < 0) n = -n; 89 if (0 == n) return m; 90 else return gcd(n, m % n); 91 } 92 93 // return lcm(|m|, |n|) 94 private static int lcm(int m, int n) { 95 if (m < 0) m = -m; 96 if (n < 0) n = -n; 97 return m * (n / gcd(m, n)); // parentheses important to avoid overflow 98 } 99 100 // return a * b, staving off overflow as much as possible by cross-cancellation101 public Rational times(Rational b) {102 Rational a = this;103 104 // reduce p1/q2 and p2/q1, then multiply, where a = p1/q1 and b = p2/q2105 Rational c = new Rational(a.num, b.den);106 Rational d = new Rational(b.num, a.den);107 return new Rational(c.num * d.num, c.den * d.den);108 }109 110 111 // return a + b, staving off overflow112 public Rational plus(Rational b) {113 Rational a = this;114 115 // special cases116 if (a.compareTo(zero) == 0) return b;117 if (b.compareTo(zero) == 0) return a;118 119 // Find gcd of numerators and denominators120 int f = gcd(a.num, b.num);121 int g = gcd(a.den, b.den);122 123 // add cross-product terms for numerator124 Rational s = new Rational((a.num / f) * (b.den / g) + (b.num / f) * (a.den / g),125 lcm(a.den, b.den));126 127 // multiply back in128 s.num *= f;129 return s;130 }131 132 // return -a133 public Rational negate() {134 return new Rational(-num, den);135 }136 137 // return a - b138 public Rational minus(Rational b) {139 Rational a = this;140 return a.plus(b.negate());141 }142 143 144 public Rational reciprocal() { return new Rational(den, num); }145 146 // return a / b147 public Rational divides(Rational b) {148 Rational a = this;149 return a.times(b.reciprocal());150 }151 152 153 // test client154 public static void main(String[] args) {155 Rational x, y, z;156 157 // 1/2 + 1/3 = 5/6158 x = new Rational(1, 2);159 y = new Rational(1, 3);160 z = x.plus(y);161 System.out.println(z);162 163 // 8/9 + 1/9 = 1164 x = new Rational(8, 9);165 y = new Rational(1, 9);166 z = x.plus(y);167 System.out.println(z);168 169 // 1/200000000 + 1/300000000 = 1/120000000170 x = new Rational(1, 200000000);171 y = new Rational(1, 300000000);172 z = x.plus(y);173 System.out.println(z);174 175 // 1073741789/20 + 1073741789/30 = 1073741789/12176 x = new Rational(1073741789, 20);177 y = new Rational(1073741789, 30);178 z = x.plus(y);179 System.out.println(z);180 181 // 4/17 * 17/4 = 1182 x = new Rational(4, 17);183 y = new Rational(17, 4);184 z = x.times(y);185 System.out.println(z);186 187 // 3037141/3247033 * 3037547/3246599 = 841/961 188 x = new Rational(3037141, 3247033);189 y = new Rational(3037547, 3246599);190 z = x.times(y);191 System.out.println(z);192 193 // 1/6 - -4/-8 = -1/3194 x = new Rational( 1, 6);195 y = new Rational(-4, -8);196 z = x.minus(y);197 System.out.println(z);198 }199 200 }
Twitter OA prepare: Rational Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。