Featured image of post C++ 算法题-弹跳球
算法

C++ 算法题-弹跳球

题目

同样是来自 codewar 的算法题，如果上道题主要是字符串问题，那么这一题就是判断循环题了。
题目很长:

A child is playing with a ball on the nth floor of a tall building. The height of this floor above ground level, h, is known.

He drops the ball out of the window. The ball bounces (for example), to two-thirds of its height (a bounce of 0.66).

His mother looks out of a window 1.5 meters from the ground.

How many times will the mother see the ball pass in front of her window (including when it’s falling and bouncing)? Three conditions must be met for a valid experiment:

Float parameter “h” in meters must be greater than 0 Float parameter “bounce” must be greater than 0 and less than 1 Float parameter “window” must be less than h.

If all three conditions above are fulfilled, return a positive integer, otherwise return -1.

大致意思就是任意的一个高度向下丢一个弹跳球，每次弹起来都是上一次高度的 bounce 倍(0 < bounce < 1)。问弹出窗户 (高 h) 要几次？ 比较理想的是不需要讨论距窗户的长度，只需要讨论是否能够弹出窗户，以及这个球能蹦达到窗户这个高度几次？
提供的函数返回一个整型，如果不满足先决条件就返回 -1，如果可以就返回能蹦达到窗户高度几次。

1
2
3
4
5
6

using namespace std;
class Bouncingball
{
public:
    static int bouncingBall(double h, double bounce, double window);
};

实例:

  • h = 3, bounce = 0.66, window = 1.5 结果: 3
  • h = 3, bounce = 1, window = 1.5 结果: -1

题解

分析题目，首先需要判断能够跳出窗户的条件，肯定需要判断语句，而且调整还不止一个，需要逻辑运算符。当判断不能后直接返回 -1 跳出函数即可
根据题目意思需要三个条件:

  1. h 必须大于 0(废话): h > 0
  2. bounce 要在 0 ~ 1 之间: bounce > 0 && bounce < 1
  3. window 要小于 h (不然怎么跳出去？): window < h

这些是跳出条件，需要全部成立则用 && 与运算符连接。而要的是不成立条件，在连接后整体加 ! 非运算符即可。
语句如下：

1
2
3

if (!(h > 0 && bounce > 0 && bounce < 1 && window < h)) {
    return -1;
}

答案里面也有用 || 或运算符串联的，实际就是绕了一下，或运算符如下:

1

if (h <= 0 || bounce <= 0 || bounce >= 1 || window >= h){}

那么当能够跳出，则就需要考虑看到几次？反弹是多次的，应该需要一个循环，而且循环次数不知道，应该用 while 语句。
此时需要一个变量来计数并在最后作为返回值，使用 int count。 但是再想一想，最开始肯定是可以过窗户的，可以将 count 初始值设为 1。
继续讨论，当弹了一次再下一次就跳出窗户了呢？此时弹起后会先过窗户而后跳出窗户，又还要再过一次窗户，之后便没有了，需要加 2 次。
延伸下去，每次弹起必会再过窗户高度 2 次。而再弹起的要求是此时最高点球的高度还大于窗户。而且每次弹起都有损耗，只有原来的 bounce 倍。这样就很好理解整个逻辑了。
画图大致如下:
图解 代码如下:

1
2
3
4
5
6
7
8

int count = 1;
h *= bounce;
while (h > window) {
    count += 2;
    h *= bounce;

}
return count;

整个函数代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

static int bouncingBall(double h, double bounce, double window) {
    if (!(h > 0 && bounce > 0 && bounce < 1 && window < h)) {
        return -1;
    }
    int counce = 1;
    h *= bounce;
    while (h > window) {
        counce+=2;
        h *= bounce;

    }
    return counce;
}

他人解答

看到有一个用递归思维解答的，也还挺好理解，思路清晰简洁:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

using namespace std;
class Bouncingball {
   public:
    static int bouncingBall(double h, double bounce, double window) {
        if (!(h > 0 && bounce > 0 && bounce < 1 && window < h)) {
            return -1;
        }
        else
            return bouncingBall(h * bounce, bounce, window) + 2;
    }
};

if 判断也有 window < h 因而在每次递归的时候也可以用来判断，而返回的计数可以不断累加，在最后一次一定返回 -1，恰好在最初是 2，2 + (-1) 刚好满足，非常巧妙的递归!!!

萌ICP备20241614号