diff options
| -rw-r--r-- | 076.pl | 237 |
1 files changed, 237 insertions, 0 deletions
@@ -0,0 +1,237 @@ +#!/usr/bin/env perl +use strict; +use warnings; +use 5.020; +use experimental 'signatures'; + +my %memoize; + +sub sub_combinations($n, $max_val = $n) { + return 1 if $n == 0; + + my $key = "$n,$max_val"; + return $memoize{$key} if $memoize{$key}; + + my $combinations = 0; + for my $i (reverse 1..$n) { + next if $i > $max_val; + $combinations += __SUB__->($n - $i, $i); + } + $memoize{$key} = $combinations; + $combinations; +} + +for my $i (2..100) { + say "$i: " . (sub_combinations($i) - 1); +} + +__END__ + +# 1 1 2 3 5 8 13 21 34 55 +# 1 3 6 10 15 21 28 36 45 55 + +# 1: 0 ( ) ( ) +# 2: 1 ( 1) ( 1) +# 3: 2 ( 1+ 1) ( 1+ 1) +# 4: 4 ( 2+ 1+ 1) ( 1+ 2+ 1) +# 5: 6 ( 2+ 2+ 1+ 1) ( 1+ 2+ 2+ 1) +# 6: 10 ( 3+ 3+ 2+ 1+ 1) ( 1+ 2+ 3+ 3+ 1) +# 7: 14 ( 3+ 4+ 3+ 2+ 1+ 1) ( 1+ 2+ 3+ 4+ 3+ 1) +# 8: 21 ( 4+ 5+ 5+ 3+ 2+ 1+ 1) ( 1+ 2+ 3+ 5+ 5+ 4+ 1) +# 9: 29 ( 4+ 7+ 6+ 5+ 3+ 2+ 1+ 1) ( 1+ 2+ 3+ 5+ 6+ 7+ 4+ 1) +# 10: 41 ( 5+ 8+ 9+ 7+ 5+ 3+ 2+ 1+ 1) ( 1+ 2+ 3+ 5+ 7+ 9+ 8+ 5+ 1) +# 11: 54 ( 5+10+10+10+ 7+ 5+ 5+ 2+ 1+ 1) ( 1+ 2+ 3+ 5+ 7+ 9+11+11+ 6+ 1) +# +# 1 1 +# +# 2 1 +# 1 1 1 +# +# 3 1 +# 2 2 +# 2 1 1 +# 1 1 1 1 +# +# 4 1 +# 3 2 +# 3 1 1 +# 2 2 1 +# 2 1 1 1 +# 1 1 1 1 1 +# +# 5 1 +# 4 2 +# 4 1 1 +# 3 3 +# 3 2 1 +# 3 1 1 1 +# 2 2 2 +# 2 2 1 1 +# 2 1 1 1 1 +# 1 1 1 1 1 1 +# +# 6 1 +# 5 2 +# 4 3 +# 5 1 1 +# 4 2 1 +# 3 3 1 +# 3 2 2 +# 4 1 1 1 +# 3 2 1 1 +# 2 2 2 1 +# 3 1 1 1 1 +# 2 2 1 1 1 +# 2 1 1 1 1 1 +# 1 1 1 1 1 1 1 +# +# 7 1 +# 6 2 +# 5 3 +# 4 4 +# 6 1 1 +# 5 2 1 +# 4 3 1 +# 4 2 2 +# 3 3 2 +# 5 1 1 1 +# 4 2 1 1 +# 3 3 1 1 +# 3 2 2 1 +# 2 2 2 2 +# 4 1 1 1 1 +# 3 2 1 1 1 +# 2 2 2 1 1 +# 3 1 1 1 1 1 +# 2 2 1 1 1 1 +# 2 1 1 1 1 1 1 +# 1 1 1 1 1 1 1 1 +# +# 8 1 +# 7 2 +# 6 3 +# 5 4 +# 7 1 1 +# 6 2 1 +# 5 3 1 +# 5 2 2 +# 4 4 1 +# 4 3 2 +# 3 3 3 +# 6 1 1 1 +# 5 2 1 1 +# 4 3 1 1 +# 4 2 2 1 +# 3 3 2 1 +# 3 2 2 2 +# 5 1 1 1 1 +# 4 2 1 1 1 +# 3 3 1 1 1 +# 3 2 2 1 1 +# 2 2 2 2 1 +# 4 1 1 1 1 1 +# 3 2 1 1 1 1 +# 2 2 2 1 1 1 +# 3 1 1 1 1 1 1 +# 2 2 1 1 1 1 1 +# 2 1 1 1 1 1 1 1 +# 1 1 1 1 1 1 1 1 1 +# +# 9 1 +# 8 2 +# 8 1 1 +# 7 3 +# 7 2 1 +# 7 1 1 1 +# 6 4 +# 6 3 1 +# 6 2 2 +# 6 2 1 1 +# 6 1 1 1 1 +# 5 5 +# 5 4 1 +# 5 3 2 +# 5 3 1 1 +# 5 2 2 1 +# 5 2 1 1 1 +# 5 1 1 1 1 1 +# 4 4 2 +# 4 4 1 1 +# 4 3 3 +# 4 3 2 1 +# 4 3 1 1 1 +# 4 2 2 2 +# 4 2 2 1 1 +# 4 2 1 1 1 1 +# 4 1 1 1 1 1 1 +# 3 3 3 1 +# 3 3 2 2 +# 3 3 2 1 1 +# 3 3 1 1 1 1 +# 3 2 2 2 1 +# 3 2 2 1 1 1 +# 3 2 1 1 1 1 1 +# 3 1 1 1 1 1 1 1 +# 2 2 2 2 2 +# 2 2 2 2 1 1 +# 2 2 2 1 1 1 1 +# 2 2 1 1 1 1 1 1 +# 2 1 1 1 1 1 1 1 1 +# 1 1 1 1 1 1 1 1 1 1 +# +# 10 1 +# 9 2 +# 8 3 +# 7 4 +# 6 5 +# 9 1 1 +# 8 2 1 +# 7 3 1 +# 7 2 2 +# 6 4 1 +# 6 3 2 +# 5 5 1 +# 5 4 2 +# 5 3 3 +# 4 4 3 +# 8 1 1 1 +# 7 2 1 1 +# 6 3 1 1 +# 6 2 2 1 +# 5 4 1 1 +# 5 3 2 1 +# 4 4 2 1 +# 4 3 3 1 +# 4 3 2 2 +# 3 3 3 2 +# 7 1 1 1 1 +# 6 2 1 1 1 +# 5 3 1 1 1 +# 5 2 2 1 1 +# 4 4 1 1 1 +# 4 3 2 1 1 +# 4 2 2 2 1 +# 3 3 3 1 1 +# 3 3 2 2 1 +# 3 2 2 2 2 +# 6 1 1 1 1 1 +# 5 2 1 1 1 1 +# 4 3 1 1 1 1 +# 4 2 2 1 1 1 +# 3 3 2 1 1 1 +# 3 2 2 2 1 1 +# 2 2 2 2 2 1 +# 5 1 1 1 1 1 1 +# 4 2 1 1 1 1 1 +# 3 3 1 1 1 1 1 +# 3 2 2 1 1 1 1 +# 2 2 2 2 1 1 1 +# 4 1 1 1 1 1 1 1 +# 3 2 1 1 1 1 1 1 +# 2 2 2 1 1 1 1 1 +# 3 1 1 1 1 1 1 1 +# 2 2 1 1 1 1 1 1 +# 3 1 1 1 1 1 1 1 1 +# 2 2 1 1 1 1 1 1 1 +# 2 1 1 1 1 1 1 1 1 1 +# 1 1 1 1 1 1 1 1 1 1 1 |