Posted by: Zeeshan Amjad | April 22, 2014

Fibonacci Word


I came across an interesting concept Fibonacci word. It is formed by repeated concatenation of symbols, usually two alphabets, using the Fibonacci numbers way.

For sample lets start with the symbol “a” and “ab”.

Here are the first few words

F0 = a

F1 = ab

F2 = aba

F3 = abaab

F4 = abaababa

F5 = abaababaabaab

Let’s do this coding but first make a integer version of the program.

Code Snippet
static int[] Fibonacci(int no)
{
    var fib = new int[no];

    fib[0] = 0;
    fib[1] = 1;

    for (var i = 2; i < no; i++)
    {
        fib[i] = fib[i – 1] + fib[i – 2];
    }

    return fib;
}

 

Now let’s make the string version of the program.

Code Snippet
static string[] FibonacciString(int no)
{
    var fib = new string[no];

    fib[0] = "a";
    fib[1] = "b";

    for (var i = 2; i < no; i++)
    {
        fib[i] = fib[i – 1] + fib[i – 2];
    }

    return fib;
}

 

The integer version and the string version of the programs are very similar to each other. Let’s try to make a generic  function. This is our first attempt.

Code Snippet
static T[] Fibonacci<T>(int no)
{
    var fib = new T[no];

    fib[0] = 0;
    fib[1] = 1;

    for (var i = 2; i < no; i++)
    {
        fib[i] = fib[i – 1] + fib[i – 2];
    }

    return fib;
}

 

This program has two problem. First the initialization of the first and second elements of Fibonacci word. It can be easily solved by passing the initial values as a parameter. Here is a modified version of the program.

Code Snippet
static T[] Fibonacci<T>(int no, T first, T second)
{
    var fib = new T[no];

    fib[0] = first;
    fib[1] = second;

    for (var i = 2; i < no; i++)
    {
        fib[i] = fib[i – 1] + fib[i – 2];
    }

    return fib;
}

 

But there is still another problem. There is still a compilation error.

Error    1    Operator ‘+’ cannot be applied to operands of type ‘T’ and ‘T’   

We can solve this problem with the dynamic keyword of C#. We can convert the last and second last item of the Fibonacci word using dynamic keyword before applying the concatenation words.

Here is a modified version of Fibonacci word.

Code Snippet
static T[] FibonacciGeneric<T>(int no, T first, T second)
{
    if (no < 2)
        return null;

    var fib = new T[no];

    fib[0] = first;
    fib[1] = second;

    for (var i = 2; i < no; i++)
    {
        dynamic last = fib[i – 1];
        dynamic secondlast = fib[i – 2];

        fib[i] = last + secondlast;
    }

    return fib;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: