Help Project Triangles
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:
5 // This triangle has 5 rows
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
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.
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:
5 // This triangle has 5 rows
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
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.
Last edited on
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. |
| Can you give me the code to help me easier understand, please? |
This is not a free Homework service.
@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.
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.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
( 0, 0) - 7
( 1, 0) - 3
( 2, 0) - 8
( 3, 1) - 7
( 4, 1) - 5
Best sum is 30
7
3 -
8 - -
- 7 - -
- 5 - - - |
Last edited on
Topic archived. No new replies allowed.