摔杯算法(要求用最少的测试次数找出恰巧会使杯子破碎的楼层。)

题目: 一种杯子，若在第N层被摔破，则在任何比N高的楼层均会破；若在第M层不破，则在任何比M低的楼层均不会破。给你两个这样的杯子，让你在100层高的楼层中测试，要求用最少的测试次数找出恰巧会使杯子破碎的楼层。

解题思路:

1个杯子尝试的次数假设为n, 则可能尝试有1次, 2次, 3次,...,n次, 但,要求最少的测试次数(楼层不可能重复), 所以尝试总数还应该是这次大于等于100, 上次计算得出的尝试总数小于100

即1+2+3+...+n >= 100

简化公式: 1/2n(n+1) >= 100

求得n的最小整数为14

function bei({n}) {let currentNum = 0if(n == 1) return {n:1}if(n > 1 && n <= 100) {const obj = bei({n: n - 1})if(typeof obj === 'object') {const pre = obj.n; // 上次尝试总数currentNum = n + pre // 此次尝试总数if(currentNum >= 100 && pre < 100) {console.log(n, pre, currentNum)// 14 91 105print(n)return}return {n:currentNum, parts: n}}}
}function print(minNum) {console.log(minNum) // 14
}bei({n:100})

优化: 除了最小值, 其他可能的区间:

var arr = []
function bei2({ n, step }) {let currentNum = 0const end = n + step - 1if (end) {arr.push([n, end])if (n >= 100) {return}const start = endconst end2 = start + step - 1if (start > end2) returnreturn end + 1 >= 100 ? arr.push([100]) : bei2({ n: end + 1, step: step - 1 })}// 计算第一个最小测试区间, 后面的区间数字间隔逐渐变小while (n >= 1 && n <= 100) {currentNum += n // 此次尝试总数if (currentNum >= 100) {arr.push([1, n])print(n)return bei2({ n: n + 1, step: n - 1 })}n++}
}
bei2({ n: 1 })
console.log(arr)// 一种杯子,若在第N层被摔破,则在任何比N高的楼层均会破,若在第M层不破,则在任何比M低的楼层均会破,给你两个这样的杯子,让你在100层高的楼层中测试,要求用最少的测试次数找出恰巧会使杯子破碎的楼层。
// 第一个杯子可能的投掷楼层分别为:14,27,39,50,60,69,77,84,90,95,99,100
// 14 + 13 => 27
// 27 + 12 = 39
// 39 + 11 => 50
// 50 + 10 => 60
// 60 + 9 => 69
// 69 + 8 => 77
// 77 + 7 => 84
// 84 + 6 => 90
// 90 + 5 => 95
// 95 + 4 => 99
// 最大100

当我们用14时，我们可以得出范围为1~14, 15~27, 28~39... 96~99, 100