小偷越牆所需的跳躍次數

---

想象一下，一個囚犯（或小偷）想要越獄。為此，他需要越過**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

結論

我們討論了查詢小偷越牆所需跳躍次數的各種方法。我們可以使用**迭代方法**。除了這種迭代，我們還可以直接使用**公式**。此外，我們還可以使用**除法**和**取模運算子**來解決這個問題。