数学算法挑战

Question

为什么这个解决方案有效？大多数人都在做循环来解决这个问题，而我做了递归，但是这很容易，对计算机来说，我很困惑为什么这是工作的？

描述:一个孩子正在一座高楼的第九层玩球。这层楼的高度是众所周知的。

他把球扔出窗外。这个球反弹(例如)，达到其高度的三分之二(反弹0.66)。

他的母亲从离地面1.5米的窗户往外看。

母亲会多少次看到球在她的窗前传球(包括球下落和弹跳的时候)？

有效实验必须满足三个条件:仪表中的浮动参数" h“必须大于0，浮动参数”弹跳“必须大于0，而小于1的浮动参数”窗口“必须小于h。如果满足上述所有三个条件，则返回一个正整数，否则返回-1。

注意:只有当篮板球的高度大于窗口参数时，才能看到球。

export class G964 {
    public static bouncingBall(h: number, bounce: number, window: number): any {
        if (h <= 0 || bounce >= 1 || bounce <= 0 || window >= h) {
          return -1
        }

        return 1 + 2 * (Math.ceil(Math.log(window / h) / Math.log(bounce)) - 1)
  }
}

Answer 1

这其实是个数学题，但是.

每弹一次，你的球就会弹起之前弹跳的一小部分。因此，为了简单起见，假设弹跳参数为0.5。每次弹跳的高度只有以前的一半。如果您的窗口为1.0，则弹出如下：

1/2, 1/4, 1/8, 1/16...

另一种说法是反弹的高度是bounce_rate ** n，n是反弹的数量。第三次反弹是0.5 ** 3或1/8。

现在，如果给出一个高度，并询问该高度对应于哪个弹跳，则需要求解n的方程n。解决n需要一个日志--在本例中，n = log(base bounce_rate)height.日志库bounce_rate是不方便的，但是您可以将它重写为log(height)/log(bounce_rate)。用具体的术语来表示弹出到1/16窗口的高度，您只需计算log(1/16)/log(0.5)并得到4。

所以你应该可以开始看看这和你的方程有什么相似之处。但是，由于我们的方程是用高度作为窗口高度的一小部分，我们需要将这个高度转化为相对于母亲窗口的东西。因此，与其计算出球什么时候会反弹到1/16左右，即下降窗口的高度，而是我们想知道球何时达到不同的比率--下降窗口与母亲的-- window/h --如果母亲的窗口在5岁时，球从20下掉下来，那将是计算1/4，正如我们前面所显示的，是log(1/4)/log(bounce_rate)或log(window/h)/log(bounce)。

这就是它的肉。方程的其余部分处理的是这样一个事实，即窗口不一定是日志方程的精确解，因此我们用Math.ceil和一个事实，即球在窗口下边出现一次，但每次跳过窗口高度时，都会出现两次。