blob: 57f66a430a744bea6f498fb4a7d5a485eff68e07 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
#!/usr/bin/env perl
use strict;
use warnings;
use feature qw{ say postderef signatures state };
no warnings qw{ experimental };
use JSON;
use List::Util qw{ sum0 uniq };
my $json = JSON->new->pretty->canonical;
my @examples = qw{16 9 15};
for my $n (@examples) {
my @o = solve_task($n);
my $o = scalar @o;
my $oo = join ",\n ", map { ($_) } @o;
say <<"END";
Input: \$n = $n
Output: $o
$oo
END
}
sub solve_task ($n) {
my @fib = grep { $_ < $n } map { fib($_) } 1 .. $n;
my @sequences = recursion( $n, \@fib );
return @sequences;
}
# Let's call it what it is
sub recursion ( $n, $ref, $x = [] ) {
my @output;
my $depth = 1 + scalar $x->@*;
my $sum = sum0 $x->@*;
my $nex->@* = sort $ref->@*;
return undef if $sum > $n;
if ( $sum == $n ) {
$x->@* = sort { $a <=> $b } map { int $_ } $x->@*;
my $answer = join ' + ', $x->@*;
return $answer;
}
for my $i ( 1 .. scalar $nex->@* ) {
my $v = shift $nex->@*;
my $y->@* = $x->@*;
push $y->@*, $v;
my @return = recursion( $n, $nex, $y );
push @output, @return;
push $nex->@*, $v;
}
return uniq sort grep { defined } @output;
}
sub fib ($n) {
state $fib;
$fib->{0} = 1;
$fib->{1} = 1;
if ( $fib->{$n} ) {
return $fib->{$n};
}
$fib->{$n} = fib( $n - 1 ) + fib( $n - 2 );
}
|
