Dado un entero ‘n’, imprima los primeros términos ‘n’ de la Secuencia de Moser-de Bruijn.
La sucesión de Moser-de Bruijn es la sucesión que se obtiene sumando las distintas potencias del número 4 (Por ejemplo, 1, 4, 16, 64, etc).
Ejemplos:
Input : 5 Output : 0 1 4 5 16 Input : 10 Output : 0 1 4 5 16 17 20 21 64 65
Se observa que los términos de la sucesión siguen la relación de recurrencia:
1) S(2 * n) = 4 * S(n) 2) S(2 * n + 1) = 4 * S(n) + 1 with S(0) = 0 and S(1) = 1
Cabe señalar aquí que cualquier número que sea la suma de potencias no distintas de 4 no forma parte de la secuencia. Por ejemplo, 8 no es parte de la secuencia porque se forma como la suma de potencias no distintas de 4, que son 4 y 4. Por lo tanto,
cualquier número que no sea una potencia de 4 y esté presente en la secuencia debe sea la suma de las distintas potencias de 4.
Por ejemplo, 21 es parte de la secuencia, aunque no sea una potencia de 4, porque es la suma de las distintas potencias de 4, que son 1, 4 y dieciséis.
Emplee la relación de recurrencia discutida anteriormente para generar la secuencia de manera eficiente.
C++
// CPP code to generate first 'n' terms
// of the Moser-de Bruijn Sequence
#include <bits/stdc++.h>
using namespace std;
// Function to generate nth term
// of Moser-de Bruijn Sequence
int gen(int n)
{
// S(0) = 0
if (n == 0)
return 0;
// S(1) = 1
else if (n == 1)
return 1;
// S(2 * n) = 4 * S(n)
else if (n % 2 == 0)
return 4 * gen(n / 2);
// S(2 * n + 1) = 4 * S(n) + 1
else if (n % 2 == 1)
return 4 * gen(n / 2) + 1;
}
// Generating the first 'n' terms
// of Moser-de Bruijn Sequence
void moserDeBruijn(int n)
{
for (int i = 0; i < n; i++)
cout << gen(i) << " ";
cout << "\n";
}
// Driver Code
int main()
{
int n = 15;
cout << "First " << n << " terms of "
<< "Moser-de Bruijn Sequence : \n";
moserDeBruijn(n);
return 0;
}
Java
// Java code to generate first 'n' terms
// of the Moser-de Bruijn Sequence
class GFG
{
// Function to generate nth term
// of Moser-de Bruijn Sequence
public static int gen(int n)
{
// S(0) = 0
if (n == 0)
return 0;
// S(1) = 1
else if (n == 1)
return 1;
// S(2 * n) = 4 * S(n)
else if (n % 2 == 0)
return 4 * gen(n / 2);
// S(2 * n + 1) = 4 * S(n) + 1
else if (n % 2 == 1)
return 4 * gen(n / 2) + 1;
return 0;
}
// Generating the first 'n' terms
// of Moser-de Bruijn Sequence
public static void moserDeBruijn(int n)
{
for (int i = 0; i < n; i++)
System.out.print(gen(i) + " ");
System.out.println();
}
// Driver Code
public static void main(String args[])
{
int n = 15;
System.out.println("First " + n +
" terms of " +
"Moser-de Bruijn Sequence : ");
moserDeBruijn(n);
}
}
// This code is contributed by JaideepPyne.
Python3
# Python code to generate first
# 'n' terms of the Moser-de
# Bruijn Sequence
# Function to generate nth term
# of Moser-de Bruijn Sequence
def gen(n):
# S(0) = 0
if n == 0:
return 0
# S(1) = 1
elif n ==1:
return 1
# S(2 * n) = 4 * S(n)
elif n % 2 ==0:
return 4 * gen(n // 2)
# S(2 * n + 1) = 4 * S(n) + 1
elif n % 2 == 1:
return 4 * gen(n // 2) +1
# Generating the first 'n' terms
# of Moser-de Bruijn Sequence
def moserDeBruijn(n):
for i in range(n):
print(gen(i), end = " ")
# Driver Program
n = 15
print("First", n, "terms of ",
"Moser-de Bruijn Sequence:")
moserDeBruijn(n)
# This code is contributed by Shrikant13
C#
// C# code to generate first 'n' terms
// of the Moser-de Bruijn Sequence
using System;
class GFG {
// Function to generate nth term
// of Moser-de Bruijn Sequence
public static int gen(int n)
{
// S(0) = 0
if (n == 0)
return 0;
// S(1) = 1
else if (n == 1)
return 1;
// S(2 * n) = 4 * S(n)
else if (n % 2 == 0)
return 4 * gen(n / 2);
// S(2 * n + 1) = 4 * S(n) + 1
else if (n % 2 == 1)
return 4 * gen(n / 2) + 1;
return 0;
}
// Generating the first 'n' terms
// of Moser-de Bruijn Sequence
public static void moserDeBruijn(int n)
{
for (int i = 0; i < n; i++)
Console.Write(gen(i) + " ");
Console.WriteLine();
}
// Driver Code
public static void Main()
{
int n = 15;
Console.WriteLine("First " + n +
" terms of " +
"Moser-de Bruijn Sequence : ");
moserDeBruijn(n);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP code to generate first 'n' terms
// of the Moser-de Bruijn Sequence
// Function to generate nth term
// of Moser-de Bruijn Sequence
function gen($n)
{
// S(0) = 0
if ($n == 0)
return 0;
// S(1) = 1
else if ($n == 1)
return 1;
// S(2 * n) = 4 * S(n)
else if ($n % 2 == 0)
return 4 * gen($n / 2);
// S(2 * n + 1) = 4 * S(n) + 1
else if ($n % 2 == 1)
return 4 * gen($n / 2) + 1;
}
// Generating the first 'n' terms
// of Moser-de Bruijn Sequence
function moserDeBruijn($n)
{
for ($i = 0; $i < $n; $i++)
echo(gen($i) . " ");
echo("\n");
}
// Driver Code
$n = 15;
echo("First " . $n . " terms of " .
"Moser-de Bruijn Sequence : \n");
echo(moserDeBruijn($n));
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript code to generate first 'n' terms
// of the Moser-de Bruijn Sequence
// Function to generate nth term
// of Moser-de Bruijn Sequence
function gen(n)
{
// S(0) = 0
if (n == 0)
return 0;
// S(1) = 1
else if (n == 1)
return 1;
// S(2 * n) = 4 * S(n)
else if (n % 2 == 0)
return 4 * gen(parseInt(n / 2, 10));
// S(2 * n + 1) = 4 * S(n) + 1
else if (n % 2 == 1)
return 4 * gen(parseInt(n / 2, 10)) + 1;
return 0;
}
// Generating the first 'n' terms
// of Moser-de Bruijn Sequence
function moserDeBruijn(n)
{
for(let i = 0; i < n; i++)
document.write(gen(i) + " ");
document.write("</br>");
}
// Driver code
let n = 15;
document.write("First " + n + " terms of " +
"Moser-de Bruijn Sequence : " + "</br>");
moserDeBruijn(n);
// This code is contributed by decode2207
</script>
Producción :
First 15 terms of Moser-de Bruijn Sequence : 0 1 4 5 16 17 20 21 64 65 68 69 80 81 84
Implementación de Programación Dinámica:
C++
// CPP code to generate first 'n' terms
// of the Moser-de Bruijn Sequence
#include <bits/stdc++.h>
using namespace std;
// Function to generate nth term
// of Moser-de Bruijn Sequence
int gen(int n)
{
int S[n+1];
S[0] = 0;
S[1] = 1;
for (int i = 2; i <= n; i++)
{
// S(2 * n) = 4 * S(n)
if (i % 2 == 0)
S[i] = 4 * S[i / 2];
// S(2 * n + 1) = 4 * S(n) + 1
else
S[i] = 4 * S[i / 2] + 1;
}
return S[n];
}
// Generating the first 'n' terms
// of Moser-de Bruijn Sequence
void moserDeBruijn(int n)
{
for (int i = 0; i < n; i++)
cout << gen(i) << " ";
cout << "\n";
}
// Driver Code
int main()
{
int n = 15;
cout << "First " << n << " terms of "
<< "Moser-de Bruijn Sequence : \n";
moserDeBruijn(n);
return 0;
}
Java
// Java code to generate first 'n' terms
// of the Moser-de Bruijn Sequence
class GFG
{
// Function to generate nth term
// of Moser-de Bruijn Sequence
static int gen(int n)
{
int []S = new int [n + 1];
S[0] = 0;
if(n != 0)
S[1] = 1;
for (int i = 2; i <= n; i++)
{
// S(2 * n) = 4 * S(n)
if (i % 2 == 0)
S[i] = 4 * S[i / 2];
// S(2 * n + 1) = 4 * S(n) + 1
else
S[i] = 4 * S[i/2] + 1;
}
return S[n];
}
// Generating the first 'n' terms
// of Moser-de Bruijn Sequence
static void moserDeBruijn(int n)
{
for (int i = 0; i < n; i++)
System.out.print(gen(i)+" ");
}
// Driver Code
public static void main(String[] args)
{
int n = 15;
System.out.println("First " + n +
" terms of " +
"Moser-de Bruijn Sequence : ");
moserDeBruijn(n);
}
}
// This code is contributed by
// Smitha Dinesh Semwal.
Python3
# python3 code to generate first 'n' terms
# of the Moser-de Bruijn Sequence
# Function to generate nth term
# of Moser-de Bruijn Sequence
def gen( n ):
S = [0, 1]
for i in range(2, n+1):
# S(2 * n) = 4 * S(n)
if i % 2 == 0:
S.append(4 * S[int(i / 2)]);
# S(2 * n + 1) = 4 * S(n) + 1
else:
S.append(4 * S[int(i / 2)] + 1);
z = S[n];
return z;
# Generating the first 'n' terms
# of Moser-de Bruijn Sequence
def moserDeBruijn(n):
for i in range(n):
print(gen(i), end = " ")
# Driver Code
n = 15
print("First", n, "terms of ",
"Moser-de Brujn Sequence:")
moserDeBruijn(n)
# This code is contributed by mits.
C#
// C# code to generate first 'n' terms
// of the Moser-de Bruijn Sequence
using System;
class GFG
{
// Function to generate nth term
// of Moser-de Bruijn Sequence
static int gen(int n)
{
int []S = new int [n + 1];
S[0] = 0;
if(n != 0)
S[1] = 1;
for (int i = 2; i <= n; i++)
{
// S(2 * n) = 4 * S(n)
if (i % 2 == 0)
S[i] = 4 * S[i / 2];
// S(2 * n + 1) = 4 * S(n) + 1
else
S[i] = 4 * S[i/2] + 1;
}
return S[n];
}
// Generating the first 'n' terms
// of Moser-de Bruijn Sequence
static void moserDeBruijn(int n)
{
for (int i = 0; i < n; i++)
Console.Write(gen(i)+" ");
}
// Driver Code
public static void Main()
{
int n = 15;
Console.WriteLine("First " + n +
" terms of " +
"Moser-de Bruijn Sequence : ");
moserDeBruijn(n);
}
}
// This code is contributed by
// Smitha Dinesh Semwal.
PHP
<?php
// PHP code to generate first 'n' terms
// of the Moser-de Bruijn Sequence
// Function to generate nth term
// of Moser-de Bruijn Sequence
function gen( $n)
{
$S = array();
$S[0] = 0;
$S[1] = 1;
for ( $i = 2; $i <= $n; $i++)
{
// S(2 * n) = 4 * S(n)
if ($i % 2 == 0)
$S[$i] = 4 * $S[$i / 2];
// S(2 * n + 1) = 4 * S(n) + 1
else
$S[$i] = 4 * $S[$i/2] + 1;
}
return $S[$n];
}
// Generating the first 'n' terms
// of Moser-de Bruijn Sequence
function moserDeBruijn( $n)
{
for ( $i = 0; $i < $n; $i++)
echo gen($i) , " ";
echo "\n";
}
// Driver Code
$n = 15;
echo "First " ,$n ," terms of "
, "Moser-de Bruijn Sequence : \n";
moserDeBruijn($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript code to generate first 'n' terms
// of the Moser-de Bruijn Sequence
// Function to generate nth term
// of Moser-de Bruijn Sequence
function gen(n)
{
let S = new Array(n + 1);
S.fill(0);
S[0] = 0;
if(n != 0)
S[1] = 1;
for (let i = 2; i <= n; i++)
{
// S(2 * n) = 4 * S(n)
if (i % 2 == 0)
S[i] = 4 * S[parseInt(i / 2, 10)];
// S(2 * n + 1) = 4 * S(n) + 1
else
S[i] = 4 * S[parseInt(i / 2, 10)] + 1;
}
return S[n];
}
// Generating the first 'n' terms
// of Moser-de Bruijn Sequence
function moserDeBruijn(n)
{
for (let i = 0; i < n; i++)
document.write(gen(i)+" ");
}
let n = 15;
document.write("First " + n +
" terms of " +
"Moser-de Bruijn Sequence : " + "</br>");
moserDeBruijn(n);
</script>
Producción :
First 15 terms of Moser-de Bruijn Sequence : 0 1 4 5 16 17 20 21 64 65 68 69 80 81 84
Complejidad de tiempo : O (n) desde que se usa un ciclo for
Complejidad espacial : O (n) para array
Publicación traducida automáticamente
Artículo escrito por SaagnikAdhikary y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA