Division maximale possible des sous-chaînes binaires équilibrées, prenant au plus k

Le tableau dans le langage de programmation C a une taille fixe, ce qui signifie qu'une fois la taille spécifiée, elle ne peut pas être modifiée ; vous ne pouvez ni la réduire ni l'étendre.

Comme nous le savons, un tableau est un ensemble d'éléments du même type de données qui sont stockés dans une zone mémoire contiguë.

Étant donné un tableau de valeurs v[] et un tableau binaire a[]. L'objectif est d'utiliser autant de k pièces pour diviser le tableau binaire autant que possible tout en garantissant que chaque segment a un nombre égal de 0 et 1s. i et j sont les indices voisins du segment divisé, et le coût de chaque division est (v[i] - v[j])2.

Énoncé du problème

Implémentez un programme qui trouve la plus grande division de sous-chaînes binaires équilibrée possible, coûtant au plus k.

Exemple Exemple 1

Let the Input array be: 
a: [1,0,0, 1, 0, 0, 1, 1]
The given values be: 
v: [7, 8, 9, 10, 11, 12,13,14]
K: 1

Le résultat obtenu est : 1

Explication

Puisque la valeur de K est 1, on peut faire une coupure entre le premier et le deuxième indice.

Dans ce cas, [0, 1] et [0, 0, 1, 1] sont les sous-chaînes binaires équilibrées du résultat final.

Faire cette coupe coûtera (8 - 9) ^ 2 = 1 et 1 = 1.

Exemple Exemple 2

Let the Input array be: 
a: [1,0 1, 0, 1, 1, 0,0]
The given values be: 
v: [2, 4, 7, 10, 11, 12, 13, 14]
K: 14

Output obtained is: 2

Explication

La première coupe sera faite entre le premier et le deuxième index qui est 4 et 7, ce qui nous coûte (4 - 7)^2 = 9 et la deuxième coupe sera faite entre le troisième et le quatrième index qui est 7 et 10, ce qui coûte us (7 - 10)^ 2 = 9. Aucune autre coupe n'est possible pour le moment. Les sous-chaînes binaires équilibrées qui se produiraient dans ce cas sont [1, 0], [1, 0] et [1, 1, 0]. , 0].

Approche

Afin de trouver le maximum de divisions de sous-chaînes binaires équilibrées possibles avec un coût maximal k, nous adoptons la méthodologie suivante.

Ici, nous adoptons une approche descendante pour résoudre ce problème et trouver le maximum de divisions de sous-chaînes binaires équilibrées avec le coût le plus élevé k.

Utilisez une approche descendante, ou plus communément appelée programmation dynamique. Le principal avantage de la programmation dynamique est l’efficacité améliorée de la récursivité simple. La programmation dynamique peut être utilisée pour optimiser toute solution récursive impliquant des appels répétés à la même entrée. Pour éviter de recalculer ultérieurement les résultats des sous-problèmes, l’idée est de les stocker. Avec cette simple optimisation, la complexité temporelle est réduite de polynomiale à exponentielle.

Algorithme

L'algorithme permettant de trouver le maximum de divisions de sous-chaînes binaires équilibrées possibles avec le coût le plus élevé K est donné ci-dessous.

• Étape - Démarrer

• Étape 2 - Définir une matrice bidimensionnelle m

• Étape 3 - Définissez une fonction pour trouver la division de sous-chaîne binaire équilibrée maximale possible.

• Étape 4 - Définissez les variables entières zeroCount pour compter le nombre de zéros et oneCount pour compter le nombre de un respectivement

• Étape 5 − Définissez une variable entière cntSplits pour compter le nombre de divisions

• Étape 6 - Parcourir le tableau donné a

• Étape 7 − vérifiez si le nombre de zéros est égal au nombre de un, puis stockez le maximum réalisable

• Étape 8 - Supposons que l'index soit à la position 0, puis découvrez s'il est 1 ou 0, puis incrémentez le décompte

• Étape 9 − définissez les cntSplits sur zéro, si le nombre de un et le nombre de zéro sont inégaux.

• Étape 10 - Stocker les valeurs résultantes dans une matrice

• Étape 11 − Imprimez le résultat souhaité obtenu

• Étape 12 − Arrêtez

Exemple : programme C

Il s'agit d'une implémentation de programme C de l'algorithme ci-dessus pour trouver la division de sous-chaîne binaire équilibrée maximale possible, coûtant au plus k.

#include <stdio.h>
#include <limits.h>
#include <string.h>
//Define a two-dimensional matrix m
int m[1001][1001];

//Define a function to find maximum possible //balanced binary substring splits
int maxSplits(int a[], int v[], int k, int s) {
   if (k < 0) {
      return INT_MIN;
   }
   if (m[k][s] != -1) {
      return m[k][s];
   }
   
   //Define integer variables to count the number of zeros and ones 
   // Define an integer variable to count the //number of splits
   int zeroCount = 0, oneCount = 0;
   int cntSplits = 0;
   int i;
   
   //Iterating through the given array a
   for (i = s - 1; i > 0; i--) {
      a[i] == 0 ? zeroCount++ : oneCount++;
      
   // check whether the number of zeros is equal to the number of ones, then store the maximum feasible one
      if (zeroCount == oneCount) {
         cntSplits = cntSplits > (1 + maxSplits(a, v, k - (v[i] - v[i - 1]) * (v[i] - v[i - 1]), i)) ? cntSplits : (1 + maxSplits(a, v, k - (v[i] - v[i - 1]) * (v[i] - v[i - 1]), i));
      }
   }
   
   //Suppose the index is at the position 0, then find whether it is a one or a zero. then increment the count
   if (i == 0) {
      a[0] == 0 ? zeroCount++ : oneCount++;
      
   // set the cntSplits to zero , if count of one and count of zero is unequal.
      if (zeroCount != oneCount) {
         cntSplits = 0;
      }
   }
   
   // store the resultant value in the matrix
   return m[k][s] = cntSplits;
}
int main() {
   int a[] = { 1, 0, 0, 1, 0, 0, 1, 1 };
   int v[] = { 7, 8, 9, 10, 11, 12, 13, 14 };
   int k = 1;
   int s = sizeof(a) / sizeof(a[0]);
   
   //To assign a specific value to a block of memory, we use the memset() function.
   memset(m, -1, sizeof(m));
   printf("%d\n", maxSplits(a, v, k, s));
   return 0;
}

Sortie

1

Conclusion

De même, nous pouvons trouver le possible fractionnement équilibré de sous-chaînes binaires qui coûte au plus K.

Dans cet article, le défi consistant à obtenir un programme permettant de trouver la division de sous-chaînes binaires la plus équilibrée possible au coût maximal K est abordé.

Le code de programmation C est fourni ici avec un algorithme pour trouver la plus grande division de sous-chaîne binaire équilibrée possible, coûtant au plus K.

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!