Números en zigzag de Euler (permutación alterna)

Los números de Euler Zigzag son una secuencia de números enteros que es un número de arreglos de esos números de modo que cada entrada sea alternativamente mayor o menor que la entrada anterior.
c1, c2, c3, c4 es una permutación alterna donde 
c1 < c2 
c3 < c2 
c3 < c4… los
números en zigzag son los siguientes 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521 ……
Para un entero N dado. La tarea es imprimir una secuencia de hasta N términos.
Ejemplos: 
 

Entrada: N = 10 
Salida: 1 1 1 2 5 16 61 272 1385 7936 
Entrada: N = 14 
Salida: 1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 

Enfoque: 
El número de zigzag (n+1) es: 
a(n+1) = \dfrac{\sum_{k=0}^{n} (\binom{N}{k}*a(k)*a(n-k))}{2} \\
Encontraremos el factorial hasta n y los almacenaremos en una array y también crearemos una segunda array para almacenar el i-ésimo número de zigzag y aplicaremos la fórmula indicada anteriormente para encontrar todos los n números en zigzag.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// CPP program to find zigzag sequence
#include <bits/stdc++.h>
using namespace std;
 
// Function to print first n zigzag numbers
void ZigZag(int n)
{
    // To store factorial and n'th zig zag number
    long long fact[n + 1], zig[n + 1] = { 0 };
 
    // Initialize factorial upto n
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = fact[i - 1] * i;
 
    // Set first two zig zag numbers
    zig[0] = 1;
    zig[1] = 1;
 
    cout << "zig zag numbers: ";
 
    // Print first two zig zag number
    cout << zig[0] << " " << zig[1] << " ";
 
    // Print the rest zig zag numbers
    for (int i = 2; i < n; i++)
    {
        long long sum = 0;
 
        for (int k = 0; k <= i - 1; k++)
        {
            // Binomial(n, k)*a(k)*a(n-k)
            sum += (fact[i - 1]/(fact[i - 1 - k]*fact[k]))
                                 *zig[k] * zig[i - 1 - k];
        }
         
        // Store the value
        zig[i] = sum / 2;
 
        // Print the number
        cout << sum / 2 << " ";
    }
}
 
// Driver code
int main()
{
    int n = 10;
     
    // Function call
    ZigZag(n);
 
    return 0;
}

Java

// Java program to find zigzag sequence
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG
{
 
// Function to print first n zigzag numbers
static void ZigZag(int n)
{
    // To store factorial and n'th zig zag number
    long[] fact= new long[n + 1];
    long[] zig = new long[n + 1];
    for (int i = 0; i < n + 1; i++)
        zig[i] = 0;
 
    // Initialize factorial upto n
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = fact[i - 1] * i;
 
    // Set first two zig zag numbers
    zig[0] = 1;
    zig[1] = 1;
 
    System.out.print("zig zag numbers: ");
 
    // Print first two zig zag number
    System.out.print(zig[0] + " " + zig[1] + " ");
 
    // Print the rest zig zag numbers
    for (int i = 2; i < n; i++)
    {
        long sum = 0;
 
        for (int k = 0; k <= i - 1; k++)
        {
            // Binomial(n, k)*a(k)*a(n-k)
            sum += (fact[i - 1] / (fact[i - 1 - k] *
                    fact[k])) * zig[k] * zig[i - 1 - k];
        }
         
        // Store the value
        zig[i] = sum / 2;
 
        // Print the number
        System.out.print(sum / 2 + " " );
         
    }
}
 
// Driver code
public static void main (String[] args)
              throws java.lang.Exception
{
    int n = 10;
     
    // Function call
    ZigZag(n);
}
}
 
// This code is contributed by nidhiva

Python3

# Python3 program to find zigzag sequence
 
# Function to print first n zigzag numbers
def ZigZag(n):
 
    # To store factorial and
    # n'th zig zag number
    fact = [0 for i in range(n + 1)]
    zig = [0 for i in range(n + 1)]
  
    # Initialize factorial upto n
    fact[0] = 1
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i
 
    # Set first two zig zag numbers
    zig[0] = 1
    zig[1] = 1
 
    print("zig zag numbers: ", end = " ")
 
    # Print first two zig zag number
    print(zig[0], zig[1], end = " ")
 
    # Print the rest zig zag numbers
    for i in range(2, n):
        sum = 0
 
        for k in range(0, i):
             
            # Binomial(n, k)*a(k)*a(n-k)
            sum += ((fact[i - 1] //
                    (fact[i - 1 - k] * fact[k])) *
                     zig[k] * zig[i - 1 - k])
 
        # Store the value
        zig[i] = sum // 2
 
        # Print the number
        print(sum // 2, end = " ")
 
# Driver code
n = 10
 
# Function call
ZigZag(n)
 
# This code is contributed by Mohit Kumar

C#

// C# program to find zigzag sequence
using System;
     
class GFG
{
 
// Function to print first n zigzag numbers
static void ZigZag(int n)
{
    // To store factorial and n'th zig zag number
    long[] fact= new long[n + 1];
    long[] zig = new long[n + 1];
    for (int i = 0; i < n + 1; i++)
        zig[i] = 0;
 
    // Initialize factorial upto n
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = fact[i - 1] * i;
 
    // Set first two zig zag numbers
    zig[0] = 1;
    zig[1] = 1;
 
    Console.Write("zig zag numbers: ");
 
    // Print first two zig zag number
    Console.Write(zig[0] + " " + zig[1] + " ");
 
    // Print the rest zig zag numbers
    for (int i = 2; i < n; i++)
    {
        long sum = 0;
 
        for (int k = 0; k <= i - 1; k++)
        {
            // Binomial(n, k)*a(k)*a(n-k)
            sum += (fact[i - 1] / (fact[i - 1 - k] *
                    fact[k])) * zig[k] * zig[i - 1 - k];
        }
         
        // Store the value
        zig[i] = sum / 2;
 
        // Print the number
        Console.Write(sum / 2 + " " );
         
    }
}
 
// Driver code
public static void Main (String[] args)
{
    int n = 10;
     
    // Function call
    ZigZag(n);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program to find zigzag sequence
 
// Function to print first n zigzag numbers
function ZigZag(n)
{
    // To store factorial and n'th zig zag number
    var fact = Array(n+1).fill(0);
    var zig = Array(n+1).fill(0);
 
    // Initialize factorial upto n
    fact[0] = 1;
    for (var i = 1; i <= n; i++)
        fact[i] = fact[i - 1] * i;
 
    // Set first two zig zag numbers
    zig[0] = 1;
    zig[1] = 1;
 
    document.write( "zig zag numbers: ");
 
    // Print first two zig zag number
    document.write( zig[0] + " " + zig[1] + " ");
 
    // Print the rest zig zag numbers
    for (var i = 2; i < n; i++)
    {
        var sum = 0;
 
        for (var k = 0; k <= i - 1; k++)
        {
            // Binomial(n, k)*a(k)*a(n-k)
            sum += parseInt(fact[i - 1]/(fact[i - 1 - k]*fact[k]))
                                 *zig[k] * zig[i - 1 - k];
        }
         
        // Store the value
        zig[i] = parseInt(sum / 2);
 
        // Print the number
        document.write( parseInt(sum / 2) + " ");
    }
}
 
// Driver code
var n = 10;
 
// Function call
ZigZag(n);
 
// This code is contributed by rutvik_56.
</script>

Producción: 
 

zig zag numbers: 1 1 1 2 5 16 61 272 1385 7936

Complejidad temporal: O(n 2 )

Espacio Auxiliar: O(n)

Referencia  
https://en.wikipedia.org/wiki/Alternating_permutation  
https://oeis.org/A000111
 

Publicación traducida automáticamente

Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *