Number of jumps required for a thief to cross a wall

Imagine a prisoner (or thief) trying to escape from prison. In order to do this, he needs to cross N walls of different lengths. He can climb X feet with each jump. However, since the wall is slippery, he slides down Y feet after each jump. Therefore, we need to calculate the number of jumps required to cross all walls. In this article, we will explore different C techniques to find the number of jumps required to escape the prison.

Input and output scenarios

We have N walls of different heights in the form of an array. X is the length of his jump, and Y is the length of his retreat. We have the number of jumps as output.

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

Use iteration method

Here, we use for and while loops to find the number of jumps.

When the height of the wall is less than the jump length (x), you can jump over the wall in a single jump. Therefore, numJumps increases by one. We use the continue statement to stop the remaining loop and continue with the next loop.

When the height is greater than the jump length, we use a while loop to calculate the number of jumps through h – (x – y) until the remaining height becomes smaller than or equal to the jump length.

Next, we add a jump to the last wall.

The Chinese translation of

Example

is:

Example

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

Output

Minimum number of jumps required: 14

Use direct calculation

The following is the formula for calculating the number of jumps required for a thief to cross a wall -

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

We use a for loop to iterate through each wall. The current height of the wall is stored in the variable h.

Then, we use the formula to directly calculate the required number of jumps. We use the ceil function to round the value to the nearest integer.

The Chinese translation of

Example

is:

Example

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

Output

Minimum number of jumps required: 12

Use division and modulo operators

We can also use the division (/) and modulo (%) operators to count the number of jumps. Here we calculate the difference between the height of the wall and the length of the jump. If the difference is greater than 0, we calculate the number of jumps by dividing it by (x-y). If there is a remainder, we add one. And if the difference is zero or negative, we only need one jump.

The Chinese translation of

Example

is:

Example

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

Output

Minimum number of jumps required: 12

in conclusion

We discussed various ways to determine the number of jumps a thief takes to get over a wall. We can use iteration method. We can directly use Formula to replace such iteration. In addition, we can use division and modulo operator to solve this problem.

The above is the detailed content of Number of jumps required for a thief to cross a wall. For more information, please follow other related articles on the PHP Chinese website!