小偷越墙所需的跳跃次数

---

想象一下，一个囚犯（或小偷）想要越狱。为此，他需要越过**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)**计算跳跃次数，直到剩余高度小于或等于跳跃长度。

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

示例

#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

使用直接计算

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

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

我们使用`for`循环迭代每一堵墙。当前墙的高度存储在变量h中。

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

示例

#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

使用除法和取模运算符

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

示例

#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

结论

我们讨论了查找小偷越墙所需跳跃次数的各种方法。我们可以使用**迭代方法**。除了这种迭代，我们还可以直接使用**公式**。此外，我们还可以使用**除法**和**取模运算符**来解决这个问题。