Dyck Mots de longueur donnée

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Étant donné un entier nla tâche est de compter les mots Dyck de longueur possible n. Un mot DYCK est un mot ne contenant que des caractères ‘X’ et ‘O’ de sorte que dans chaque préfixe du mot fréquence(‘X’) ≥ fréquence(‘Y’)
Exemples:

Saisir: n = 2
Production: 2
“XY” et “XX” sont les seuls mots DYCK possibles de longueur 2.
Saisir: n = 5
Production: 42

Approcher:

Interprétation géométrique : Il est basé sur l’idée de DYCK PATH.

pic1 10pic12 1

Les diagrammes ci-dessus représentent les CHEMINS DE DYCK de (0, 0) à (n, n).

Un CHEMIN DYCK contient n segments de ligne horizontaux et n segments de ligne verticaux qui ne croisent pas le segment AB.
L’idée principale derrière ce problème est de trouver le nombre total de chemins DYCK de (0, 0) à (n, n).
Pour aborder ce problème, l’idée principale est de trouver le nombre total de chemins de Manhattan Distance entre (0, 0) et (n, n) et d’exclure tous les chemins qui traversent le segment AB.

Comment calculer le nombre de chemins qui traversent le segment AB ?
Appelons tous ces chemins qui traversent AB comme “incorrects”. Les chemins ‘incorrects’ qui croisent AB doivent passer par la ligne CD.

  1. Prendre la symétrie du point A sur la droite A.
  2. Tracez une ligne symétrique de la ligne incorrecte en prenant référence avec CD.

pic3 4

Une ligne symétrique wrt CD.

pic4 2

FG-Ligne symétrique d’une ligne incorrecte.

Toutes ces droites qui coupent AB leur droite symétrique qui commence en F finit en G(n-1, n+1).
D’où le nombre de lignes incorrectes :
2 * nCn-1
Donc le nombre de mots DYCK avec n ‘X’ et n ‘Y’ est :
2 * nCn2 * nCn-1 = (2 * n) ! / (n) ! * (n+1) !

Voici la mise en œuvre de l’approche ci-dessus :

C++

#include <iostream>

using namespace std;

long long int count_Dyck_Words(unsigned int n)

{

    

    long long int res = 1;

    for (int i = 0; i < n; ++i) {

        res *= (2 * n - i);

        res /= (i + 1);

    }

    

    return (res / (n + 1));

}

int main()

{

    int n = 5;

    cout << count_Dyck_Words(n);

    return 0;

}

Java

class GFG

{

    

static int count_Dyck_Words( int n)

{

    

    int res = 1;

    for (int i = 0; i < n; ++i)

    {

        res *= (2 * n - i);

        res /= (i + 1);

    }

    

    return (res / (n + 1));

}

public static void main(String[] args)

{

    int n = 5;

    System.out.println(count_Dyck_Words(n));

}

}

Python3

def count_Dyck_Words(n) :

    

    

    res = 1;

    for i in range(n) :

        res *= (2 * n - i);

        res //= (i + 1);

    

    

    return (res / (n + 1));

if __name__ == "__main__" :

    n = 5;

    print(count_Dyck_Words(n));

C#

using System;

class GFG

{

    

static int count_Dyck_Words( int n)

{

    

    int res = 1;

    for (int i = 0; i < n; ++i)

    {

        res *= (2 * n - i);

        res /= (i + 1);

    }

    

    return (res / (n + 1));

}

public static void Main()

{

    int n = 5;

    Console.WriteLine(count_Dyck_Words(n));

}

}

PHP

<?php

function count_Dyck_Words( $n)

{

    

    $res = 1;

    for ($i = 0; $i < $n; ++$i)

    {

        $res *= (2 * $n - $i);

        $res /= ($i + 1);

    }

    

    return ($res / ($n + 1));

}

$n = 5;

echo(count_Dyck_Words($n));

?>

Javascript

<script>

    

    

    

    

    function count_Dyck_Words(n)

    {

        

        let res = 1;

        for (let i = 0; i < n; ++i)

        {

            res *= (2 * n - i);

            res = parseInt(res / (i + 1), 10);

        }

        

        return parseInt(res / (n + 1), 10);

    }

    

    let n = 5;

    document.write(count_Dyck_Words(n));

    

    

</script>

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *