100 层楼,两个玻璃球,求最少多少次测出能摔碎玻璃球的楼层

2022-05-28T15:26:08

给你两个一摸一样的球,这两个球如果从一定的高度掉到地上有可能就会摔碎,当然,如果在这个高度以下往下扔,怎么都不会碎,当然超过这个高度肯定就一定摔碎了。
现在已知这个恰巧摔碎高度范围在一层楼到 100 层楼之间。
如何用最少的试验次数,用这两个玻璃球测试出摔碎的楼高
假设最少次数是 x 次 那么第一个我们从哪里扔呢 ?从 x 因为如果碎了 另一个球从 1 到 x 正好就是 x 如果没碎这时候我们第一个球第二次只剩 x-1 次 所以我们从 x+x-1 层扔 碎了从 x+1 到 x + x-2 遍历 后面逻辑一样 减 1 去扔第一个球 没碎下次再减 1 碎了从上一次的没碎的上一层遍历就好了

所以可以一共层数等于 x + (x-1) + (x-2) + ... + 1 = 100

下面我们来解这个这个方程:

(x+1)*x/2 = 100

最终 x 向上取整,得到 x=14

因此,最优解在最坏情况的尝试次数是 14 次,第一次扔鸡蛋的楼层也是 14 层。

最后,让我们把第一个鸡蛋没碎的情况下,所尝试的楼层数完整列举出来:

14,27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

function solution(n) {
  const dp = Array.from({ length: 2 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    dp[0][i] = i;
    dp[1][i] = n;
    for (let j = 1; j <= i; j++) {
      dp[1][i] = Math.min(dp[1][i], Math.max(dp[0][j - 1], dp[1][i - j]) + 1);
    }
  }
  return dp[1][n - 1];
}
当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »