Catalan numbers/Pascal's triangle: Difference between revisions
m
added comments
m (extra example) |
m (added comments) |
||
Line 768:
p[j] = p1
end for
-- ?p[1..N-i+1]
end for
?catalan</lang>
Line 774 ⟶ 775:
{1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845}
</pre>
Explanatory comments to accompany the above
<lang Phix>-- FreeBASIC said:
--' 1 1 1 1 1 1
--' 1 2 3 4 5 6
--' 1 3 6 10 15 21
--' 1 4 10 20 35 56
--' 1 5 15 35 70 126
--' 1 6 21 56 126 252
--' The Pascal triangle is rotated 45 deg.
--' to find the Catalan number we need to follow the diagonal
--' for top left to bottom right
--' take the number on diagonal and subtract the number in de cell
--' one up and one to right
--' 1 (2 - 1), 2 (6 - 4), 5 (20 - 15) ...
--
-- The first thing that struck me was it is twice as big as it needs to be,
-- something like this would do...
-- 1 1 1 1 1 1
-- 2 3 4 5 6
-- 6 10 15 21
-- 20 35 56
-- 70 126
-- 252
-- It is more obvious from the upper square that the diagonal on that, which is
-- that same as column 1 on this, is twice the previous, which on the second
-- diagram is in column 2. Further, once we have calculated the value for column
-- one above, we can use it immediately to calculate the next catalan number and
-- do not need to store it. Lastly we can overwrite row 1 with row 2 etc in situ,
-- and the following shows what we need for subsequent rounds:
-- 1 1 1 1 1
-- 3 4 5 6
-- 10 15 21
-- 35 56
-- 126 (unused)</lang>
The following bigatom version is over ten times faster than the equivalent on [[Catalan_numbers#Phix|Catalan_numbers]]
<lang Phix>include builtins\bigatom.e
| |||