Fibonacci

From Software Engineers Wiki
Jump to: navigation, search

Contents

Answer #1: Using recursion

unsigned int fibonacci(unsigned int n)
{
        if (n == 0)
                return 0;
        else if (n == 1)
                return 1;
        else
                return fibonacci(n - 1) + fibonacci(n - 2);

}

Answer #2: Without using recursion

unsigned int fibonacci(unsigned int n)
{
        if (n <= 1)
                return n;
        else {
                unsigned int minus1 = 1, minus2 = 0;
                unsigned int cur;
                unsigned int i;

                for (i = 2; i <= n; ++i) {
                        cur = minus1 + minus2;
                        minus2 = minus1;
                        minus1 = cur;
                }

                return cur;
        }
}

In Python,

def fibonacci(num):
        if num < 0:
                return -1
        elif num == 0:
                return 0
        elif num == 1:
                return 1

        minus_2 = 0
        minus_1 = 1
        cur_num = 1
        fibo = 1

        while cur_num < num:
                fibo = minus_1 + minus_2
                minus_2 = minus_1
                minus_1 = fibo
                cur_num += 1

        return fibo

def main():
        for i in range(0, 11):
                print("Fibonacci({}) = {}".format(i, fibonacci(i)))

main()

Answer #3: Without using recursion, overflow detection, C

#include <errno.h>

int fibonacci(unsigned int n, unsigned int *result)
{
        if (n <= 1) {
                *result = n;
                return 0;
        } else {
                unsigned int minus1 = 1, minus2 = 0;
                unsigned int cur;
                unsigned int i;

                for (i = 2; i <= n; ++i) {
                        cur = minus1 + minus2;
                        if (cur < minus1)
                                return -EOVERFLOW;
                        minus2 = minus1;
                        minus1 = cur;
                }

                *result = cur;
                return 0;
        }
}

Answer #4: Without using recursion, overflow detection, C++

#include <stdexcept>
#include <climits>

unsigned int fibonacci(unsigned int n)
{
        if (n <= 1) {
                return n;
        } else {
                unsigned int minus1 = 1, minus2 = 0;
                unsigned int cur;
                unsigned int i;

                for (i = 2; i <= n; ++i) {
                        cur = minus1 + minus2;
                        if (cur < minus1) {
                                throw std::overflow_error("Overflow in fibonacci()");
                                return UINT_MAX;
                        }
                        minus2 = minus1;
                        minus1 = cur;
                }

                return cur;
        }
}
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox