El N-ésimo término en la secuencia numérica de Wedderburn-Etherington (comenzando con el número 0 para n = 0) cuenta el número de árboles enraizados desordenados con n hojas en los que todos los Nodes, incluida la raíz, tienen cero o exactamente dos hijos.
Para un N dado . La tarea es encontrar los primeros N términos de la sucesión.
Secuencia:
0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, ….
Árboles con 0 o 2 hijos:
Ejemplos:
Entrada: N = 10
Salida: 0, 1, 1, 1, 2, 3, 6, 11, 23, 46
Entrada: N = 20
Salida: 0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, 127912
Enfoque:
La relación de recurrencia para encontrar el número N es:
- a(2x-1) = a(1) * a(2x-2) + a(2) * a(2x-3) + … + a(x-1) * a(x)
- a(2x) = a(1) * a(2x-1) + a(2) * a(2x-2) + … + a(x-1) * a(x+1) + a(x) * (a(x)+1)/2
Usando la relación anterior podemos encontrar el i-ésimo término de la serie. Comenzaremos desde el término 0 y luego almacenaremos la respuesta en un mapa y luego usaremos los valores en el mapa para encontrar el término i+1 de la serie. también usaremos casos base para el elemento 0, 1 y 2 que son 0, 1, 1 respectivamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find N terms of the sequence
#include <bits/stdc++.h>
using namespace std;
// Stores the Wedderburn Etherington numbers
map<int, int> store;
// Function to return the nth
// Wedderburn Etherington numbers
int Wedderburn(int n)
{
// Base case
if (n <= 2)
return store[n];
// If n is even n = 2x
else if (n % 2 == 0)
{
// get x
int x = n / 2, ans = 0;
// a(2x) = a(1)a(2x-1) + a(2)a(2x-2) + ... +
// a(x-1)a(x+1)
for (int i = 1; i < x; i++) {
ans += store[i] * store[n - i];
}
// a(x)(a(x)+1)/2
ans += (store[x] * (store[x] + 1)) / 2;
// Store the ans
store[n] = ans;
// Return the required answer
return ans;
}
else
{
// If n is odd
int x = (n + 1) / 2, ans = 0;
// a(2x-1) = a(1)a(2x-2) + a(2)a(2x-3) + ... +
// a(x-1)a(x),
for (int i = 1; i < x; i++) {
ans += store[i] * store[n - i];
}
// Store the ans
store[n] = ans;
// Return the required answer
return ans;
}
}
// Function to print first N
// Wedderburn Etherington numbers
void Wedderburn_Etherington(int n)
{
// Store first 3 numbers
store[0] = 0;
store[1] = 1;
store[2] = 1;
// Print N terms
for (int i = 0; i < n; i++)
{
cout << Wedderburn(i);
if(i!=n-1)
cout << ", ";
}
}
// Driver code
int main()
{
int n = 10;
// function call
Wedderburn_Etherington(n);
return 0;
}
Java
// Java program to find N terms of the sequence
import java.util.*;
class GFG
{
// Stores the Wedderburn Etherington numbers
static HashMap<Integer,
Integer> store = new HashMap<Integer,
Integer>();
// Function to return the nth
// Wedderburn Etherington numbers
static int Wedderburn(int n)
{
// Base case
if (n <= 2)
return store.get(n);
// If n is even n = 2x
else if (n % 2 == 0)
{
// get x
int x = n / 2, ans = 0;
// a(2x) = a(1)a(2x-1) + a(2)a(2x-2) + ... +
// a(x-1)a(x+1)
for (int i = 1; i < x; i++)
{
ans += store.get(i) * store.get(n - i);
}
// a(x)(a(x)+1)/2
ans += (store.get(x) * (store.get(x) + 1)) / 2;
// Store the ans
store. put(n, ans);
// Return the required answer
return ans;
}
else
{
// If n is odd
int x = (n + 1) / 2, ans = 0;
// a(2x-1) = a(1)a(2x-2) + a(2)a(2x-3) + ... +
// a(x-1)a(x),
for (int i = 1; i < x; i++)
{
ans += store.get(i) * store.get(n - i);
}
// Store the ans
store. put(n, ans);
// Return the required answer
return ans;
}
}
// Function to print first N
// Wedderburn Etherington numbers
static void Wedderburn_Etherington(int n)
{
// Store first 3 numbers
store. put(0, 0);
store. put(1, 1);
store. put(2, 1);
// Print N terms
for (int i = 0; i < n; i++)
{
System.out.print(Wedderburn(i));
if(i != n - 1)
System.out.print(" ");
}
}
// Driver code
public static void main(String[] args)
{
int n = 10;
// function call
Wedderburn_Etherington(n);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to find N terms # of the sequence # Stores the Wedderburn Etherington numbers store = dict() # Function to return the nth # Wedderburn Etherington numbers def Wedderburn(n): # Base case if (n <= 2): return store[n] # If n is even n = 2x elif (n % 2 == 0): # get x x = n // 2 ans = 0 # a(2x) = a(1)a(2x-1) + a(2)a(2x-2) + ... + # a(x-1)a(x+1) for i in range(1, x): ans += store[i] * store[n - i] # a(x)(a(x)+1)/2 ans += (store[x] * (store[x] + 1)) // 2 # Store the ans store[n] = ans # Return the required answer return ans else: # If n is odd x = (n + 1) // 2 ans = 0 # a(2x-1) = a(1)a(2x-2) + a(2)a(2x-3) + ... + # a(x-1)a(x), for i in range(1, x): ans += store[i] * store[n - i] # Store the ans store[n] = ans # Return the required answer return ans # Function to print first N # Wedderburn Etherington numbers def Wedderburn_Etherington(n): # Store first 3 numbers store[0] = 0 store[1] = 1 store[2] = 1 # Print N terms for i in range(n): print(Wedderburn(i), end = "") if(i != n - 1): print(end = ", ") # Driver code n = 10 # function call Wedderburn_Etherington(n) # This code is contributed by Mohit Kumar
C#
// C# program to find N terms of the sequence
using System;
using System.Collections.Generic;
class GFG
{
// Stores the Wedderburn Etherington numbers
static Dictionary<int,
int> store = new Dictionary<int,
int>();
// Function to return the nth
// Wedderburn Etherington numbers
static int Wedderburn(int n)
{
// Base case
if (n <= 2)
return store[n];
// If n is even n = 2x
else if (n % 2 == 0)
{
// get x
int x = n / 2, ans = 0;
// a(2x) = a(1)a(2x-1) + a(2)a(2x-2) + ... +
// a(x-1)a(x+1)
for (int i = 1; i < x; i++)
{
ans += store[i] * store[n - i];
}
// a(x)(a(x)+1)/2
ans += (store[x] * (store[x] + 1)) / 2;
// Store the ans
if(store.ContainsKey(n))
{
store.Remove(n);
store.Add(n, ans);
}
else
store.Add(n, ans);
// Return the required answer
return ans;
}
else
{
// If n is odd
int x = (n + 1) / 2, ans = 0;
// a(2x-1) = a(1)a(2x-2) + a(2)a(2x-3) + ... +
// a(x-1)a(x),
for (int i = 1; i < x; i++)
{
ans += store[i] * store[n - i];
}
// Store the ans
if(store.ContainsKey(n))
{
store.Remove(n);
store.Add(n, ans);
}
else
store.Add(n, ans);
// Return the required answer
return ans;
}
}
// Function to print first N
// Wedderburn Etherington numbers
static void Wedderburn_Etherington(int n)
{
// Store first 3 numbers
store.Add(0, 0);
store.Add(1, 1);
store.Add(2, 1);
// Print N terms
for (int i = 0; i < n; i++)
{
Console.Write(Wedderburn(i));
if(i != n - 1)
Console.Write(" ");
}
}
// Driver code
public static void Main(String[] args)
{
int n = 10;
// function call
Wedderburn_Etherington(n);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find N terms of the sequence
// Stores the Wedderburn Etherington numbers
var store = new Map();
// Function to return the nth
// Wedderburn Etherington numbers
function Wedderburn(n)
{
// Base case
if (n <= 2)
return store[n];
// If n is even n = 2x
else if (n % 2 == 0)
{
// get x
var x = parseInt(n / 2), ans = 0;
// a(2x) = a(1)a(2x-1) + a(2)a(2x-2) + ... +
// a(x-1)a(x+1)
for (var i = 1; i < x; i++) {
ans += store[i] * store[n - i];
}
// a(x)(a(x)+1)/2
ans += (store[x] * (store[x] + 1)) / 2;
// Store the ans
store[n] = ans;
// Return the required answer
return ans;
}
else
{
// If n is odd
var x = (n + 1) / 2, ans = 0;
// a(2x-1) = a(1)a(2x-2) + a(2)a(2x-3) + ... +
// a(x-1)a(x),
for (var i = 1; i < x; i++) {
ans += store[i] * store[n - i];
}
// Store the ans
store[n] = ans;
// Return the required answer
return ans;
}
}
// Function to print first N
// Wedderburn Etherington numbers
function Wedderburn_Etherington(n)
{
// Store first 3 numbers
store[0] = 0;
store[1] = 1;
store[2] = 1;
// Print N terms
for (var i = 0; i < n; i++)
{
document.write( Wedderburn(i));
if(i != n - 1)
document.write( ", ");
}
}
// Driver code
var n = 10;
// function call
Wedderburn_Etherington(n);
// This code is contributed by rrrtnx.
</script>
Producción:
0, 1, 1, 1, 2, 3, 6, 11, 23, 46
Complejidad de tiempo: O (n 2 logn)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA