Palabra de Fibonacci

Como los números de Fibonacci , una palabra de Fibonacci . es una secuencia específica de dígitos binarios (o símbolos de cualquier alfabeto de dos letras). La palabra de Fibonacci se forma por concatenación repetida de la misma manera que los números de Fibonacci se forman por suma repetida. Pero a diferencia del número de Fibonacci, la palabra de Fibonacci tiene sus dos primeros términos diferentes entre sí. 

In Fibonacci word,
  S(0) = 0, 
  S(1) = 01, 
  S(2) = 010,
  S(3) = 01001
   ..... 
where S(n) = S(n-1) + S(n-2) and + 
represents the concatenation of 
strings. 

La tarea es encontrar la enésima palabra de Fibonacci para un número dado n.

Ejemplos: 

Input : n = 4
Output : S(4) = 01001010

Input : n = 2
Output : S(2) = 010

Al igual que en el programa del número de Fibonacci, usamos el concepto iterativo de encontrar el n-ésimo número de Fibonacci aquí para encontrar la n-ésima palabra de Fibonacci podemos usar el concepto iterativo. Entonces, para encontrar la n-ésima palabra de Fibonacci, tomaremos dos strings Sn y Sn_1 que representan S(n) y S(n-1) respectivamente y en cada iteración actualizaremos tmp = Sn, Sn = Sn + Sn_1 y Sn_1 = tmp de esta forma podemos encontrar la enésima palabra de fibonacci.

Implementación:

// program for nth Fibonacci word
#include<bits/stdc++.h>
using namespace std;
 
// Returns n-th Fibonacci word
string fibWord(int n)
{
    string Sn_1 = "0";
    string Sn = "01";
    string tmp;
    for (int i=2; i<=n; i++)
    {
        tmp = Sn;
        Sn += Sn_1;
        Sn_1 = tmp;
    }
 
    return Sn;
}
 
// driver program
int main()
{
    int n = 6;
    cout << fibWord(n);
    return 0;
}

// Java program for nth Fibonacci word
import java.util.*;
 
class Eulerian
{
    // Returns n-th Fibonacci word
    public static String fibWord(int n)
    {
        String Sn_1 = "0";
        String Sn = "01";
        String tmp;
        for (int i=2; i<=n; i++)
        {
            tmp = Sn;
            Sn += Sn_1;
            Sn_1 = tmp;
        }
 
        return Sn;
    }
     
    // driver code
    public static void main(String[] args)
    {
        int n = 6;
        System.out.print(fibWord(n));
    }
}
 
// This code is contributed by rishabh_jain

# Python3 program for nth Fibonacci word
 
# Returns n-th Fibonacci word
def fibWord(n):
    Sn_1 = "0"
    Sn = "01"
    tmp = ""
    for i in range(2, n + 1):
        tmp = Sn
        Sn += Sn_1
        Sn_1 = tmp
    return Sn
 
# driver program
n = 6
print (fibWord(n))
 
# This code is contributed by Sachin Bisht

// C# program for nth Fibonacci word
using System;
 
class GFG
{
    // Returns n-th Fibonacci word
    public static String fibWord(int n)
    {
        String Sn_1 = "0";
        String Sn = "01";
        String tmp;
        for (int i = 2; i <= n; i++)
        {
            tmp = Sn;
            Sn += Sn_1;
            Sn_1 = tmp;
        }
 
        return Sn;
    }
     
    // Driver code
    public static void Main()
    {
        int n = 6;
        Console.WriteLine(fibWord(n));
    }
}
 
// This code is contributed by vt_m

<script>
 
// program for nth Fibonacci word
 
// Returns n-th Fibonacci word
function fibWord(n)
{
    var Sn_1 = "0";
    var Sn = "01";
    var tmp;
    for (var i = 2; i <= n; i++)
    {
        tmp = Sn;
        Sn += Sn_1;
        Sn_1 = tmp;
    }
 
    return Sn;
}
 
// driver program
var n = 6;
document.write( fibWord(n));
 
// This code is contributed by noob2000.
</script>

010010100100101001010