Comptez le nombre de séquences de brackets normales différentes qui ne sont pas des périodes N

Dans cet article, nous allons nous plonger dans un problème intrigant du domaine de la combinatoire et du traitement des chaînes : "Compter des séquences de parenthèses régulières distinctes qui ne sont pas N périodiques. Ce problème implique de générer des séquences de parenthèses valides distinctes, puis". filtrer les séquences N-périodiques. Nous discuterons du problème, fournirons une implémentation de code C++ d'une approche par force brute et expliquerons un cas de test.

Comprendre l'énoncé du problème

Étant donné un entier N, la tâche consiste à compter le nombre de séquences de parenthèses régulières différentes de longueur 2N qui ne sont pas N périodes. Si une séquence peut être représentée comme une chaîne S répétée M fois, où la longueur de S est N et M > 1, alors la séquence est N-périodique.

Une séquence de crochets régulière est une chaîne qui peut être transformée en une expression arithmétique correcte en insérant les caractères '1' et '+' entre les caractères d'origine. Par exemple, la séquence "(())" est régulière, tandis que ")(. " et "(()" ne le sont pas.

Méthode

En raison de la complexité du problème, une solution mathématique directe peut ne pas être réalisable. Au lieu de cela, nous devons utiliser une approche programmatique pour générer des séquences de parenthèses et compter le nombre de séquences de parenthèses qui correspondent à nos critères.

Nous utiliserons une fonction récursive pour générer toutes les séquences de parenthèses possibles de longueur 2N Lors de la génération des séquences, nous garderons une trace de deux paramètres importants : l'équilibre des parenthèses (le nombre de parenthèses ouvertes ne doit jamais être inférieur au nombre. de parenthèses fermées) et le nombre de parenthèses ouvertes (ne doit pas dépasser N).

Afin de filtrer les séquences à N périodes, nous vérifierons chaque séquence générée. Si la séquence est une répétition d’une séquence plus petite de longueur N, nous l’excluons du décompte.

Implémentation C++

Il s'agit d'une manière brutale de résoudre le problème en C++. Cette méthode génère toutes les séquences de parenthèses possibles et vérifie si chaque séquence est N-périodique et incrémente le décompte sinon. Cette solution convient aux petites tailles d’entrée car elle a une complexité temporelle exponentielle et ne s’adapte pas bien aux entrées plus volumineuses.

Exemple

#include <bits/stdc++.h>
using namespace std;

// Function to check if string is N periodic
bool isPeriodic(string s, int N) {
   string sub = s.substr(0, N);
   for (int i = N; i < s.size(); i += N) {
      if (sub != s.substr(i, N)) return false;
   }
   return true;
}

// Function to generate all bracket sequences
void generateBrackets(string s, int open, int close, int N, int &count) {
   // If sequence is complete
   if (s.size() == 2*N) {
      if (!isPeriodic(s, N)) count++;
      return;
   }
   
   // Add an open bracket if we have some left
   if (open < N) generateBrackets(s + "(", open + 1, close, N, count);
   
   // Add a close bracket if it doesn't make the sequence invalid
   if (close < open) generateBrackets(s + ")", open, close + 1, N, count);
}

int main() {
   int N = 3;
   int count = 0;
   generateBrackets("", 0, 0, N, count);
   cout << "Count of sequences: " << count;
   return 0;
}

Sortie

Count of sequences: 5

Cas de test

Considérons un cas de test avec N = 3. Ce code générera les 5 séquences de parenthèses régulières distinctes de longueur 6 qui ne sont pas 3-périodiques : ((())), (()()), (())( ), ()(()), ()()().

Conclusion

Cet article présente une méthode pour résoudre violemment le problème du comptage de différentes séquences de parenthèses régulières avec des périodes non N. Bien que cette approche puisse gérer des entrées à petite échelle, il est important de noter que le problème présente une complexité exponentielle en raison de la nécessité de générer et de vérifier toutes les séquences de parenthèses possibles, et n'est donc pas adapté aux entrées à grande échelle.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!