廊坊网站建设总部在哪里,网站建设基础服务,小程序定制公司,微信营销工具题目: 一种杯子#xff0c;若在第N层被摔破#xff0c;则在任何比N高的楼层均会破#xff1b;若在第M层不破#xff0c;则在任何比M低的楼层均不会破。给你两个这样的杯子#xff0c;让你在100层高的楼层中测试#xff0c;要求用最少的测试次数找出恰巧会使杯子破碎的楼层…题目: 一种杯子若在第N层被摔破则在任何比N高的楼层均会破若在第M层不破则在任何比M低的楼层均不会破。给你两个这样的杯子让你在100层高的楼层中测试要求用最少的测试次数找出恰巧会使杯子破碎的楼层。
解题思路:
1个杯子尝试的次数假设为n, 则可能尝试有1次, 2次, 3次,...,n次, 但,要求最少的测试次数(楼层不可能重复), 所以尝试总数还应该是这次大于等于100, 上次计算得出的尝试总数小于100
即123...n 100
简化公式: 1/2n(n1) 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 参考地址: 100层楼两个杯子找杯子碎的临界点-CSDN博客
