Nombre de sauts nécessaires à un voleur pour traverser un mur

Imaginez qu'un prisonnier (ou un voleur) veuille s'évader de prison. Pour ce faire, il doit traverser des N murs de différentes longueurs. Il peut grimper X pieds par saut. Cependant, comme le mur est glissant, il glissera de Y pieds après chaque saut. Par conséquent, nous devons calculer le nombre de sauts nécessaires pour traverser tous les murs. Dans cet article, nous explorerons différentes techniques C++ pour trouver le nombre de sauts nécessaires pour s'échapper de prison.

Scénarios d'entrée et de sortie

Nous avons N murs de différentes hauteurs sous forme de tableau. X est la longueur de son saut, et Y est la longueur de sa retraite. Nous avons le nombre de sauts en sortie.

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

Utilisez des méthodes itératives

Ici, nous utilisons les boucles for et while pour trouver le nombre de sauts.

Lorsque la hauteur du mur est inférieure à la longueur du saut (x), vous pouvez sauter par-dessus le mur en un seul saut. Par conséquent, numJumps augmente de un. Nous utilisons l'instruction continue pour arrêter la boucle restante et continuer avec la boucle suivante.

Lorsque la hauteur est supérieure à la longueur du saut, nous utilisons while pour parcourir h – (x – y) pour calculer le nombre de sauts jusqu'à ce que la hauteur restante devienne inférieure ou égale à la longueur du saut.

Ensuite, nous ajoutons un saut vers le dernier mur.

La traduction chinoise de

Exemple

est :

Exemple

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

Sortie

Minimum number of jumps required: 14

Utilisez le calcul direct

Voici la formule pour calculer le nombre de sauts nécessaires à un voleur pour traverser un mur -

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

Nous utilisons une boucle for pour parcourir chaque mur. La hauteur actuelle du mur est stockée dans la variable h.

Ensuite, nous utilisons la formule pour calculer directement le nombre de sauts requis. Nous utilisons la fonction ceil pour arrondir la valeur à l’entier le plus proche.

La traduction chinoise de

Exemple

est :

Exemple

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

Sortie

Minimum number of jumps required: 12

Utilisez les opérateurs de division et de modulo

On peut également utiliser les opérateurs division (/) et modulo (%) pour compter le nombre de sauts. Ici, nous calculons la différence entre la hauteur du mur et la longueur du saut. Si la différence est supérieure à 0, on calcule le nombre de sauts en le divisant par (x-y). S'il y a un reste, on en ajoute un. Et si la différence est nulle ou négative, un seul saut suffit.

La traduction chinoise de

Exemple

est :

Exemple

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

Sortie

Minimum number of jumps required: 12

Conclusion

Nous avons discuté de différentes façons de déterminer le nombre de sauts qu'un voleur effectue par-dessus un mur. Nous pouvons utiliser la méthode itérative. Nous pouvons directement utiliser la formule pour remplacer une telle itération. Alternativement, nous pouvons utiliser division et modulo Operator pour résoudre ce problème.

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!