diff options
| author | James Smith <baggy@baggy.me.uk> | 2021-06-17 23:57:57 +0100 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-06-17 23:57:57 +0100 |
| commit | 8cf30ac3764b883497c91bb47806a787ea3ee22a (patch) | |
| tree | 6061b617455de9aa8871e6f303ad587d31bf1d81 | |
| parent | 5a25295151e8217c1e312fddac1b127eaf607747 (diff) | |
| download | perlweeklychallenge-club-8cf30ac3764b883497c91bb47806a787ea3ee22a.tar.gz perlweeklychallenge-club-8cf30ac3764b883497c91bb47806a787ea3ee22a.tar.bz2 perlweeklychallenge-club-8cf30ac3764b883497c91bb47806a787ea3ee22a.zip | |
Update README.md
| -rw-r--r-- | challenge-117/james-smith/README.md | 16 |
1 files changed, 14 insertions, 2 deletions
diff --git a/challenge-117/james-smith/README.md b/challenge-117/james-smith/README.md index aa4a62c493..84b19d8bef 100644 --- a/challenge-117/james-smith/README.md +++ b/challenge-117/james-smith/README.md @@ -72,8 +72,14 @@ sub schroder_cache_array { } ``` -But as we've said before recursion is a curse - so to remove the function -overhead of recursion we can re-write this like this: +But as we've said before recursion is a curse - but we notice that +``` + T0,m = 1 + Tn,0 = Tn-1,0 + Tn-1,1 + Tn,m = Tn-1,m + Tn-1,m+1 + Tn,m-1 +``` +We can use that to define each row of a triangle with `Sn` as the last +value. ```perl sub schroder_non_recursive { @@ -88,6 +94,12 @@ sub schroder_non_recursive { } ``` +We again use the row "flip" as we only need one row and the previous +one to get values... + +There is a faster solution - in that the Scrhoder numbers can be +written as a recurrence relation: + ```perl sub schroder_recurrence_rel { my( $size, @S ) = ( shift, 1, 2 ); |
