免费申请个人网站申请,河北省中级经济师考试,网络运营商包括哪些,定制开发电商网站建设哪家好大家好#xff0c;我是牛牛#xff0c;经过了忙碌的一周#xff0c;终于盼来了周五。今天给大家分享一道有趣有料的算法题#xff0c;希望能让大家开启周末的好心情。01故事起源有1000瓶药水#xff0c;其中有一瓶是毒药#xff0c;只要喝上一滴#xff0c;一天之后就必… 大家好我是牛牛经过了忙碌的一周终于盼来了周五。今天给大家分享一道有趣有料的算法题希望能让大家开启周末的好心情。01故事起源有1000瓶药水其中有一瓶是毒药只要喝上一滴一天之后就必死无疑。现在提供一批兔子来试毒那我们怎么花最少的兔子、最少的时间找出这瓶毒药呢02条件分析喝一滴就死掉换句话说那一瓶药水是可以给多只兔子喝的。要花最少的兔子又要花最少的时间看起来像是时间与空间的决策不如我们先来简化问题1.只追求时间最快速度找出药水。2.只追求空间节约兔子时间可以慢慢来。这样从简单角度辅助思考一下也能为我们深入思考打下基础。03花式试毒追求时间简单来说就是堆兔子。直接拿1000只兔子试毒一只兔子负责一瓶药水。结果自然是耗用1000只兔子1天出结果。这样的优势比较明显就是快缺点也明显使用的兔子太多占资源不环保。追求空间如果我们出于环保考虑节约兔子那么可以考虑用2分。第一轮就分为500瓶毒药为一组先放一只兔子每瓶药水喝一滴这样可以排除500瓶。如果活着就继续用这只兔子如果死了就补充兔子。我们按最坏情况来算每次都要消耗掉一只兔子。下一轮250瓶这样循环迭代1000-500-250-125-63-32-16-8-4-2-110个箭头就是10次也就是用了10天。这样我们只用了10只兔子很节约不过就是等得太心慌。中庸之道把前两种方式综合一下我们可以不用1000只兔子也可以不用等足足10天。把2分变成多分。比如9只兔子的话每次能分10份每轮补充兔子到9只这样试完1000瓶药水只需要3天1000-100-10-1。2只兔子的话就是3份1000-333-111-37-(12,12,13)-(4,4,5)-(2,2,1) - 1规律也很明显天数为d分a份则兔子是a-1只药水N瓶那么d等于以a为底N的对数logaN。比如当耗用2只兔子时a为3算出来正好是7天和我们刚才的推算是一样的。计算机思维还有没有更好的办法呢时间短效率高。当然有因为一次可以喝多瓶药水那么我们可以用10只兔子模拟出1024种情况。给药水编号从1-1000兔子也编上号1-10号1000瓶药水编号都转换为二进制编号1就是000 000 00011000就是111 110 1000。这种情况下第几位为1就让对应的兔子喝一滴药水。由于编号都是独一无二的所以最后根据死掉的兔子反过来组合一下就是药水的编号。如此一来10只兔子只花1天就能试毒成功。无论空间还是时间都是最快的。04兔兔复盘如果你是使用1000只兔子试毒那么说明你对时间很敏感如果是二分法那你一定是个节约成本的大师如果使用多分法说明你懂得在空间和时间上取一个均衡深谙中庸之道如果你能很快想到二进制模拟那么你一定是对计算机01存储非常熟悉是选择时间或空间或寻求平衡亦或是有办法另辟蹊径两者兼备相信随着思维的循序渐进你会有所感悟。今天分享的这道题不光有趣还是大厂热门面试题看起来似乎很简单但其实是有巧思在其中的它考察了你的思维方式和逻辑能力希望大家在阅读过程中有所收获推荐阅读专辑|Linux文章汇总专辑|程序人生专辑|C语言我的知识小密圈关注公众号后台回复「1024」获取学习资料网盘链接。欢迎点赞关注转发在看您的每一次鼓励我都将铭记于心~嵌入式Linux微信扫描二维码关注我的公众号
