彩票平台:首页 > 学习之路 > ACM||算法ACM||算法

113彩票官网:厉害了我的杯

卞振伟2019-01-24【ACM||算法】人已围观

简介有一种玻璃杯质量确定但未知,需要检测。
有一栋100层的大楼,该种玻璃杯从某一层楼扔下,刚好会碎。
现给你两个杯子,问怎样检测出这个杯子的质量,即找到在哪一层楼刚好会碎?

注册登录

  • 2 个杯子的脆弱程度是一样的

  • 如果杯子从 N 楼扔下来没有碎,那么它从小于 N 楼扔下来,也不会碎

  • 如果杯子从 N 楼扔下来碎了,那么它从大于 N 楼扔下来,也一定会碎

  • 一个扔出去但没有碎的杯子,可以继续被用于试验

  • 碎了的杯子将无法再继续试验。

举个栗子:

如果从 x 楼扔下,没碎,在 x+1 楼扔下,碎掉了,即证明找到了 x+1 是刚好碎掉的楼层。

那么问题来了:怎样才能最快速的找到这个楼层?

问题的解决有很多种方案,注意点就是找到的最佳方案是能在各种情况下都能快速地找到目标楼层

总结一下:我们的终极目的是要找出连续的两层楼 x 与 x + 1 ,在楼层 x 杯子没有摔碎,在楼层 x + 1 杯子碎了,问题的关键之处在于,测试之前,并不知道杯子会在哪一层摔碎,需要找到的是一种测试方案,这种测试方案,无论杯子会在哪层被摔碎,都至多只需要 m 次测试,在所有这些测试方案中, m 的值最小。
 


------------------------------一条思考的分界线------------------------------


题目:成功率跟运气有关运气,尝试次数可能情况1、2、3······100

目的:最差情况尝试次数最小

思想:均分次数(类似五笔把汉字均分到26个字母)

方法:划分最小区间

解:设最小区间大小为X

     能判定的最大范围 res = X + (X-1) + (X-2) + ··· + 2

     由题意得:res >= 100

     解的 X = 14

最差情况14次  期望值9次多  平均次数10次

Tags:编程   生活   程序员

很赞哦! ()

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:71篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00