PROBLEM STATEMENT
We all learned how to take integrals of complicated functions like e^(-(x^2))
in our calculus classes (well maybe not that one, but you get the idea). Now
that we have grown older, and lazier, we don't want to have to take integrals
by hand any more, and would like to write a program to do this for us. Your
task is to write a method that will calculate an integral over a given range
and return the result as a fraction. To simplify things, we will only consider
polynomial functions with all exponents greater than or equal to 0.
For those of you who have forgotten how to do take integrals, you will need the
following basic rules:
Integral(i*x^j + k*x^m) = Integral(i*x^j) + Integral(k*x^m), for arbitrary
constants i, j, k, and m. In other words, the integral of the sum of two or
more components is equal to the sum of the integrals of the individual
components.
Integral(i*x^j) = (i/(j+1))*x^(j+1), for arbitrary constants i, and j.
Now, to evaluate an integral in the range a to b, we calculate the integral,
and evaluate the function at x = a and x = b, and subtract the value at x = a
from the value at x = b.
Thus, the integral of 5x^0 + 3x^2 is 5x^1 + 1x^3
To evaluate this in the range a = 3 to b = 6 we first evaluate the above result
at x = 6: 5*6^1 + 1*6^3 = 30 + 216 = 246
We then evaluate the integral at x = 3: 5*3^1 + 1*3^3 = 15 + 27 = 42
246 - 42 = 204
In addition to calculating the integral, we must also return the result as a
fraction (see examples). To do this, there will be occasions when we need to
find the least common multiple of two numbers. This can be done by multiplying
the two numbers together, and dividing the product by the greatest common
divisor (GCD) of the two numbers. Code to find the GCD of two POSITIVE
integers has been provided.
DEFINITION
Class Name: Integrate
Method Name: compute
Parameters: String, int, int
Returns: String
Method Signature (be sure your method is public): String compute(String
expression, int a, int b)
NOTES
- Returned values must be reduced as much as possible such that the numerator
and denominator have no common factor other than 1
- 0 should be returned as "0/1"
- Negative numbers must be returned with a '-' as the first character in the
String
TopCoder will ensure that:
- b is greater than or equals to a, and both a and b are in the range -10 to
10, inclusive.
- The expression has no extra leading 0's or spaces and is less than or equal
to 50 characters in length.
- All coefficients (the <num> preceding 'x') are in the range 0 to 9, inclusive.
- All exponents are in the range 0 to 4, inclusive.
- All terms will be formatted as "<num>x^<num>" where <num> is an integer
(quotes and angle brackets are for clarity only.
- There will be a " + " between every pair of adjacent terms.
- There will be at least one term in the expression.
EXAMPLES
1. expression = "1x^1 + 1x^2", a = 0, b = 1:
First we evaluate the integral to (1/2)x^2 + (1/3)x^3. We then evaluate this
at x = 1, 1/2 + 1/3 and at x = 0, 0 + 0.
So, our final result is 1/2 + 1/3. To combine these we must transform them so
that they have the same denominator. Doing this, we get 3/6 + 2/6, at which
point we can simply add the numerators and return "5/6".
2. expression = "1x^1 + 1x^2", a = 1, b = 4
We get the same integral as above, and evaluate it at 1 and 4 to get: 1/2 + 1/3
and 16/2 + 64/3, respectively. Subtracting the first from the second, we get
15/2 + 63/3. Again we see that we must transform the denominator such that
they are both 6. Doing this we get: 45/6 + 126/6 = 171/6. However this is not
in its most simplified form because both the numerator and denominator are
divisible by 3. Dividing both numerator and denominator by 3, we end up with
57/2 and thus return "57/2".
3. expression = "0x^4 + 0x^1", a = -10, b = -10
Since the expression is clearly 0, the integral is also 0, and thus the result
is 0, so we return "0/1".
4. expression = "1x^2 + 2x^2", a = -1, b = 3
The integral evaluates to 1x^3. At x = 3, this is 27. At x = -1, this is -1.
27 - (-1) = 28
returns "28/1"
5. expression = "1x^3 + 2x^1", a = -10, b = 0
returns "-2600/1"
6. expression = "1x^0 + 1x^1 + 1x^2 + 1x^3 + 1x^4"
a = 0, b = 3, returns "1707/20"
a = -3, b = 4 returns "20279/60"
a = -10, b = 10 returns "122060/3"