100 层楼,两个玻璃球,求最少多少次测出能摔碎玻璃球的楼层
给你两个一摸一样的球,这两个球如果从一定的高度掉到地上有可能就会摔碎,当然,如果在这个高度以下往下扔,怎么都不会碎,当然超过这个高度肯定就一定摔碎了。
现在已知这个恰巧摔碎高度范围在一层楼到 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];
}