Write a program that calculates the highest sum of numbers passed on
a route that starts at the top and ends somewhere on
the base. Each step can go either diagonally down to
the left or diagonally down to the right. The number
of rows in the triangle is >1 but <=100. The numbers
in the triangle, all integers, are between 0 and 99.
Input Data: Data about the number of rows in the triangle are first read from the input
file. In our example, the input file appears as follows:
Output Data
1. Display the triangle if and only if its size is <= 15, as shown below:
Triangle size = 5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
2. Display the highest sum (30 in our example) and the path (row, column and
value) as shown below.
( 0, 0) - 7
( 1, 0) - 3
( 2, 0) - 8
( 3, 1) - 7
( 4, 1) - 5
===
30
3. (Optional) In addition to the above output, if the number of rows <= 15 display
the path a second time as shown below.
|7|
|3 _|
|8 _ _|
|_ 7 _ _|
|_ 5 _ _ _|
Highest sum = 30.
Algorithm – will be discussed in class.
For each row:
For each element in the row:
Store the better of the two sums from the elements above (and where it came from)
When you get to the last row, take the largest sum you have found for that row and work back for the route.
@Kenst,
there's a difference between "can" and "will".
Start by writing code to read triangle data from file and write it back to screen. That doesn't require much of an algorithm. We can move on when you have done that.