diff options
| -rw-r--r-- | challenge-117/james-smith/README.md | 18 | ||||
| -rw-r--r-- | challenge-117/james-smith/blog.txt | 1 |
2 files changed, 17 insertions, 2 deletions
diff --git a/challenge-117/james-smith/README.md b/challenge-117/james-smith/README.md index aa4a62c493..07571f0918 100644 --- a/challenge-117/james-smith/README.md +++ b/challenge-117/james-smith/README.md @@ -55,6 +55,8 @@ sub triangle { ### Now the counts... Schroder numbers +*It's amazing what you find out about when you google the answers you get!* + Due to the "memory" storage issues we can change the problem to one of counting rather than listing... The first approach is to just convert the `triangle` method above to count - we introduce a cache as well to improve performance. @@ -72,8 +74,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 +96,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 ); diff --git a/challenge-117/james-smith/blog.txt b/challenge-117/james-smith/blog.txt new file mode 100644 index 0000000000..8d12b20b58 --- /dev/null +++ b/challenge-117/james-smith/blog.txt @@ -0,0 +1 @@ +https://github.com/drbaggy/perlweeklychallenge-club/blob/master/challenge-117/james-smith/ |