阅读上一个主题 :: 阅读下一个主题 |
作者 |
正文 |
三文鱼 (只看此人)
|
时间: 2021-11-17 01:04
|
|
|
有一栋100层高的大楼,给你两个完全相同的玻璃球,假设从某一层开始丢下玻璃球会摔碎,怎么利用手中的两个玻璃球,用什么最优策略(最坏情况下最少次数)知道这个临界的层是第几层
_________________ 哦,西风,你吹舞我如波如叶如云吧!
我是太浮,太傲,太和你一样的不羁!
|
|
|
|
|
楼主 |
电梯直达
|
|
不怕没柴烧 (只看此人)
|
时间: 2021-11-17 01:09
|
|
|
|
|
|
沙发 |
返回顶端
|
|
三文鱼 (只看此人)
|
时间: 2021-11-17 01:09
|
|
|
用2个玻璃球找到从一100层的大楼的某一层落下刚好会摔碎,如何制定最优策略?
有一栋100层高的大楼,给你两个完全相同的玻璃球,假设从某一层开始丢下玻璃球会摔碎,怎么利用手中的两个玻璃球,用什么最优策略(最坏情况下最少次数)知道这个临界的层是第几层
这个题目首先是关于“最优”的定义。
考虑best-worse case最坏情况下最优。也就是说假如你的算法是从第一楼逐楼往上试,那么相应最坏的情况是在100楼破,相应的是一百次。
这种情况下最优策略也就是从14楼开始递减间隔的办法,worst case 需要14次。
记n层s球的问题为Q(n,s),对应的最坏情况最优解为ba(n,s);
一些简单的结果:
(0) ba(m,2)>=ba(n,2) 如果m>n,trivial.
(1) ba(n,1)=n
当你只剩下一个球,为了能够检验出临界点,你只能逐层检验,最坏情况下所需的检验次数为n;
(2)ba(1,2)=1
(3)iterative: 假设你从k层扔球,有两种情形:
球破。那么临界层必然在1层到k-1层之间,剩下一球,由(1)得出,最坏情况最优所需的步数为: 1 + ba(k-1,1)=k;
球不破。问题变成n-k层两球的问题Q(n-k,2), 所以最坏情况最优所需步数是:1+ba(n-k,2);
综合1,2,最坏情况所需步数: 当k=1+ba(n-k,2)的时候,ba(n,2)=ba(n-k,2)+1结合(2),(3),由(2)迭代得知:当n = 1+2+3+...+kba(n,2)=k当k=13时, n=91;ba(100,2)=max(9,1+ba(91,2))=14所以100层,最坏情况最优策略的步数是14
_________________ 哦,西风,你吹舞我如波如叶如云吧!
我是太浮,太傲,太和你一样的不羁!
|
|
|
板凳 |
返回顶端
|
|
三文鱼 (只看此人)
|
时间: 2021-11-17 01:10
|
|
|
是啊,帖了半天,明天再说吧。晚安
_________________ 哦,西风,你吹舞我如波如叶如云吧!
我是太浮,太傲,太和你一样的不羁!
|
|
|
地板 |
返回顶端
|
|
bbsang2 (只看此人)
|
时间: 2021-11-17 05:59
|
|
|
用这个来指导炒股怎么样
|
|
|
5 楼 |
返回顶端
|
|
长枪刺破云霄 (只看此人)
|
时间: 2021-11-17 10:02
|
|
|
不用那么复杂,common sense,玻璃球从一楼丢下去就碎了。
|
|
|
6 楼 |
返回顶端
|
|
pws07 (只看此人)
|
时间: 2021-11-17 10:41
|
|
|
太复杂了。 不想想太多
|
|
|
7 楼 |
返回顶端
|
|
明娘娘 (只看此人)
|
时间: 2021-11-17 11:44
|
|
|
买一个modem+wifi router合在一起的会不会看起来清爽一些呢?
|
|
|
8 楼 |
返回顶端
|
|
bbsang2 (只看此人)
|
|
9 楼 |
返回顶端
|
|
smschat (只看此人)
|
时间: 2021-11-17 12:53
|
|
|
题目都没看懂
|
|
|
10 楼 |
返回顶端
|
|
|
|
论坛首页
-> 日月当空 |
所有的时间均为 美国太平洋时间
|
第1页,共4页 |
分页: 1, 2, 3, 4 下一页 |
|
注: 以上论坛所有发言仅代表发帖者个人观点, 并不代表本站观点或立场, 加西网对此不负任何责任。 投资理财及买房卖房版面的帖子不构成投资建议。投资有风险,责任请自负对二手买卖中的虚假信息,买卖中的纠纷等均与本站无关。 |
|
您不能在本论坛发表新主题 您不能在本论坛回复主题 您不能在本论坛编辑自己的文章 您不能在本论坛删除自己的文章 您不能在本论坛发表投票 您不能在这个论坛添加附件 您可以在这个论坛下载文件
论坛转跳:
|
|
三文鱼, 不怕没柴烧, 三文鱼, 三文鱼, bbsang2, 长枪刺破云霄, pws07, 明娘娘, bbsang2, smschat
|
|
|