La secuencia Thue-Morse, o secuencia Prouhet-Thue-Morse , es una secuencia binaria infinita de 0s y 1s. La secuencia se obtiene comenzando por 0 y añadiendo sucesivamente el complemento booleano de la secuencia obtenida hasta el momento.
Primeros pasos:
Empezar con 0
Agregar complemento de 0, obtenemos 01
Agregar complemento de 01, obtenemos 0110
Agregar complemento de 0110, obtenemos 01101001
Dado un número entero n . La tarea es encontrar la n-ésima string formada por la secuencia Thue-Morse, es decir, el prefijo de longitud 2 n-1 de la secuencia Thue-Morse.
Ejemplos:
Input : n = 4 Output : 01101001 We get 0, 01, 0110 and 01101001 in fourth iteration. Input : n = 3 Output : 0110
La idea es inicializar la string de salida con 0, luego ejecutar un ciclo n – 1 veces y para cada iteración encontrar el complemento de la string y agregarlo a la string.
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program to find nth term of Thue-Morse sequence.
#include <bits/stdc++.h>
using namespace std;
// Return the complement of the binary string.
string complement(string s)
{
string comps;
// finding the complement of the string.
for (int i = 0; i < s.length(); i++) {
// if character is 0, append 1
if (s.at(i) == '0')
comps += '1';
// if character is 1, append 0.
else
comps += '0';
}
return comps;
}
// Return the nth term of Thue-Morse sequence.
string nthTerm(int n)
{
// Initialing the string to 0
string s = "0";
// Running the loop for n - 1 time.
for (int i = 1; i < n; i++)
// appending the complement of
// the string to the string.
s += complement(s);
return s;
}
// Driven Program
int main()
{
int n = 4;
cout << nthTerm(n) << endl;
return 0;
}
Java
// Java Program to find nth
// term of Thue-Morse sequence.
class GFG
{
// Return the complement
// of the binary String.
static String complement(String s)
{
String comps = "";
// finding the complement
// of the String.
for (int i = 0; i < s.length(); i++)
{
// if character is 0,
// append 1
if (s.charAt(i) == '0')
comps += '1';
// if character is 1,
// append 0.
else
comps += '0';
}
return comps;
}
// Return the nth term
// of Thue-Morse sequence.
static String nthTerm(int n)
{
// Initialing the
// String to 0
String s = "0";
// Running the loop
// for n - 1 time.
for (int i = 1; i < n; i++)
// appending the complement of
// the String to the String.
s += complement(s);
return s;
}
// Driven Code
public static void main(String[] args)
{
int n = 4;
System.out.print(nthTerm(n));
}
}
// This code is contributed by
// mits
Python3
# Python3 Program to find nth term of # Thue-Morse sequence. # Return the complement of the # binary string. def complement(s): comps = ""; # finding the complement # of the string. for i in range(len(s)): # if character is 0, append 1 if (s[i] == '0'): comps += '1'; # if character is 1, append 0. else: comps += '0'; return comps; # Return the nth term of # Thue-Morse sequence. def nthTerm(n): # Initialing the string to 0 s = "0"; # Running the loop for n - 1 time. for i in range(1, n): # appending the complement of # the string to the string. s += complement(s); return s; # Driver Code n = 4; print(nthTerm(n)); # This code is contributed # by mits
C#
// C# Program to find nth
// term of Thue-Morse sequence.
using System;
class GFG
{
// Return the complement
// of the binary string.
static string complement(string s)
{
string comps = "";
// finding the complement
// of the string.
for (int i = 0; i < s.Length; i++)
{
// if character is 0,
// append 1
if (s[i] == '0')
comps += '1';
// if character is 1,
// append 0.
else
comps += '0';
}
return comps;
}
// Return the nth term
// of Thue-Morse sequence.
static string nthTerm(int n)
{
// Initialing the
// string to 0
string s = "0";
// Running the loop
// for n - 1 time.
for (int i = 1; i < n; i++)
// appending the complement of
// the string to the string.
s += complement(s);
return s;
}
// Driven Code
static void Main()
{
int n = 4;
Console.Write(nthTerm(n));
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
PHP
<?php
// PHP Program to find nth
// term of Thue-Morse sequence.
// Return the complement
// of the binary string.
function complement($s)
{
$comps = "";
// finding the complement
// of the string.
for ($i = 0;
$i < strlen($s); $i++)
{
// if character is
// 0, append 1
if ($s[$i] == '0')
$comps .= '1';
// if character is
// 1, append 0.
else
$comps .= '0';
}
return $comps;
}
// Return the nth term
// of Thue-Morse sequence.
function nthTerm($n)
{
// Initialing the
// string to 0
$s = "0";
// Running the loop
// for n - 1 time.
for ($i = 1; $i < $n; $i++)
// appending the complement of
// the string to the string.
$s .= complement($s);
return $s;
}
// Driven Code
$n = 4;
echo nthTerm($n);
// This code is contributed
// by mits
?>
C++
#include <iostream>
using namespace std;
int main() {
cout<<"GFG!";
return 0;
}
Javascript
<script>
// JavaScript Program to find nth
// term of Thue-Morse sequence.
// Return the complement
// of the binary string.
function complement(s)
{
let comps = "";
// finding the complement
// of the string.
for (let i = 0; i < s.length; i++)
{
// if character is 0,
// append 1
if (s[i] == '0')
comps += '1';
// if character is 1,
// append 0.
else
comps += '0';
}
return comps;
}
// Return the nth term
// of Thue-Morse sequence.
function nthTerm(n)
{
// Initialing the
// string to 0
let s = "0";
// Running the loop
// for n - 1 time.
for (let i = 1; i < n; i++)
// appending the complement of
// the string to the string.
s += complement(s);
return s;
}
// Driver program
let n = 4;
document.write(nthTerm(n));
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
01101001
Complejidad de tiempo: O(n*log(n))
Complejidad de espacio:O(1)