UVa 10268: 498-bis

UVa 10268: 498-bis

Written by on 24 May 2012

Topics: UVa Online Judge

Problem 10268 at the UVa Online Judge, 498′, asks us to evaluate the derivative of a polynomial. It is, like the name suggests, a version of problem 498, which we’ve already covered here. We solved problem 498 with code reuse in mind. We created a Polynomial class which we can extend to solve this problem.

Interpretation

The problem can basically be split up into three parts: input parsing, computing the derivative of a polynomial and evaluating a polynomial. The input parsing and polynomial evaluation can be reused from problem 498, so we’ll jump straight to computing the derivative.

Computing the derivative of arbitrary functions seems like a hard task, but in this problem we’re only dealing with polynomials. That is a much simpler task. Don’t worry if you don’t know how to compute derivatives, since the formula for computing the derivative of a polynomial is given in the problem statement. If we have the polynomial:

then its derivative is:

Implementation

With that formula given, its really just a matter of plugging the correct values into the correct places. If we add a getDerivative method to the Polynomial class, it could look something like this:

public Polynomial getDerivative() {
	
	// create the derivative polynomial
	// it has a degree one lower than the current polynomial
	Polynomial der = new Polynomial(getDegree() - 1);

	// loop through all the coefficients of the current polynomial, except the last one
	for (int i = getDegree(); i >= 1; i--) {

		// the differentiated constant will be (the power of x, i) * (the old coefficient at x^i)
		// and it will be at x^(i - 1)
		der.set(i - 1, i * get(i));
	}

	return der;
}

That’s all we need to get the derivative of the polynomial.

Differentiation (computing the derivative) and integration (nearly the opposite of computing derivatives) are two fundamental operations in calculus. If you don’t know how to differentiate or integrate, I suggest you take a look at the calculus playlist at Khan Academy. It might come in handy in later Project Euler problems, for example when we need to maximize a function.

The last thing we need to do is to create the main method. It just so happens that it’s really similar to the one at problem 498, so I won’t post it here. You can still find it in the complete source code below.

Conclusion

Problem 10268 was short and simple, but we had already finished most of the work in problem 498. It was just a matter of plugging values into a formula to get the derivative of the polynomial, and we were finished.

The complete source code for today’s problem can be found here.

Do you have some sort of a code library to solve problems faster? Or do you simply rewrite the whole code when you need it? Leave a comment and let us know.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.