Bestimmen Sie den Mindestschritt für eine Teilsequenz mit höchstens 1 basierend auf einer bestimmten Bedingung

Der Zweck dieses Artikels besteht darin, ein Programm zu implementieren, um die Mindestschritte zu finden, um eine Teilsequenz von maximal 1 Sekunde basierend auf einer bestimmten Bedingung zu bestimmen.

Wie wir alle wissen, kann ein eindimensionales Array mit nullterminierten Zeichen zum Definieren einer Zeichenfolge verwendet werden.

Gegeben sei eine Zeichenfolge Str der Länge K, wobei K immer eine gerade Zahl ist und die Zeichen „0“, „1“ und „?“ enthält. Teilen Sie die Zeichenfolge in zwei separate Zeichenfolgen auf. Wir nennen sie Str1 und Str2 enthalten Zeichen mit geraden Werten von Str und Zeichen mit ungeraden Werten von Str. Das Ziel besteht darin, die Mindestanzahl von Schritten zu bestimmen, die erforderlich sind, um die höchste Anzahl von Einsen in zwei Zeichenfolgen (Str1 oder Str2) vorherzusagen. Wählt in einem Schritt ein Zeichen für Str1 oder Str2 aus. Wählt „0“, wenn das Zeichen eine Null ist, „1“, wenn das Zeichen eine Eins ist, und „?“, wenn es ein 1- oder 0-Zeichen ist.

Problemstellung

Implementieren Sie ein Programm, um die Mindestschritte zu finden, um die maximale Teilsequenz von 1 Sekunde basierend auf gegebenen Bedingungen zu bestimmen

Beispiel 1

Input: Str = “?10?0?”

Output: 4

Anleitung

• Schritt 1 – Hier ist Str[0] „?“

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

• Schritt 2 – Hier ist Str[1] „1“

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

• Schritt 3 – Hier ist Str[2] „0“

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

• Schritt 4 – Hier ist Str[3] „?“

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

Egal welche Zahl der verbleibende Index wählt, Str2 wird nach Schritt 4 mehr Einsen haben.

Beispiel 2

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

Output: 4

Anleitung

• Schritt 1 – Hier ist Str[0] „1“

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

• Schritt 2 – Hier ist Str[1] „?“

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

• Schritt 3 – Hier ist Str[2] „0“

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

• Schritt 4 – Hier ist Str[3] „?“

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

• Schritt 5 – Hier ist Str[4] „?“

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

• Schritt 6 – Hier ist Str[5] „0“

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

• Schritt 7 – Hier ist Str[6] „1“

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

Egal welche Zahl der verbleibende Index wählt, Str2 wird nach Schritt 7 mehr Einsen haben.

Lösung

Um die minimalen Schritte zur Bestimmung der maximalen 1-Sekunden-Teilsequenz basierend auf den gegebenen Bedingungen zu finden, verwenden wir den folgenden Ansatz.

Im Folgenden finden Sie die Methode zur Lösung dieses Problems und zur Ermittlung der Mindestschritte zur Bestimmung der Teilsequenz von maximal 1 Sekunde basierend auf den gegebenen Bedingungen.

Das Ziel besteht darin, das Problem rekursiv zu lösen und nach Abwägung jeder Alternative zu einer Lösung zu gelangen.

Der Begriff „Rekursion“ ist nichts anderes als der Prozess, bei dem sich eine Funktion selbst aufruft, sei es direkt (d. h. ohne Zwischenhändler) oder indirekt. Diese äquivalente Funktion wird als rekursive Funktion bezeichnet. Darüber hinaus können rekursive Algorithmen verwendet werden, um verschiedene Probleme relativ einfach zu lösen.

Algorithmus

Finden Sie den Algorithmus zur Bestimmung des Mindestschritts zur Bestimmung der maximalen 1-Sekunden-Teilsequenz basierend auf den unten angegebenen Bedingungen

• Schritt 1 – Erste Schritte

• Schritt 2 – Definieren Sie die rekursive Funktion.

• Schritt 3 - Definieren Sie die Zeichenfolge Str, die Ganzzahl i, die Ganzzahlen count1 und count2, die zum Speichern der Zahlen bis i in Str1 bzw. Str2 verwendet werden.

• Schritt 4 – Definieren Sie die Ganzzahlen n1 und n2, um die verfügbaren Positionen in Str1 und Str2 zu speichern

• Schritt 5 – Wenn i gleich m ist, dann sind sowohl Str1 als auch Str2 vollständig gefüllt und die Antwort kann nun mit Sicherheit erwartet werden. Also antworten Sie bitte mit 0.

• Schritt 6 – Wenn count1 das Produkt aus n2 und count2 überschreitet, geben Sie 0 zurück, da Str1 jetzt mehr Werte als Str2 hat, selbst nachdem alle Werte in Str2 ausgewählt wurden. < /p>

Wenn count2 das Produkt aus n1 und count1 überschreitet, wird aufgrund des oben Gesagten 0 zurückgegeben.

• Schritt 7 – Überprüfen Sie, ob i gleich einer geraden oder ungeraden Zahl ist, nachdem Sie die Basisinstanz getestet haben. Wenn i gerade ist, wählt Str1 diesen Index aus; wenn nicht, wählt Str2 diesen Index aus.

Da sich die Anzahl der zugänglichen Positionen in der Zeichenfolge nach dem Auffüllen um eine Position verringert, wird sie abhängig von der aktuell aufgefüllten Zeichenfolge um n1 oder n2 reduziert.

• Schritt 8 – Angenommen, das aktuelle Zeichen ist „?“, also s[i] = „?“. Führen Sie dann zwei rekursive Aufrufe aus, um „1“ und „0“ auszuwählen, führen Sie 1 in beide zusammen und geben Sie „The“ zurück der kleinste von beiden.

Andernfalls rufen Sie an und fügen Sie einen Anruf hinzu, um die Antwort zu erhalten.

Die Antwort auf diese Abfrage wird durch den letzten rekursiven Aufruf bereitgestellt.

• Schritt 8 – Stopp

Beispiel: C++-Programm

Dies ist eine C-Programmimplementierung des oben beschriebenen Algorithmus, um die minimalen Schritte zum Bestimmen einer Teilsequenz von maximal 1 Sekunde basierend auf einer bestimmten Bedingung zu finden

// 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;
}

Ausgabe

1

Fazit

Ähnlich können wir die minimale Anzahl von Schritten finden, um die Teilsequenz mit einem Maximum von 1 Sekunde gemäß den gegebenen Bedingungen zu bestimmen

Dieses Dokument befasst sich mit der Herausforderung, die Mindestanzahl an Schritten zu ermitteln, um die maximal 1-sekündige Teilsequenz unter einer gegebenen Bedingung zu bestimmen.

C++-Programmiercode wird hier zusammen mit einem Algorithmus bereitgestellt, um den minimalen Schritt zu finden, der die maximale 1-Sekunden-Teilsequenz basierend auf gegebenen Bedingungen bestimmt.

Das obige ist der detaillierte Inhalt vonBestimmen Sie den Mindestschritt für eine Teilsequenz mit höchstens 1 basierend auf einer bestimmten Bedingung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!