Maison > Article > développement back-end > Calculer des chaînes binaires de longueur N qui sont des concaténations répétées de sous-chaînes
Le but de cet article est d'implémenter un programme qui compte le nombre de chaînes binaires de longueur N formées par concaténation répétée d'une sous-chaîne.
L'objectif est de déterminer combien de chaînes binaires de longueur N peuvent être créées en concaténant à plusieurs reprises des sous-chaînes individuelles du texte donné, où N est un entier positif.
Implémentez un programme qui compte le nombre de chaînes binaires de longueur N qui concatènent à plusieurs reprises des sous-chaînes.
Let us take the Input, N = 3
Output: 2La traduction chinoise de
Vous trouverez ci-dessous des chaînes binaires réalisables de longueur N = 3, où une sous-chaîne est concaténée à plusieurs reprises.
"000":The substring "0" is repeatedly concatenated to form this string. "111":The substring "1" is repeatedly concatenated to form this string.
Ainsi, lorsque nous comptons le nombre total de toutes ces chaînes, la somme que nous obtenons est de 2. La sortie est donc 2.
Let us take the Input, N = 8
Output: 16La traduction chinoise de
Vous trouverez ci-dessous des chaînes binaires réalisables de longueur N = 8 contenant une concaténation répétée de sous-chaînes.
“00000000”: The substring "0" is repeatedly concatenated to form this string. “11111111”: The substring "1" is repeatedly concatenated to form this string. “01010101”: The substring "01" is repeatedly concatenated to form this string. “10101010”: The substring "10" is repeatedly concatenated to form this string. "00110011”: The substring "0011" is repeatedly concatenated to form this string. "11001100”: The substring "1100" is repeatedly concatenated to form this string. "11011101”: The substring "1101" is repeatedly concatenated to form this string. "00100010”: The substring "0010" is repeatedly concatenated to form this string. "10111011”: The substring "1011" is repeatedly concatenated to form this string. "01000100”: The substring "0100" is repeatedly concatenated to form this string. "10001000”: The substring "1000" is repeatedly concatenated to form this string. "00010001”: The substring "0001" is repeatedly concatenated to form this string. "11101110”: The substring "1110" is repeatedly concatenated to form this string. "01110111”: The substring "0111" is repeatedly concatenated to form this string. "01100110”: The substring "0110" is repeatedly concatenated to form this string. "10011001”: The substring "1001" is repeatedly concatenated to form this string.
Ainsi, lorsque nous additionnons le nombre total de toutes ces chaînes, nous obtenons une somme de 16. La sortie est donc 16.
Pour compter le nombre de chaînes binaires de longueur N formées par concaténation répétée de sous-chaînes, nous utilisons la méthode suivante.
Un moyen de résoudre ce problème et de compter le nombre de chaînes binaires de longueur N en concaténant à plusieurs reprises des sous-chaînes.
Le problème ci-dessus peut être résolu sur la base du fait que chaque chaîne réalisable contient une sous-chaîne répétée qui est concaténée C fois. Par conséquent, la longueur de chaîne fournie N doit être divisible par C pour générer toutes les chaînes consécutives.
Donc, trouvez d'abord tous les diviseurs de N, puis pour chaque diviseur possible C, trouvez le nombre total de toutes les chaînes potentielles qui peuvent être créées en les concaténant, ce nombre peut être déterminé en utilisant 2C ; Pour déterminer le nombre total de chaque appel récursif, appliquez la même technique au diviseur C et soustrayez-le de 2C. Cela prendra également en compte le nombre de chaînes en double présentes entre elles.
Algorithme de calcul d'une chaîne binaire de longueur N par concaténation répétée de sous-chaînes donné ci-dessous.
Première étape − Démarrer
Étape 2 - Définissez une fonction pour compter le nombre de chaînes de longueur N telles qu'elles soient la concaténation de ses sous-chaînes.
Étape 3 - Vérifiez si le statut a été calculé
Étape 4 - Stocker le résultat de l'appel récursif en cours ou la valeur du décompte
Étape 5 - Itérer sur tous les diviseurs
Étape 6 - Renvoyez les résultats obtenus
Étape 7 − Arrêtez
Il s'agit d'une implémentation de programme C de l'algorithme ci-dessus pour compter le nombre de chaînes binaires de longueur N formées par concaténation répétée de sous-chaînes.
// C++ program for the above approach #include<bits/stdc++.h> using namespace std; // Storing all the states of recurring recursive map<int, int> dp; // Function for counting the number of strings of length n wherein thatstring is a concatenation of its substrings int countTheStrings(int n){ //the single character cannot be repeated if (n == 1) return 0; // Checking whether the state is calculated already or not if (dp.find(n) != dp.end()) return dp[n]; // Storing those value of the result or the count for the present recursive call int res = 0; // Iterate through all of the divisors for(int d= 1; d <= sqrt(n); d++){ if (n % d== 0){ res += (1 << d) - countTheStrings(d); int div1 = n/d; if (div1 != d and d!= 1) // Non-Rep = Total - Rep res += (1 << div1) - countTheStrings(div1); } } // Storing the result of the above calculations dp[n] = res; // Returning the obtained result return res; } int main(){ int n = 8; cout<< "Count of 8-length binary strings that are repeated concatenation of a substring: "<< endl; cout << countTheStrings(n) << endl; }
Count of 8-length binary strings that are repeated concatenation of a substring − 16
De même, nous pouvons calculer des chaînes binaires de longueur N, qui sont des concaténations répétées de sous-chaînes.
Dans cet article, le défi consistant à obtenir le décompte d'une chaîne binaire de longueur N formée par concaténation répétée de sous-chaînes est abordé.
Le code de programmation C++ est fourni ici avec l'algorithme de calcul de chaînes binaires de longueur N de sous-chaînes concaténées à plusieurs reprises.
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!