When I was a student, lots of my fellow students approached me and asked "Where do you start to solve a computer science problem?" A question could typically be something like "write an algorithm to calculate..." I hope the following will give a good starting point and building block to get you on the road to solving the problem.
Let's work through an example. You get the question to write an algorithm or program to solve "Pascal's Triangle". The question might be something like "The user will enter a row number, and then the program must calculate and display the elements of that row in the Pascal Triangle"
Pascal's triangle is a geometric arrangement of the binomial coefficients in a triangle. In plain English this can be explained as "every number in the triangle is the sum of the two numbers above". The number Zero is always invisible to the left and right of the triangle's edges. To read more about Pascal's Triangle, search for "Pascal's Triangle" in Wikipedia.
Here are the first few rows of Pascal's Triangle: (The triangle starts with Row 0 and each row starts with element 0 from left to right)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Now, to solve this in an algorithm / program, there are always 4 basic ways to approach the problem. The 4 approaches are here listed from generally easiest to advanced, and also generally from worst to best.
1) Hard Coding
2) Iterative
3) Recursive
4) Function
Lets look at all 4:
Hard Coding
The hard-coded solution is a silly solution! Bad programming! To solve the problem with hard coding, we will store each row as a variable/memory structure and then when required, we return that specific row. Only use this method if you are writing an exam and you are seriously running out of time!
Iterative
The iterative approach is in most cases the "model answer". This is generally a good solid solution. The solution is easy to write, and also easy for someone to understand when reading the code.
We will start with hard-coding only the first row. Then we will iterate calculating through the rows until we are at the required row. For Pascal's triangle, our algorithm will loop until the required row. Each subsequent row is calculated by using the values from the previously calculated row.
Recursive
The recursive solution is normally the "higher grade" solution. It is something that is not always understood by students. I used to call this the "job security" solution. Computer Scientists enjoy this solution.
With the recursive solution we will use a function to return each element of the required row. The function will call itself to calculate the answer by calling the same function (recursively). Each time the function is called, it will return "1" if it is the first element of the row, otherwise it will return the sum of the two elements above it.
Function
The Function is normally the best and fasted approach. It could however be very difficult to work out a formula. With a formula we want to say:
f(r,e) = some formula
where r = row number and e = element number.
For Pascal's Triangle there is a formula! nCr or n! / (r! * (n-r)!)
where n = row number and r = element number.
So, our algorithm will call this function with the row- and element numbers as parameters and displayed the return value.
That's it! Problem solved.
Andre Maakal -
http://www.maakal.com/maakaldb.htm
Andre Maakal is a Database Administrator for a Multi-National Mining Company. He has 15+ years experience in the full spectrum of Information- and Telecommunication Technology. He has a Masters degree in Information Technology. His experience includes analysis, design, programming, managing databases, fault finding-and-resolution, performance tuning, pc-, server-, and networking hardware. As a hobby he is actively involved in long-distance running and spends time as a web entrepreneur.
Article Source: http://EzineArticles.com/?expert=Andre_Maakal
Posts
No comments:
Post a Comment