Anzahl der Sprünge, die ein Dieb benötigt, um eine Mauer zu überqueren

Stellen Sie sich vor, ein Gefangener (oder Dieb) möchte aus dem Gefängnis fliehen. Dazu muss er N Wände unterschiedlicher Länge überqueren. Er kann X Fuß pro Sprung klettern. Da die Wand jedoch rutschig ist, rutscht er nach jedem Sprung Y Füße nach unten. Daher müssen wir die Anzahl der Sprünge berechnen, die erforderlich sind, um alle Wände zu überqueren. In diesem Artikel werden wir verschiedene C++-Techniken untersuchen, um die Anzahl der Sprünge zu ermitteln, die erforderlich sind, um aus dem Gefängnis zu entkommen.

Eingabe- und Ausgabeszenarien

Wir haben N Wände unterschiedlicher Höhe in Form eines Arrays. X ist die Länge seines Sprungs und Y ist die Länge seines Rückzugs. Als Ausgabe erhalten wir die Anzahl der Sprünge.

Input: height[] = {5, 18, 10, 3}
       N = 4, X = 5, Y = 2
Output: 11
Input: height[] = {15, 8, 10, 3, 5, 12}
       N = 6, X = 5, Y = 2
Output: 16

Verwenden Sie iterative Methoden

Hier verwenden wir for- und while-Schleifen, um die Anzahl der Sprünge zu ermitteln.

Wenn die Höhe der Wand geringer ist als die Sprunglänge (x), können Sie in einem einzigen Sprung über die Wand springen. Daher erhöht sich numJumps um eins. Wir verwenden die continue-Anweisung, um die verbleibende Schleife zu stoppen und mit der nächsten Schleife fortzufahren.

Wenn die Höhe größer als die Sprunglänge ist, verwenden wir while, ​​um h – (x – y) zu durchlaufen, um die Anzahl der Sprünge zu berechnen, bis die verbleibende Höhe kleiner oder gleich der Sprunglänge wird.

Als nächstes fügen wir einen Sprung zur letzten Wand hinzu.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#include <iostream>
using namespace std;

int numOfJumps(int x, int y, int N, int heights[]) {
   int numJumps = 0;

   // When the height is less than jump length
   for (int j = 0; j < N; j++) {
      if (x >= heights[j]) {
         numJumps++;
         continue;
      }

      // When the height is more than jump length
      int h = heights[j];
      while (h > x) {
         numJumps++;
         h = h - (x - y);
      }
      numJumps++;
   }
   return numJumps;
}

int main() {
   int N = 5; // Number of walls
   int x = 4; // jump height
   int y = 1; // length after he slips back
   int heights[] = {5, 18, 10, 3, 5};
   int minJumpsRequired = numOfJumps(x, y, N, heights);
   cout << "Minimum number of jumps required: " << minJumpsRequired << endl;
   return 0;
}

Ausgabe

Minimum number of jumps required: 14

Verwenden Sie die direkte Berechnung

Hier ist die Formel zur Berechnung der Anzahl der Sprünge, die ein Dieb benötigt, um eine Mauer zu überqueren -

Jumps = ceil((h - y) / static_cast<double>(x - y))

Wir verwenden eine for-Schleife, um jede Wand zu durchlaufen. Die aktuelle Höhe der Wand wird in der Variablen h gespeichert.

Anschließend berechnen wir mithilfe der Formel direkt die Anzahl der erforderlichen Sprünge. Wir verwenden die Funktion ceil, um den Wert auf die nächste ganze Zahl zu runden.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#include <iostream>
#include <cmath>
using namespace std;

int numOfJumps(int x, int y, int N, int height[]) {
    int numJumps = 0;
    
    for (int j = 0; j < N; j++) {
        int h = height[j];
        int jumpsRequired = ceil((h - y) / static_cast<double>(x - y));
        numJumps += jumpsRequired;
    }
    
    return numJumps;
}


int main() {
    int x = 8, y = 2;
    int height[] = { 4, 14, 8, 16, 20, 11 };
    int N = sizeof(height) / sizeof(height[0]);
    
    int minJumpsRequired = numOfJumps(x, y, N, height);
    cout << "Minimum number of jumps required: " << minJumpsRequired << endl;
    return 0;
}

Ausgabe

Minimum number of jumps required: 12

Verwenden Sie Divisions- und Modulooperatoren

Wir können auch die Operatoren division (/) und modulo (%) verwenden, um die Anzahl der Sprünge zu zählen. Hier berechnen wir den Unterschied zwischen der Höhe der Wand und der Länge des Sprunges. Wenn die Differenz größer als 0 ist, berechnen wir die Anzahl der Sprünge, indem wir sie durch (x-y) dividieren. Wenn es einen Rest gibt, fügen wir einen hinzu. Und wenn die Differenz Null oder negativ ist, brauchen wir nur einen Sprung.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#include <iostream>

using namespace std;

int numOfJumps(int x, int y, int N, int height[]) {
   int jumps = 0;
   for (int j = 0; j < N; j++) {
      int diff = height[j] - x;

      // When height is greater than jump length
      if (diff > 0) {
         jumps++;

         // Additional jumps
         jumps += diff / (x - y);

         // If there is a remainder, increment the jumps
         if (diff % (x - y) != 0)
            jumps++;
      }

      // When height is less than jump length
      else {
         jumps++;
      }
   }
   return jumps;
}
int main() {
   int N = 5; // Number of walls
   int x = 5; // jump height
   int y = 2; // length after he slips back
   int height[] = { 15, 8, 10, 3, 5, 12};
   int minJumpsRequired = numOfJumps(x, y, N, height);
   cout << "Minimum number of jumps required: " << minJumpsRequired << endl;
   return 0;
}

Ausgabe

Minimum number of jumps required: 12

Fazit

Wir haben verschiedene Möglichkeiten besprochen, um die Anzahl der Sprünge zu bestimmen, die ein Dieb über eine Mauer macht. Wir können die iterative Methode verwenden. Wir können die Formel direkt verwenden, um eine solche Iteration zu ersetzen. Alternativ können wir Division und Modulo-Operator verwenden, um dieses Problem zu lösen.

Das obige ist der detaillierte Inhalt vonAnzahl der Sprünge, die ein Dieb benötigt, um eine Mauer zu überqueren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!