The Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and are characterised by the fact that every number after the first two is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 114, … etc.
By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two. We define Fib(0)=0, Fib(1)=1, Fib(2)=1, Fib(3)=2, Fib(4)=3, etc. The first 22 Fibonacci numbers given below:
Fib(0) Fib(1) Fib(2) Fib(3) Fib(4) Fib(5) Fib(6) Fib(7) Fib(8) Fib(9) Fib(10)
0 1 1 2 3 5 8 13 21 34 55
Fib(11) Fib(12) Fib(13) Fib(14) Fib(15) Fib(16) Fib(17) Fib(18) Fib(19) Fib(20) Fib(21)
89 144 233 377 610 987 1597 2584 4181 6765 10946
Write a MARIE program to calculate Fib(n), where the user inputs n. For example, if the user inputs 7, the program outputs the value 13; if the user inputs 15, the program outputs the value 610; if the user inputs 20, the program outputs the value 6765 and so on. You need to write and run the program using MARIE simulator. Please include appropriate comments to make your code readable
Answers
In mathematics, the Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence, characterized by the fact that every number after the first two is the sum of the two preceding ones:
{\displaystyle 1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots \;} {\displaystyle 1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots \;}
or (often, in modern usage):
{\displaystyle 0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots \;} {\displaystyle 0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots \;}
The Fibonacci sequence is named after Leonardo Fibonacci. His 1202 book Liber Abaci introduced the sequence to Western European mathematics, although the sequence had been described earlier in Indian mathematics. Fibonacci numbers are intimately connected with the golden ratio.