Déterminer le pas minimum pour une sous-séquence avec au plus 1 en fonction d'une condition donnée

Le but de cet article est de mettre en œuvre un programme pour trouver les étapes minimales pour déterminer une sous-séquence de maximum 1 seconde en fonction d'une condition donnée.

Comme nous le savons tous, un tableau unidimensionnel contenant des caractères terminés par un caractère nul peut être utilisé pour définir une chaîne.

Étant donné une chaîne Str de longueur K, où K est toujours un nombre pair et contient les caractères "0", "1" et "?" Divisez la chaîne en deux chaînes distinctes, nous les appellerons Str1 et Str2, chaque chaîne sera contiennent des caractères aux valeurs paires de Str et des caractères aux valeurs impaires de Str. L'objectif est de déterminer le nombre minimum d'étapes nécessaires pour prédire le plus grand nombre de 1 dans deux chaînes (Str1 ou Str2). Sélectionne un caractère pour Str1 ou Str2 en une seule étape. Sélectionne "0" si le caractère est zéro, "1" si le caractère est un et "?" s'il s'agit d'un caractère 1 ou 0.

Énoncé du problème

Mettre en œuvre un programme pour trouver les étapes minimales afin de déterminer la sous-séquence maximale de 1 seconde en fonction de conditions données

Exemple 1

Input: Str = “?10?0?”

Output: 4

Instructions

• Étape 1 - Ici Str[0] est "?"

So select "0" as the character for Str1.
Which implies Str1=”0″, Str2=”″.

• Étape 2 - Ici Str[1] vaut "1"

Select "1" as the character for Str2.
Which implies Str1=”0″, Str2=”1″.

• Étape 3 - Ici Str[2] est "0"

Select "0" as the character for Str1.
Which implies Str1=”00″, Str2=”1″.

• Étape 4 - Ici Str[3] est "?"

Select "1" as the character for Str2.
Which implies Str1=”00″, Str2=”11″.

Quel que soit le nombre choisi par l'index restant, Str2 aura plus de 1 après l'étape 4.

Exemple 2

Input: Str = “1?0??0110”

Output: 4

Instructions

• Étape 1 - Ici Str[0] est "1"

So select "1" as the character for Str1.
Which implies Str1=”1″, Str2=”″.

• Étape 2 - Ici Str[1] est "?"

Select "1" as the character for Str2.
Which implies Str1=”1″, Str2=”1″.

• Étape 3 - Ici Str[2] est "0"

Select "0" as the character for Str1.
Which implies Str1=”10″, Str2=”1″.

• Étape 4 - Ici Str[3] est "?"

Select "1" as the character for Str2.
Which implies Str1=”10″, Str2=”11″.

• Étape 5 - Ici Str[4] est "?"

Select "0" as the character for Str1.
Which implies Str1=”100″, Str2=”11″.

• Étape 6 - Ici Str[5] est "0"

Select "0" as the character for Str2.
Which implies Str1=”100″, Str2=”111″.

• Étape 7 - Ici Str[6] est "1"

Select "1" as the character for Str1.
Which implies Str1=”1001″, Str2=”111″.

Quel que soit le nombre choisi par l'index restant, Str2 aura plus de 1 après l'étape 7.

Solution

Pour trouver les étapes minimales pour déterminer la sous-séquence maximale d'une seconde en fonction des conditions données, nous utilisons l'approche suivante.

Vous trouverez ci-dessous la méthode pour résoudre ce problème et trouver les étapes minimales pour déterminer la sous-séquence d'un maximum de 1 seconde en fonction des conditions données.

L'objectif est de résoudre le problème de manière récursive et d'arriver à une solution après avoir envisagé chaque alternative.

Le terme « récursion » n'est rien d'autre que le processus par lequel une fonction s'appelle elle-même, que ce soit directement (c'est-à-dire sans intermédiaires) ou indirectement. Cette fonction équivalente est dite récursive. De plus, les algorithmes récursifs peuvent être utilisés pour résoudre divers problèmes avec une relative facilité.

Algorithme

Trouvez l'algorithme pour déterminer le pas minimum pour déterminer la sous-séquence maximale d'une seconde en fonction des conditions données ci-dessous

• Étape 1 - Commencer

• Étape 2 - Définir la fonction récursive.

• Étape 3 - Définissez la chaîne Str, l'entier i, les entiers count1 et count2, qui sont utilisés pour stocker les nombres jusqu'à i dans Str1 et Str2 respectivement.

• Étape 4 - Définissez les entiers n1 et n2 pour stocker les positions disponibles dans Str1 et Str2

• Étape 5 - Si i est égal à m, alors Str1 et Str2 sont entièrement remplis et la réponse peut maintenant être attendue avec certitude. Alors s'il vous plaît, répondez 0.

• Étape 6 - Si count1 dépasse le produit de n2 et count2, alors renvoyez 0 car Str1 aura désormais plus de valeurs que Str2 même après avoir sélectionné toutes les valeurs de Str2.

En raison de ce qui précède, si count2 dépasse le produit de n1 et count1, 0 ​​​​est renvoyé.

• Étape 7 - Vérifiez si i est égal à un nombre pair ou impair après avoir testé l'instance de base. Si i est pair, Str1 sélectionnera cet index ; sinon, Str2.

Étant donné que le nombre de positions accessibles dans la chaîne sera réduit d'une position après le remplissage, il est réduit de n1 ou n2 selon la chaîne actuellement remplie.

• Étape 8 - Supposons que le caractère actuel soit '?', c'est-à-dire s[i] = '? ' Ensuite, effectuez deux appels récursifs pour sélectionner "1" et "0", fusionnez 1 dans les deux et renvoyez le plus petit. des deux.

Sinon, passez un appel et ajoutez un appel pour obtenir la réponse.

La réponse à cette requête sera fournie par l'appel récursif final.

• Étape 8 - Arrêtez

Exemple : programme C++

Il s'agit d'une implémentation de programme C de l'algorithme écrit ci-dessus pour trouver les étapes minimales pour déterminer une sous-séquence d'une seconde maximum en fonction d'une condition donnée

// the C++ program of the above written algorithm
#include <bits/stdc++.h>
using namespace std;

// the function in order find the minimum number of the steps recursively  needed by combining both the 2 strings
int minimumSteps(string& Str, int cnt1, int cnt2,int n1, int n2, int m,int i){

   // check whetherthe current pointer reach //the end
   if (i == m) {
      return 0;
   }
    
   // the Condition which indicates here that one string does more ones than the other regardless of which number is opted  for theindexes which is remaining
   if (cnt1 > (n2 + cnt2)
         || cnt2 > (n1 + cnt1)) {
      return 0;
   }
   int ch1 = 0;
   int ch2 = 0;
    
   // on condition that i is found to be even, then choose the character for Str
   if (i % 2 == 0) {
      if (Str[i] == '?') {
         return min( 1 + minimumSteps(Str, i + 1,  cnt1 + 1, cnt2, n1 - 1, n2, m), 1 + minimumSteps( Str, i + 1, cnt1, cnt2, n1 - 1, n2, m));
      } else if (Str[i] == '1') {
         ch1 = 1 + minimumSteps(Str, i + 1, cnt1 + 1, cnt2, n1 - 1, n2, m);
         return ch1;
      } else {
         ch2 = 1 + minimumSteps(Str, i + 1, cnt1, cnt2, n1 - 1, n2, m);
         return ch2;
      }
   }
   else {
      if (Str[i] == '?') {
         return min(1 + minimumSteps(Str, i + 1, cnt1, cnt2 + 1, n1, n2 - 1, m),1 + minimumSteps(Str, i + 1,cnt1, cnt2, n1, n2 - 1, m));
      } else if (Str[i] == '1') {
         ch1 = 1+ minimumSteps(Str, i + 1, cnt1, cnt2 + 1, n1, n2 - 1, m);
         return ch1;
      } else {
         ch2 = 1+ minimumSteps( Str, i + 1, cnt1, cnt2, n1, n2 - 1, m);
         return ch2;
      }
   }
}
int main(){
   string str = "?10?0?01";
   int M = str.size();
   cout << minimumSteps(str, 0, 0, 0, M / 2, M / 2, M);
   return 0;
}

Sortie

1

Conclusion

De même, on peut trouver le nombre minimum d'étapes pour déterminer la sous-séquence avec un maximum de 1 selon les conditions données

Cet article aborde le défi consistant à obtenir le nombre minimum d'étapes pour déterminer la sous-séquence maximale d'une seconde étant donné une condition.

Le code de programmation C++ est fourni ici avec un algorithme pour trouver l'étape minimale qui détermine la sous-séquence maximale d'une seconde en fonction de conditions données.

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!