抛玻璃算法-ubuntuer-ChinaUnix博客

人生如逆旅，我亦是行人！江湖人称wsjjeremy.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

ubuntuer

博客访问： 4732043
博文数量： 930
博客积分： 12070
博客等级：上将
技术积分： 11448
用户组：普通用户
注册时间： 2008-08-15 16:57

文章分类

全部博文（930）

html5（0）
python（1）
google_gnu fans（8）
高品位（2）
perl（4）
mobile_dev（2）
openssl（1）
libcurl（2）
windows内核安全（5）
自己的C_LIB（5）
高性能MySQL学习（94）
多线程（4）
ldd学习笔记（3）
netfilter（3）
笔试题（5）
师徒之言传身教（1）
转载（15）
work（146）
introduction to （9）
debug（3）

intern（3）
mobile ip（0）
毕业设计（2）
linux防火墙（10）
c++（16）
database（13）
CentOS（11）
data structure（5）
kernel（50）
DIY（4）
酷软（19）
iptables（9）
linux c（105）

string（19）
APUE学习笔记（7）
facetea（13）
shell（68）
tcp_ip（23）
apache（3）
linux（258）

正则表达式（5）
未分配的博文（1）

文章存档

2011年（60）

2010年（220）

2009年（371）

2008年（279）

我的朋友

相关博文

抛玻璃算法

分类： LINUX

2009-08-30 20:07:51

题1】有一幢100层高的大厦，给你两个完全相同的玻璃围棋子。假设从某一层开始，丢下玻璃棋子就会摔碎。那么怎么利用手中的两颗棋子，用一种什么样的最优策略，知道这个临界的层高呢？

100-99-97-94-90-85-79-72-64-55-45-34-22-9由大到小相隔一次加1

反过来的话就是

先9-22.....这样就保证只要差不多都是14次可以搞定!!!!!

阅读(1849) | 评论(4) | 转发(0) |

上一篇：gperf完美hash

下一篇：变位词问题

给主人留下些什么吧！~~

ubuntuer2009-09-04 18:14:52

我的思路是这样的,这题就是为了保证不管临界点在那里都能保证抛珠的次数大致相等. 假设第一次是上M层,如果碎了当然好说,没碎的话,第二次就只能抛M-1次了,为了保证1,2大致相同 M+(M-1)+(M-2)+....+1 = 100 这样M大概为14,其实13，14没必要太计较^_^

回复 | 举报

chinaunix网友2009-09-04 13:08:06

不知道楼主的结果怎么出来的, 这个结果也不用爬14次，最多在22层碎掉只要13次就搞定了。

回复 | 举报

chinaunix网友2009-09-03 10:28:31

楼上的只用了一颗棋子，还有一颗没有用上。每次爬两层，每层扔一颗，没碎就去捡回来。1-2；3-4；5-6；... ... 直到发现有一颗碎了。这个不能用二分法，碎了就没了，从上往下爬楼要累死人。那位有兴趣算一下，先爬到2楼，扔一颗，碎了下一层扔，没碎酒上一层才扔。抛完去捡回来，上4层如法炮制。看看那个跑得楼层比较少点。

回复 | 举报

chinaunix网友2009-09-02 15:54:27

从最下层开始抛，，，只要不碎掉，就去捡回来继续抛，直到碎掉；

回复 | 举报

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6