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

题目: 一种杯子，若在第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 = 0
        if(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 105
                    print(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 = 0
    const end = n + step - 1
    if (end) {
        arr.push([n, end])
        if (n >= 100) {
            return
        }
        const start = end
        const end2 = start + step - 1
        if (start > end2) return
        return 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

参考地址: 100层楼两个杯子找杯子碎的临界点-CSDN博客