Maison > Article > développement back-end > 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.
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
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#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; }
Minimum number of jumps required: 14
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#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; }
Minimum number of jumps required: 12
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#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; }
Minimum number of jumps required: 12
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!