Sequence Generation – Iterative
Problem
Given the following sequence of integer numbers:
1 |
1 1 2 3 5 8 13 21 34 55 89 ... |
Write a function that receives the index of a given number in the sequence above and returns the corresponding sequence number for example if index = 2 the function should return 2, if the index = 5 the function should return 8 and so on
Solution
The first two elements in the sequence are the base case in the solution. If index is 0 or 1 we just return 1 otherwise we loop starting from 2 stopping at the given index while adding the previous two elements in the sequence. At the end we return the sum. Please refer to the code below for more details. By the way I did not mention that this is the Fibonacci series on purpose because one might copy and paste the solution from memory.
Code
Here is the code in Perl
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 |
#!/usr/bin/perl # Print the first 11 elements of the sequence for ($k = 0; $k <= 10; $k++) { print &Sequence($k) . " "; } # Given an index print the corresponding # sequence number sub Sequence { # Pass index number my ($index) = @_; # Base case if ($index == 0 || $index == 1) { return 1; } # Those variables are gonna slide # to the right starting with 1, 1 $x = 1; $y = 1; for ($i = 2; $i <= $index; $i++) { # Save the sum before altering the values of x and y $s = $x + $y; # Slide to the right $x = $y; $y = $s; } # Return the sum return $s; } |