盗贼跨越墙壁所需的跳跃次数

想象一下一个囚犯（或小偷）想要从监狱逃脱。为了做到这一点，他需要越过 N 个长度不同的墙。他每次跳跃可以爬升 X 英尺。但是，由于墙壁很滑，他每次跳跃后会下滑 Y 英尺。因此，我们需要计算穿越所有墙壁所需的跳跃次数。在本文中，我们将探讨不同的C++技术，以找到逃脱监狱所需的跳跃次数。

输入输出场景

我们以数组的形式有不同高度的 N 面墙。 X 是跳跃长度，而Y 是他后退的长度。我们有跳跃次数作为输出。

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

使用迭代方法

在这里，我们使用for和while循环来找到跳跃次数。

当墙的高度小于跳跃长度（x）时，可以单次跳跃越过墙。因此，numJumps增加一。我们使用 continue 语句来停止剩余的循环并继续进行下一个循环。

当高度大于跳跃长度时，我们使用while循环通过h – (x – y)计算跳跃次数，直到剩余高度变小大于或等于跳跃长度。

接下来，我们为最后一面墙添加一次跳跃。

Batch GPT

使用AI批量处理数据、自动执行任务

下载

Example

示例

#include 
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

使用直接计算

以下是计算小偷越过墙壁所需跳跃次数的公式 -

Jumps = ceil((h - y) / static_cast(x - y))

我们使用一个for循环来遍历每堵墙。当前墙的高度存储在变量h中。

然后，我们用公式直接计算出需要的跳跃次数。我们使用 ceil 函数将值四舍五入到最接近的整数。

Example

示例

#include 
#include 
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(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

使用除法和模运算符

我们还可以使用 除法 (/) 和 取模 (%) 运算符来计算跳跃的次数。在这里，我们计算墙的高度与跳跃长度之间的差值。如果差值大于0，我们通过将其除以 (x-y) 来计算跳跃次数。如果有余数，我们就加一。而如果差值为零或负数，则我们只需要一次跳跃。

Example

示例

#include 

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

结论

我们讨论了各种方法来确定小偷越墙的跳跃次数。我们可以使用迭代方法。我们可以直接使用公式来代替这样的迭代。另外，我们可以使用除法和取模运算符来解决这个问题。