Programming Practice - Problem 1

I recently found the website Project Euler (pronounced like oiler) and have been slightly addicted to it.

Basically Project Euler is a website filled with fun math problems that you can either solve by coding or through pen and paper. It isn't like other programming practice problem websites that require you to submit code to an online judge using standard input and output. Project Euler is simple: they give you a problem and a text box to put the answer in. Once you figure it out you click submit and check if you found the correct answer.

As a basic example I'm going to walk through the first practice problem.
Problem 1 from PE states:
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

My solution used the following java Code.

class p1
public static void main(String [] args)
int sum=0;
for(int i = 0; i < 1000; i++) { if(i%3 == 0 || i%5 == 0) { sum = sum + i; System.out.println(i); } } System.out.println("\n\nThe total is: " + sum); } }

I solved this problem using the basics of divide and conquer programming. Wikipedia defines this as-
In computer science, divide and conquer (D&C) is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

Basically we split the problem into two "subproblems."
1. Find the sum of numbers below 1000.
2. Determine whether a number is a multiple of 3 or 5

For the first part we simply add for(int i = 0; i< 1000; i++) , which lets us walk through the values of 1:1000. Inside of this for loop we test each integer with if(i%3 == 0 || i%5 == 0) to see if it is a multiple of 3 or 5. If it is, we add our number "i" to our variable keeping track of the sums.

Using this method we get the correct answer of: 233168

That wasn't too difficult, now was it? Give Project Euler a try and happy coding!

No comments:

Post a Comment