Sequence Generation – Iterative

Problem

Given the following sequence of integer numbers:

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. #!/usr/bin/perl
  2.  
  3. # Print the first 11 elements of the sequence
  4. for ($k = 0; $k <= 10; $k++)
  5. {
  6. print &Sequence($k) . " ";
  7. }
  8.  
  9. # Given an index print the corresponding
  10. # sequence number
  11. sub Sequence
  12. {
  13. # Pass index number
  14. my ($index) = @_;
  15.  
  16. # Base case
  17. if ($index == 0 || $index == 1)
  18. {
  19. return 1;
  20. }
  21.  
  22. # Those variables are gonna slide
  23. # to the right starting with 1, 1
  24. $x = 1;
  25. $y = 1;
  26.  
  27. for ($i = 2; $i <= $index; $i++)
  28. {
  29. # Save the sum before altering the values of x and y
  30. $s = $x + $y;
  31.  
  32. # Slide to the right
  33. $x = $y;
  34. $y = $s;
  35. }
  36.  
  37. # Return the sum
  38. return $s;
  39. }
Tags:

Leave a Reply