blob: b39028c5b994eef80afeb7c51b1f0c54f8abc4b0 (
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
|
#!/opt/perl/bin/perl
#
# Exercise:
# You are given a positive integer $N.
# Write a script to find out all possible combination of Fibonacci
# Numbers required to get $N on addition.
#
# You are NOT allowed to repeat a number. Print 0 if none found.
#
#
# Note:
# The "Print 0 if none found." is irrelevant. There is always at
# least one way to write any positive integer as a sum of distinct
# Fibonacci Numbers. (Zeckendorf's theorem states: "very positive
# integer can be represented uniquely as the sum of one or more
# distinct Fibonacci numbers in such a way that the sum does not
# include any two consecutive Fibonacci numbers")
#
use 5.032;
use strict;
use warnings;
no warnings 'syntax';
use experimental 'signatures';
use experimental 'lexical_subs';
chomp (my $N = <>);
#
# Create a list of Fibonacci Numbers up to $N. We will start with (1, 2),
# skipping the first two numbers 0 and 1. 0 doesn't add anything, and
# we cannot duplicate numbers, so we just need one 1.
#
my @FIB = (1, 2);
while ($FIB [-1] + $FIB [-2] <= $N) {
push @FIB => $FIB [-1] + $FIB [-2];
}
sub solutions;
#
# Create all solutions for number $target, with all Fibonnaci numbers
# having index $index or above.
#
sub solutions ($target, $index = 0) {
map {
my $fib = $FIB [$_];
$target < $fib ? ()
: $target == $fib ? [$target]
: map {[$fib, @$_]} solutions ($target - $fib, $_ + 1)
} $index .. @FIB - 1;
}
my @all = solutions $N;
local $" = " + ";
say "@$_ = $N" for @all;
__END__
|
