Write a program that computes numbers in the fibonacci sequence. This sequence is defined recursively as follows:
That is, the zeroth Fibonacci number is zero and the first Fibonacci number is one. Other Fibonacci numbers are given by the sum of its two predecessors.
The first 10 numbers in the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21 and 34.
Input will consist of several lines, each with a single integer n indicating the position in the Fibonacci sequence.
0 ≤ n ≤ 42
For each line of input, output should contain a line with a corresponding number Fₙ indicating the Fibonacci number in position n.
3
8
6
2
21
8
fibonacci
functionYour program should contain a fibonacci
function
that takes an integer and returns an integer.
Please refer to the information for your chosen language:
int fibonacci(int n)
fibonacci :: Int -> Int
def fibonacci(n):
int fibonacci(int n)
public static int Fibonacci(int n)
inside a public class Program
public static int fibonacci(int n)
inside a public class Fibonacci
function fibonacci(n)
function fibonacci (n)
def factorial(n)
Your function is expected to have good performance. The maximum expected complexity is O(n).
Specifically for this exercise when using Python, JavaScript, Lua or Ruby,
avoid using sys.exit()
, process.exit()
, os.exit()
or exit
,
as your program is appended with some extra assertions in one of the test sets.
fibonacci
functiontry first: factorial fibonacci1
try next: index-string
Copyright © 2020-2022 Rudy Matela
All rights reserved