Récursion pour créer - imbriqué ()

Question

Je suis en train de résoudre l'un des problèmes de programmation dynamique "classiques". Le problème est - Étant donné un nombre en entrée, générer des conditions imbriquées possibles.

Édition : Comme l'a souligné temp ci-dessous, je vais d'abord essayer de résoudre cela en utilisant la récursion, puis essayer avec la programmation dynamique.

Par exemple, si n = 3

Sortie :
((()))
()()()
(())()
()(())
(()())

Ma démarche pour résoudre le problème repose sur deux règles.

1. Ajouter une parenthèse ouvrante "(" si le nombre maximum (ici 3) n'est pas atteint et que le nombre de parenthèses gauches est inférieur ou égal au nombre de parenthèses droites.
2. Ajouter une parenthèse fermante uniquement si le nombre maximal n'est pas atteint et que le nombre de parenthèses droites est inférieur au nombre de parenthèses gauches.

En théorie, cela semble correct, mais cela échoue lamentablement sur la source ci-dessous. Veuillez excuser le codage en dur.

Édition : J'ai apporté quelques modifications et me suis rapproché un peu plus de la solution :)

 #include 
#include 
#include 

using namespace std;

void printPar(int l,int r,string s)
{
    if(l > 3 || r > 3 || r >l)
        return;

    if(l==3 && r==3)
    {
        cout<

`

Debug :

<<<>>>
<<<>>>
<<><>>
<<><>>
<><<>>
<><<>>
<><><>
<><><>

Je comprends pourquoi il y a des valeurs en double dans la liste, c'est-à-dire une fois que la fonction est appelée en utilisant la récursion et finit par suivre la prochaine branche lors de l'exécution. La deuxième impression est due à la fonction elle-même tombant sur la deuxième branche. Y a-t-il un moyen de gérer cela ? Je ne veux vraiment pas passer par la voie globale.

Aussi, dans ma tête, ce code devrait afficher (())() - pourtant il ne le fait pas :(

Quelqu'un pourrait-il pointer l'erreur ?

Merci !

Je sais que la condition a besoin de quelques ajustements, mais je regarde cela sans fin. Aidez-moi !

`

Answer 1

En ce moment, votre solution ne tire pas parti de la programmation dynamique. Si vous voulez utiliser la DP ici, vous devrez réfléchir au problème de manière récursive. Heureusement, il y a une excellente formulation récursive à ce problème:

1. Il n'y a qu'une seule façon de créer des parenthèses équilibrées à partir de zéro parenthèse, qui est de ne pas avoir de parenthèses du tout.
2. Si vous avez n + 1 paires de parenthèses à équilibrer, vous pouvez générer toutes les parenthèses équilibrées comme suit: pour tous les i de 0 à n, construisez chaque chaîne de la forme (X)Y, où X est une chaîne de i parenthèses équilibrées et Y est une chaîne de n - i parenthèses équilibrées.

La beauté de cette configuration est que pour calculer toutes les chaînes de n + 1 parenthèses équilibrées, vous avez seulement besoin de savoir comment faire des parenthèses équilibrées pour 0, 1, 2, ..., n + 1. Par conséquent, vous pouvez résoudre ce problème en construisant itérativement des solutions pour n = 0, 1, 2, ..., etc. et réutilisant les résultats que vous avez produits aux étapes antérieures.

J'espère que cela vous aidera!

Answer 2

Je pense que cela devrait résoudre votre problème.

// cette map contiendra toutes les expressions de parenthèses équilibrées valides
// la chaîne contiendra des expressions
// int pour contenir 'n' c'est-à-dire le nombre de '('
map mvc;

//fonction pour créer tous les ensembles de parenthèses équilibrées possibles, pour un n donné
void printAllBP(int);
//fonction d'impression
void printAll(int);

int main()
{
    int n;
    cout << "Entrez n: ";
    cin >> n;

    printAllBP(n);
    printAll(n);

    system("pause");
    return 0;
}

void printAllBP(int n)
{
    if (0==n)
    {
        mvc.insert(pair("",0));
        return;
    }    

    printAllBP(n-1);

    map::iterator it;
    for (it=mvc.begin();it!=mvc.end();++it)
    {
        if((n-1)==(*it).second)
        {
            string t=(*it).first;
            mvc.insert(pair("()"+t,n));
            mvc.insert(pair("("+t+")",n));
            mvc.insert(pair(t+"()",n));
        }
    }
}

void printAll(int n)
{
    cout << "Impression de toutes les possibilités de '" << n << "' :\n";
    map::iterator it;
    for ( it=mvc.begin();it != mvc.end();++it)
    {
        if(n==(*it).second)
            cout << "\n" << (*it).first;
    }
    cout << "\n";
}