Bilangan lompatan yang diperlukan untuk pencuri melintasi dinding

Bayangkan banduan (atau pencuri) mahu melarikan diri dari penjara. Untuk melakukan ini, dia perlu menyeberangi N dinding dengan panjang yang berbeza. Dia boleh memanjat X kaki setiap lompatan. Namun, memandangkan dinding itu licin, dia akan menggelongsor ke bawah Y kaki selepas setiap lompatan. Oleh itu, kita perlu mengira bilangan lompatan yang diperlukan untuk melintasi semua dinding. Dalam artikel ini, kami akan meneroka teknik C++ yang berbeza untuk mencari bilangan lompatan yang diperlukan untuk melarikan diri dari penjara.

Senario input dan output

Kami mempunyai N dinding dengan ketinggian yang berbeza dalam bentuk susunan. X ialah panjang lompatannya, dan Y ialah panjang pengundurannya. Kami mempunyai bilangan lompatan sebagai 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

Gunakan kaedah berulang

Di sini kita menggunakan untuk dan semasa gelung untuk mencari bilangan lompatan.

Apabila ketinggian dinding kurang daripada panjang lompatan (x), anda boleh melompat melepasi dinding dalam satu lompatan. Oleh itu, numJumps bertambah satu. Kami menggunakan pernyataan teruskan untuk menghentikan gelung yang tinggal dan meneruskan dengan gelung seterusnya.

Apabila ketinggian lebih besar daripada panjang lompatan, kami menggunakan semasa untuk menggelung melalui h – (x – y) untuk mengira bilangan lompatan sehingga ketinggian yang tinggal menjadi lebih kecil daripada atau sama dengan panjang lompatan.

Seterusnya, kami menambah lompatan ke dinding terakhir.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#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

Gunakan pengiraan terus

Berikut ialah formula untuk mengira bilangan lompatan yang diperlukan untuk pencuri melintasi dinding -

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

Kami menggunakan gelung untuk untuk melelaran melalui setiap dinding. Ketinggian semasa dinding disimpan dalam pembolehubah h.

Kemudian, kami menggunakan formula untuk mengira terus bilangan lompatan yang diperlukan. Kami menggunakan fungsi siling untuk membundarkan nilai kepada integer terdekat.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#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

Gunakan operator bahagian dan modulo

Kita juga boleh menggunakan operator divisyen (/) dan modulo (%) untuk mengira bilangan lompatan. Di sini kita mengira perbezaan antara ketinggian dinding dan panjang lompatan. Jika perbezaannya lebih besar daripada 0, kita mengira bilangan lompatan dengan membahagikannya dengan (x-y). Jika ada baki, kami tambah satu. Dan jika perbezaannya adalah sifar atau negatif, kita hanya memerlukan satu lompatan.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#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

Kesimpulan

Kami membincangkan pelbagai cara untuk menentukan bilangan lompatan pencuri mengambil alih dinding. Kita boleh menggunakan kaedah berulang. Kita boleh terus menggunakan formula untuk menggantikan lelaran tersebut. Sebagai alternatif, kita boleh menggunakan division dan modulus operator untuk menyelesaikan masalah ini.

Atas ialah kandungan terperinci Bilangan lompatan yang diperlukan untuk pencuri melintasi dinding. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!