Encuentre el término n de la secuencia de la curva del dragón

Dragon Curve Sequence es una secuencia binaria infinita de 0 y 1. El primer término de la sucesión es 1. 
A partir del siguiente término, insertamos alternativamente 1 y 0 entre cada elemento del término anterior. 
Para entender mejor consulte las siguientes explicaciones:
 

• 1 (comienza con 1) 
   
• “1” 1 “0” 
  1 y 0 se insertan alternativamente a la izquierda y derecha del término anterior. Aquí, el número entre comillas dobles representa los elementos recién agregados.
  Entonces el segundo término se convierte en 
  1 1 0
• “1” 1 “0” 1 “1” 0 “0” 
  Entonces el tercer término se convierte en 
  1 1 0 1 1 0 0 
   
• “1” 1 “0” 1 “1” 0 “0” 1 “1” 1 “0” 0 “1” 0 “0” El cuarto término se convierte en 1 1 0 1 1 0 0 1 1 1 0 0 1 
  0 
  0 
   

Esto también se conoce popularmente como la secuencia regular de plegado de papel . Dado un número natural n, la tarea es encontrar la enésima string formada por la secuencia Dragon Curve de longitud  .
Ejemplos:
 

Input: n = 4
Output: 110110011100100
Explanation:
We get 1 as the first term, 
"110" as the second term,
"1101100" as the third term ,
And hence our fourth term will be
"110110011100100"

Input: n = 3
Output: 1101100

Acercarse: 

Paso 1 : comience con el primer término 1. Luego agregue 1 y 0 alternativamente después de cada elemento del término anterior. 

Paso 2 : El nuevo término obtenido se convierte en el término actual.

Paso 3 : Repita el proceso en un ciclo de 1 a n, para generar cada término y finalmente el término n.

Algoritmo:

Paso 1 : Tome el tamaño de entrada n 

Paso 2 : inicialice el primer término de la string como «1».

Paso 3 : genera cada término de la secuencia usando el bucle for anidado.

Paso 4 : agregue 0 y 1 alternativos en el medio, si el término anterior es 1, agregue 0; viceversa. 

Paso 5 : Imprima la string de salida.
 

A continuación se muestra la implementación de la idea anterior:
 

// CPP code to find nth term
// of the Dragon Curve Sequence
#include <bits/stdc++.h>
using namespace std;
 
// function to generate the nth term
string Dragon_Curve_Sequence(int n)
{
    // first term
    string s = "1";
 
    // generating each term of the sequence
    for (int i = 2; i <= n; i++)
    {
        string temp = "1";
        char prev = '1', zero = '0', one = '1';
 
        // loop to generate the ith term
        for (int j = 0; j < s.length(); j++)
        {
            // add character from the
            // original string
            temp += s[j];
 
            // add alternate 0 and 1 in between
            if (prev == '0')
            {
                // if previous added term
                // was '0' then add '1'
                temp += one;
 
                // now current term becomes
                // previous term
                prev = one;
            }
            else
            {
                // if previous added term
                // was '1', then add '0'
                temp += zero;
 
                // now current term becomes
                // previous term
                prev = zero;
            }
        }
         
        // s becomes the ith term of the sequence
        s = temp;
    }
    return s;
}
 
// Driver program
int main()
{
    // Taking inputs
    int n = 4;
 
    // generate nth term of dragon curve sequence
    string s = Dragon_Curve_Sequence(n);
     
    // Printing output
    cout << s << "\n";
}

// Java code to find nth term
// of the Dragon Curve Sequence
import java.util.*;
 
class solution
{
 
// function to generate the nth term
static String Dragon_Curve_Sequence(int n)
{
    // first term
    String s = "1";
 
    // generating each term of the sequence
    for (int i = 2; i <= n; i++)
    {
        String temp = "1";
        char prev = '1', zero = '0', one = '1';
 
        // loop to generate the ith term
        for (int j = 0; j < s.length(); j++)
        {
            // add character from the
            // original string
            temp += s.charAt(j);
 
            // add alternate 0 and 1 in between
            if (prev == '0')
            {
                // if previous added term
                // was '0' then add '1'
                temp += one;
 
                // now current term becomes
                // previous term
                prev = one;
            }
            else
            {
                // if previous added term
                // was '1', then add '0'
                temp += zero;
 
                // now current term becomes
                // previous term
                prev = zero;
            }
        }
         
        // s becomes the ith term of the sequence
        s = temp;
    }
    return s;
}
 
// Driver program
public static void main(String args[])
{
    // Taking inputs
    int n = 4;
 
    // generate nth term of dragon curve sequence
    String s = Dragon_Curve_Sequence(n);
     
    // Printing output
    System.out.println(s);
}
 
}
 
//This code is contributed by
//Surendra_Gangwar

# Python code to find nth term
# of the Dragon Curve Sequence
 
# function to generate
# the nth term
def Dragon_Curve_Sequence(n):
     
    # first term
    s = "1"
 
    # generating each term
    # of the sequence
    for i in range(2, n + 1):
        temp = "1"
        prev = '1'
        zero = '0'
        one = '1'
 
        # loop to generate the ith term
        for j in range(len(s)):
             
            # add character from the
            # original string
            temp += s[j]
 
            # add alternate 0 and
            # 1 in between
            if (prev == '0'):
                 
                # if previous added term
                # was '0' then add '1'
                temp += one
 
                # now current term becomes
                # previous term
                prev = one
 
            else:
                 
                # if previous added term
                # was '1', then add '0'
                temp += zero
 
                # now current term becomes
                # previous term
                prev = zero
 
        # s becomes the ith term
        # of the sequence
        s = temp
 
    return s
 
# Driver Code
n = 4
 
# generate nth term of
# dragon curve sequence
s = Dragon_Curve_Sequence(n)
 
# Printing output
print(s)
 
# This code is contributed by
# Sanjit_Prasad

// C# code to find nth term
// of the Dragon Curve Sequence
using System;
 
class GFG
{
 
// function to generate the nth term
static String Dragon_Curve_Sequence(int n)
{
    // first term
    String s = "1";
 
    // generating each term of the sequence
    for (int i = 2; i <= n; i++)
    {
        String temp = "1";
        char prev = '1', zero = '0', one = '1';
 
        // loop to generate the ith term
        for (int j = 0; j < s.Length; j++)
        {
            // add character from the
            // original string
            temp += s[j];
 
            // add alternate 0 and 1 in between
            if (prev == '0')
            {
                // if previous added term
                // was '0' then add '1'
                temp += one;
 
                // now current term becomes
                // previous term
                prev = one;
            }
            else
            {
                // if previous added term
                // was '1', then add '0'
                temp += zero;
 
                // now current term becomes
                // previous term
                prev = zero;
            }
        }
 
        // s becomes the ith term of the sequence
        s = temp;
    }
    return s;
}
 
// Driver Code
public static void Main()
{
    // Taking inputs
    int n = 4;
 
    // generate nth term of dragon
    // curve sequence
    String s = Dragon_Curve_Sequence(n);
 
    // Printing output
    Console.WriteLine(s);
}
}
 
// This code is contributed by Rajput-Ji

<?php
// PHP code to find nth term
// of the Dragon Curve Sequence
 
// function to generate the nth term
function Dragon_Curve_Sequence($n)
{
    // first term
    $s = "1";
 
    // generating each term of the sequence
    for ($i = 2; $i <= $n; $i++)
    {
        $temp = "1";
        $prev = '1';
        $zero = '0';
        $one = '1';
 
        // loop to generate the ith term
        for ($j = 0; $j < strlen($s); $j++)
        {
            // add character from the
            // original string
            $temp .= $s[$j];
 
            // add alternate 0 and 1 in between
            if ($prev == '0')
            {
                // if previous added term
                // was '0' then add '1'
                $temp .= $one;
 
                // now current term becomes
                // previous term
                $prev = $one;
            }
            else
            {
                // if previous added term
                // was '1', then add '0'
                $temp .= $zero;
 
                // now current term becomes
                // previous term
                $prev = $zero;
            }
        }
         
        // s becomes the ith term of the sequence
        $s = $temp;
    }
    return $s;
}
 
// Driver code
 
    // Taking inputs
    $n = 4;
 
    // generate nth term of dragon curve sequence
    $s = Dragon_Curve_Sequence($n);
     
    // Printing output
    echo $s."\n";
 
// This code is contributed by mits
?>

<script>
// Javascript code to find nth term
// of the Dragon Curve Sequence
 
// function to generate the nth term
function Dragon_Curve_Sequence(n)
{
    // first term
    let s = "1";
 
    // generating each term of the sequence
    for (let i = 2; i <= n; i++)
    {
        let temp = "1";
        let prev = '1';
        let zero = '0';
        let one = '1';
 
        // loop to generate the ith term
        for (let j = 0; j < s.length; j++)
        {
            // add character from the
            // original string
            temp = temp + s[j];
 
            // add alternate 0 and 1 in between
            if (prev == '0')
            {
                // if previous added term
                // was '0' then add '1'
                temp += one;
 
                // now current term becomes
                // previous term
                prev = one;
            }
            else
            {
                // if previous added term
                // was '1', then add '0'
                temp += zero;
 
                // now current term becomes
                // previous term
                prev = zero;
            }
        }
         
        // s becomes the ith term of the sequence
        s = temp;
    }
    return s;
}
 
// Driver code
 
    // Taking inputs
    let n = 4;
 
    // generate nth term of dragon curve sequence
    let s = Dragon_Curve_Sequence(n);
     
    // Printing output
    document.write(s + "<br>");
 
// This code is contributed by gfgking
</script>

Producción: 
 

110110011100100

Complejidad de tiempo: O(n*s) donde s es la longitud de la string resultante

Espacio auxiliar: O(s) donde s es la longitud de la string resultante