aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJames Smith <baggy@baggy.me.uk>2021-06-17 23:57:57 +0100
committerGitHub <noreply@github.com>2021-06-17 23:57:57 +0100
commit8cf30ac3764b883497c91bb47806a787ea3ee22a (patch)
tree6061b617455de9aa8871e6f303ad587d31bf1d81
parent5a25295151e8217c1e312fddac1b127eaf607747 (diff)
downloadperlweeklychallenge-club-8cf30ac3764b883497c91bb47806a787ea3ee22a.tar.gz
perlweeklychallenge-club-8cf30ac3764b883497c91bb47806a787ea3ee22a.tar.bz2
perlweeklychallenge-club-8cf30ac3764b883497c91bb47806a787ea3ee22a.zip
Update README.md
-rw-r--r--challenge-117/james-smith/README.md16
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 );