数学算法挑战

Question

为什么这个解决方案有效？大多数人都在做循环来解决这个问题，而我做了递归，但这太简单了，对于计算机来说，我很困惑为什么这行得通？

说明： Achild在高楼第n层玩球。这层楼的高度 h 是已知的。

他把球丢出了 window。球反弹（例如）到其高度的 two-thirds（反弹 0.66）。

他妈妈从离地1.5米的地方window往外看。

妈妈会看到球从她面前经过多少次window（包括下落和弹跳的时候？

有效实验必须满足三个条件：以米为单位的float参数"h"必须大于0 float参数"bounce"必须大于0小于1 浮点参数 "window" 必须小于 h。如果以上三个条件都满足，return一个正整数，否则return-1.

注意：只有当反弹球的高度严格大于window参数时才能看到球。

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。每次弹跳都是之前弹跳高度的一半。如果您的 window 为 1.0，则反弹将为：

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

另一种表示反弹高度的方式是 bounce_rate ** n，其中 n 是反弹的次数。第三次反弹是 0.5 ** 3 或 1/8。

现在，如果给定一个高度，并且询问该高度对应于哪个弹跳，则需要求解方程 height = bounce_rate ** n 得到 n。求解 n 需要一个日志——在这种情况下 n = log(base bounce_rate)height. 日志基 bounce_rate 是不方便的，但你可以将其重写为 log(height)/log(bounce_rate)。具体来说，要计算哪个反弹达到 1/16 和 window 高度，您只需计算 log(1/16)/log(0.5) 并得到 4.

所以您应该能够开始了解这与您的等式有何相似之处。但是由于我们的等式使用身高作为 window 身高的分数，我们需要将该身高转化为相对于母亲 window 的身高。因此，我们不想弄清楚球何时会反弹到下降高度 window 的 1/16，而是想知道球何时达到不同的比率——下降 window 与妈妈的比率— window/h — 如果母亲的 window 为 5，而球从 20 开始掉落，那将计算 1/4，正如我们之前展示的那样，将是 log(1/4)/log(bounce_rate) 或 log(window/h)/log(bounce)

这就是它的核心。等式的其余部分处理 window 不一定是对数方程的精确解这一事实，因此我们用 Math.ceil 舍入，并且球出现在 [=41= 的前面这一事实] 下降一次，但每次反弹超过 window 高度时两次。

数学算法挑战

Math Algorithm Challenge

javascript

algorithm

typescript

math

logarithm