Maximum triangle path sum: Difference between revisions
→{{Header|Fortran}}: Oh, very well. A method of lesser brutality.
(→{{Header|FreeBASIC}}: Add Fortran) |
(→{{Header|Fortran}}: Oh, very well. A method of lesser brutality.) |
||
Line 476:
This being Fortran, why not a brute-force scan of all possible paths? This is eased by noting that from a given position, only two numbers are accessible, and always two numbers. Just like binary digits. So, for three levels, the choices would be 000, 001, 010, 011, 100, 101, 110, 111 or somesuch. Since however the pinnacle of the pyramid is always chosen, there is no choice there so the digits would be 100, 101, 110,111.
A triangular array can be defined in some languages, and in some circumstances a square array is used with a lower triangle and upper triangle partition, but here, a simple linear array is in order, with some attention to subscript usage. The first layer has one number, the second has two, the third has three, ... easy enough. The more refined method that determines the maximum sum without ascertaining the path through working upwards from the base employs a FOR ALL statement in adding the maximum of the two possible descendants to each brick the current layer, employing array BEST that starts off with all the values of the bottom layer. As each layer is one value shorter than the one below and the expression computes <code>BEST(i) = ... + MAX(BEST(i),BEST(i + 1))</code> the special feature of the FORALL statement, that ''all'' rhs expressions are evaluated before ''any'' results are placed on the lhs is not needed if a DO-loop were used instead.
For input, free-format is convenient. Bad input still is a problem, and can lead to puzzles. If say when N values are to be read but an input line is short of numbers, then additional lines will be read and confusion is likely. So, read the file's record into a text variable and then extract the expected N values from that. Should a problem arise, then the troublesome record can be shown.
Line 568:
WRITE (6,*) WS," is the highest score." !So much for that.
END SUBROUTINE TRAVERSE !All paths considered...
SUBROUTINE REFINE !Ascertain the highest score without searching.
INTEGER BEST(LAYERS) !A scratchpad.
INTEGER I,L !Steppers.
L = LAYERS*(LAYERS - 1)/2 + 1 !Finger the first brick of the lowest layer.
BEST = BRICK(L:L + LAYERS - 1)!Syncopation. Copy the lowest layer.
DO L = LAYERS - 1,1,-1 !Work towards the peak.
FORALL (I = 1:L) BEST(I) = BRICK(L*(L - 1)/2 + I) !Add to each brick's value
1 + MAXVAL(BEST(I:I + 1)) !The better of its two possibles.
END DO !On to the next layer.
WRITE (6,*) BEST(1)," is the highest score. By some path."
END SUBROUTINE REFINE !Who knows how we get there.
END MODULE PYRAMIDS
Line 574 ⟶ 586:
c CALL IMHOTEP("Sakkara.txt")
CALL IMHOTEP("Cheops.txt")
CALL TRAVERSE !Do this the definite way.
CALL REFINE !Only the result by more cunning.
END
</lang>
Line 660 ⟶ 673:
Score 55 94 95 77 97 7 48 72 76 83 64 90 48 80 84 85 94 71
1320 is the highest score.
1320 is the highest score. By some path.
</pre>
| |||