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

本文主要是介绍摔杯算法(要求用最少的测试次数找出恰巧会使杯子破碎的楼层。),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目: 一种杯子,若在第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

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

这篇关于摔杯算法(要求用最少的测试次数找出恰巧会使杯子破碎的楼层。)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/387545

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

性能测试介绍

性能测试是一种测试方法,旨在评估系统、应用程序或组件在现实场景中的性能表现和可靠性。它通常用于衡量系统在不同负载条件下的响应时间、吞吐量、资源利用率、稳定性和可扩展性等关键指标。 为什么要进行性能测试 通过性能测试,可以确定系统是否能够满足预期的性能要求,找出性能瓶颈和潜在的问题,并进行优化和调整。 发现性能瓶颈:性能测试可以帮助发现系统的性能瓶颈,即系统在高负载或高并发情况下可能出现的问题

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

【测试】输入正确用户名和密码,点击登录没有响应的可能性原因

目录 一、前端问题 1. 界面交互问题 2. 输入数据校验问题 二、网络问题 1. 网络连接中断 2. 代理设置问题 三、后端问题 1. 服务器故障 2. 数据库问题 3. 权限问题: 四、其他问题 1. 缓存问题 2. 第三方服务问题 3. 配置问题 一、前端问题 1. 界面交互问题 登录按钮的点击事件未正确绑定,导致点击后无法触发登录操作。 页面可能存在

业务中14个需要进行A/B测试的时刻[信息图]

在本指南中,我们将全面了解有关 A/B测试 的所有内容。 我们将介绍不同类型的A/B测试,如何有效地规划和启动测试,如何评估测试是否成功,您应该关注哪些指标,多年来我们发现的常见错误等等。 什么是A/B测试? A/B测试(有时称为“分割测试”)是一种实验类型,其中您创建两种或多种内容变体——如登录页面、电子邮件或广告——并将它们显示给不同的受众群体,以查看哪一种效果最好。 本质上,A/B测