The weekly challenge 361 - Task 1: Zeckendorf Representation

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-361/#TASK1
 3 #
 4 # Task 1: Zeckendorf Representation
 5 # =================================
 6 #
 7 # You are given a positive integer (<= 100).
 8 #
 9 # Write a script to return Zeckendorf Representation of the given integer.
10 #
11 ### Every positive integer can be uniquely represented as sum of
12 ### non-consecutive Fibonacci numbers.
13 #
14 ## Example 1
15 ##
16 ## Input: $int = 4
17 ## Output: 3,1
18 ##
19 ## 4 => 3 + 1 (non-consecutive fibonacci numbers)
20 #
21 #
22 ## Example 2
23 ##
24 ## Input: $int = 12
25 ## Output: 8,3,1
26 ##
27 ## 12 => 8 + 3 + 1
28 #
29 #
30 ## Example 3
31 ##
32 ## Input: $int = 20
33 ## Output: 13,5,2
34 ##
35 ## 20 => 13 + 5 + 2
36 #
37 #
38 ## Example 4
39 ##
40 ## Input: $int = 96
41 ## Output: 89,5,2
42 ##
43 ## 96 => 89 + 5 + 2
44 #
45 #
46 ## Example 5
47 ##
48 ## Input: $int = 100
49 ## Output: 89,8,3
50 ##
51 ## 100 => 89 + 8 + 3
52 #
53 ############################################################
54 ##
55 ## discussion
56 ##
57 ############################################################
58 #
59 # We precalculate the necessary fibonacci numbers. Then we start
60 # at the higher end, and remove the biggest possible fibonacci number,
61 # skip one of the numbers, and continue there, until the remainder
62 # is zero.
63 
64 use v5.36;
65 
66 zeckendorf_representation(4);
67 zeckendorf_representation(12);
68 zeckendorf_representation(20);
69 zeckendorf_representation(96);
70 zeckendorf_representation(100);
71 
72 sub zeckendorf_representation($int) {
73     say "Input: $int";
74     my @fib = fib(100);
75     my $i = $#fib;
76     my @elems = ();
77     while($fib[$i] > $int) {
78         $i--;
79         if($fib[$i] <= $int) {
80             push @elems, $fib[$i];
81             $int -= $fib[$i];
82             last if $int == 0;
83             $i--;
84         }
85     }
86     say "Output: (" . join(", ", @elems) . ")";
87 }
88 
89 sub fib($max) {
90     my @numbers = (1, 1);
91     my $i = 1;
92     while($numbers[$i] < $max) {
93         push @numbers, $numbers[$i-1] + $numbers[$i];
94         $i++;
95     }
96     return @numbers;
97 }