程序员2007年3月刊上的一道算法题

我自己看了你的思路 是你推理就有问题。

to:上上楼:
嗯,题目没有给出"最优策略"的定义,如果从数学期望来考虑,也是一种思路.不过这样的话解决方法就比较简单了.

不过我的算法不是从数学期望角度来考虑的.
根据原文的描述,我考虑的"最优策略"是这样的:
    给出一种策略,使得在最坏的情况下,测试的次数最少

to:上楼
     呵呵,看法不一致.

还没回答我啊。。

其实还是个折半查找吧，只不过需要根据有几个棋子来确定可以折几次，剩最后一个棋子时，开始遍历。

我那个公式的确有错误
应该是100%n+n-2

不过得到的答案是从10到18，不够稳定（考虑到平均是14）

原因是每个区间的大小都一样，我把它们的步长设为1

这样
我第一次从14楼丢（步长为13），第2次从27楼丢（步长为12）。。。。。
答案就稳定在14了

如果是14层碎了,那么只能用剩下的一颗棋子从第一层逐次往上测,最多共测14次

哦!反正就是玩到那个棋子碎了为止是吧?

确认一下,这儿是 100%n+n-2,还是100/n+n-2?
|100%n|+n-1取最小值的n与100%n+n-2取最小值时的n有不同么?

另外,当n=9(9层楼的时候),按你的公式应该是几次?

刚好在手边就有这一期.
文章中好像并没有写这是一个算法,仅仅是一种推理.
就是其中的14!=105>100 这个不太明白是什么意思.
哪位大侠解释一下?

我看了一段时间， 发现这个问题可以这样说： 因为对于每一层楼来说，是临界点的几率都一样，所以，开始选择的k，应该尽量保证k+(k-1)+…+1=n，这样不管临界点在哪里，最多次数就是k。
而对于n=100时， k约等于14。和楼主的答案不谋而合，但是楼主答案的后半部的意图我不是很了解。