有一栋100层高的大楼，给你两个完全相同的玻璃球，假设从某一层开始丢下玻璃球会摔碎，怎么利用手中的两个玻璃球，用什么最优策略（最少次数）知道这个临界的层是第几层
设F(n,k)为用k个玻璃球来测试n层大厦的临界层的最少次数，状态转移方程如下：
F(n,k)=min{max{F(r,k-1), F(n-r,k)}+1, 1<=r<=n}
边界条件:F(n,1)=n-1, F(1,k)=F(0,k)=0
状态转移方程可以这样来考虑，假设在n层楼中的第r层抛一次(对应方程中的"+1")，会有两种情况发生：
(1)玻璃球碎，说明在第1到第r层楼中必有一层为临界层，问题转化为一个子问题：求F(r,k-1)
(2)玻璃球不碎，说明临界层在第r+1层到第n层这n-r层楼中，问题转化为子问题:求F(n-r,k)
因为考虑的是最坏情况下抛球策略的所需测试次数的最小值，所以取这两种情况中的较大值，并遍历每一个可能的r，取其最小值即得到F(n,k)。
问题描述： 有一栋100层高的大楼，给你两个完全相同的玻璃球，假设从某一层开始丢下玻璃球会摔碎，怎么利用手中的两个...
2018-03-16 夏国君 2018-03-16:21:30 · 字数 241 · 阅读 12 · 日记本 20...
一．问题描述 Windows７开机提示如下错误：2018-03-16 230326.jpg 以上各个选项进入后都提...
PPT营销力双周D24(2018-03-16)会议安排： 时间：2018-03-16 6-7点 主持人 : 于佳 ...
有这样一个问题：如果你把玻璃球扔到地上，玻璃球会摔碎，把铁球扔在地上，铁球落地后不会有什么变化，把乒乓球扔到地上，...
心情的玻璃球 文(萤火淡然) 昨晚地震 摇落一夜的玻璃球 颗颗玻璃球 化作颗颗泪 捡拾
滚落的玻璃球 你还记得吗？ 童年时候的玻璃球
心情的玻璃球 文(萤火淡然) 昨夜地震 摇落了一地的玻璃球 颗颗玻璃球 滚成颗颗泪 捡拾
Author: Mikoy Date: 2018-03-16 1. Preparation： Jetpack 3....
断章曲艺 你蹲在地上弹玻璃球 弹玻璃球的人拿玻璃球弹你 你揍了那个小孩 那个小孩的父亲也揍了你
本文标题：2018-03-16 2个玻璃球问题
本文链接：https://www.haomeiwen.com/subject/mtkrqftx.html
网友评论