想象一下一个囚犯(或小偷)想要从监狱逃脱。为了做到这一点,他需要越过 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)计算跳跃次数,直到剩余高度变小大于或等于跳跃长度。
接下来,我们为最后一面墙添加一次跳跃。
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;
}
输出
'Minimum number of jumps required: 14
使用直接计算
以下是计算小偷越过墙壁所需跳跃次数的公式 -
'Jumps = ceil((h - y) / static_cast<double>(x - y))
我们使用一个for循环来遍历每堵墙。当前墙的高度存储在变量h中。
然后,我们用公式直接计算出需要的跳跃次数。我们使用 ceil 函数将值四舍五入到最接近的整数。
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;
}
输出
'Minimum number of jumps required: 12
使用除法和模运算符
我们还可以使用 除法 (/) 和 取模 (%) 运算符来计算跳跃的次数。在这里,我们计算墙的高度与跳跃长度之间的差值。如果差值大于0,我们通过将其除以 (x-y) 来计算跳跃次数。如果有余数,我们就加一。而如果差值为零或负数,则我们只需要一次跳跃。
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;
}
输出
'Minimum number of jumps required: 12
结论
我们讨论了各种方法来确定小偷越墙的跳跃次数。我们可以使用迭代方法。我们可以直接使用公式来代替这样的迭代。另外,我们可以使用除法和取模运算符来解决这个问题。