引用：
“有一个100层高的大厦，你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋
子就会碎，用你手中的这两个玻璃围棋子，找出一个最优的策略，来得知那个临界层面。
”
偶用二分法只能得出个范围，哪位高手能得出具体是哪一层啊～～～
isjfk 回复于：2006-12-11 13:58:11
他没说你不能到楼底下把棋子拣上来再扔...
ssffzz1 回复于：2006-12-11 13:59:36
这样吗，先从第一层扔，扔到那层碎，那层就是了。
invalid 回复于：2006-12-11 14:12:39
看看这位的分析：
http://blog.csdn.net/jiaomeng/archive/2006/12/08/1435226.aspx
cugb_cat 回复于：2006-12-11 15:13:52
引用：原帖由 ssffzz1 于 2006-12-11 13:59 发表
这样吗，先从第一层扔，扔到那层碎，那层就是了。
呵呵，或许可以这样钻空子。。。。:D:D:D
koolcoy 回复于：2006-12-11 15:20:00
要看到底什么为优了：时间最少？用玻璃球最少？
cugb_cat 回复于：2006-12-11 15:20:31
引用：原帖由 invalid 于 2006-12-11 14:12 发表
看看这位的分析：
http://blog.csdn.net/jiaomeng/archive/2006/12/08/1435226.aspx
这个最强～～～
softsongs 回复于：2006-12-11 15:47:06
感觉确实有一个最优解，
1。首先如果只有一个玻璃球的情况，最多需要50次，
一个球的情况，可以两层两层试，如果2层不碎，就试第4层，第4层不碎就是第6层，依此类推。如果到第n层碎了，那么临界层就是n-1层，因为n-2层的结果必定是不碎。
2。考虑有两个球的情况，其实只要看成我们有两次机会就可以了，相当于做两遍相同的题目。
这次我们挑选的楼层就不是每隔两层了，而是每隔4层，
依次为，4，8，12，16 .... 4n, (n>=1)
公式为 a(1) = 4, a(2) = 8 ... a(n) = 4n;
如果在第i层碎了，那么说明到a(i－1) 都不会碎，显然，我们只要考虑a(i-1) 到a(i)之间的楼层就可以了。
又，a(i) - a(i-1) = 4, 由递归公式得。
因此，第二个球应该在楼层a(i-1) + 2 处扔下，如果碎了，说明临界层为a(i-1) + 1, 否则临界层为a(i) -1;
证明完毕；
cugb_cat 回复于：2006-12-11 16:03:51
引用：原帖由 softsongs 于 2006-12-11 15:47 发表
1。首先如果只有一个玻璃球的情况，最多需要50次，
一个球的情况，可以两层两层试，如果2层不碎，就试第4层，第4层不碎就是第6层，依此类推。如果到第n层碎了，那么临界层就是n-1层，因为n-2层的结果必定是不碎。
这一条我感觉怎么不太对啊～～～
如果是在第4层碎了的话，那你能确定是第3层为临界面还是第4层为临界面吗？
ArXoR 回复于：2006-12-11 16:53:52
题目的意思应该是
找出一个固定的方案A, 使得对于目标t为任意[1,100]里的数的时候, 找出t要扔的最多的次数 最小
因为t不同的时候, 方案A要扔的次数不一定一样, 我们就是要使得这个最多的次数最小
动态规划就好了
F(l,r,k)为 确定目标t是否在[l,r]中且手上有k个棋子的最少扔子次数, 有状态转移方程:
/ (r-l+1) (k = 1)
F(l,r,k) = | 1 (l = r)
| 0 (l > r)
\ 1+min{max{F(l,mid-1,k-1),F(mid+1,r,k)}} (l<=mid<=r)
所求就是F(1,100,2).
Please correct me if I'm wrong.
jronald 回复于：2006-12-11 17:50:58
4,7,10... 隔两层扔？
emacsnw 回复于：2006-12-11 18:48:04
引用：原帖由 ArXoR 于 2006-12-11 00:53 发表
题目的意思应该是
找出一个固定的方案A, 使得对于目标t为任意[1,100]里的数的时候, 找出t要扔的最多的次数 最小
因为t不同的时候, 方案A要扔的次数不一定一样, 我们就是要使得这个最多的次数最小
动态规划就好 ...
问题就在于如果知道了区间[l, r]，加入还有多于1个玻璃球的话，是否应该扔一个在mid处。比如原题只有两个玻璃球的情况，显然不应该扔在50，这样最坏要50次（包括了第一次在50扔碎的那次）。而如果我在33处先扔，如果碎了，我只要再检测1－32层，共33次即可，如果第一次在33没有破碎，那么如果再二分，也最坏也只要再33次。显然比你直接50处二分要优。
我认为上面的那个链接给出的方法（均匀分10个区间）也是不对的，因为随着你从下往上实验这些区间，实验次数也在增加，只管的说，应该让下面的区间包含的层数多余顶上的区间，这样使得总测试次数差不多。
ArXoR 回复于：2006-12-11 18:56:15
我的方程后面有(l<=mid<=r), mid是枚举的
引用：原帖由 emacsnw 于 12/11/06 18:48 发表
问题就在于如果知道了区间[l, r]，加入还有多于1个玻璃球的话，是否应该扔一个在mid处。比如原题只有两个玻璃球的情况，显然不应该扔在50，这样最坏要50次（包括了第一次在50扔碎的那次）。而如果我在33处先扔 ...
ArXoR 回复于：2006-12-11 18:58:47
可以参考一下这个思路很类似的题目
http://acm.pku.edu.cn/JudgeOnline/problem?id=2904
emacsnw 回复于：2006-12-11 19:08:52
引用：原帖由 ArXoR 于 2006-12-11 02:56 发表
我的方程后面有(l<=mid<=r), mid是枚举的
这样应该是对的。
想了一下，如果是两个玻璃球，最少次数m确定楼高为N的哪一层开始能使这个玻璃球摔碎这个问题，等价于求最小的m，使得 1+2+...+m >= N 。
假设N正好等于1+2+...+m，那么我觉得最有的策略就是第一个玻璃球扔在第m层，如果碎了，显然需要剩下的m-1层从底往上一一尝试，最坏情况就是m；假设m处没有碎，问题等价于楼高N'=1+2+...+(m-1)的地方同样的问题需要的次数m'+1 （1就是第一次在m层的尝试），根据我们的递归，容易得到N'对应需要的次数正好是m-1次，因此总次数也是m。
我们的二分应该倾向于不管失败还是成功，两种情况的总检测次数相等。因此这应该是最优的算法。
当然，当N不能表示成1+2+...+m使，我们只能找最小的m作为需要测试的次数。
至于100层楼，显然m=14，我们的第一次扔球应该分别在第14, 如果没碎继续在14+13=27，再没有碎则扔在第27＋12＝39层，以此类推。最坏需要14次判断。貌似比链接里面的结论18要优。
不知道有没有人能实现你的DP算法验证一下？
ArXoR 回复于：2006-12-11 19:39:06
写了程序算了一下，是14
#include "stdio.h"
#include "string.h"
const int INF = 200000000;
const int maxN = 110;
int f[maxN][maxN][maxN];
int n, k;
int
find(int l, int r, int k)
{
if (l > r)
{
return 0;
}
if (k == 1)
{
return r - l + 1;
}
if (l == r)
{
return 1;
}
if (f[l][r][k] != -1)
{
return f[l][r][k];
}
int mid;
int left, right, t;
f[l][r][k] = INF;
for (mid = l; mid <= r; ++mid)
{
left = find(l, mid - 1, k - 1);
right = find(mid + 1, r, k);
t = left > right ? left : right;
f[l][r][k] <?= t;
}
return ++f[l][r][k];
}
int
main()
{
memset(f, -1, sizeof(f));
while (scanf("%d %d", &n, &k) == 2)
{
printf("%d\n", find(1, n, k));
}
return 0;
}
ArXoR 回复于：2006-12-11 19:46:27
Your idea sounds good.
Maybe you can prove it formally.
引用：原帖由 emacsnw 于 12/11/06 19:08 发表
这样应该是对的。
想了一下，如果是两个玻璃球，最少次数m确定楼高为N的哪一层开始能使这个玻璃球摔碎这个问题，等价于求最小的m，使得 1+2+...+m >= N 。
假设N正好等于1+2+...+m，那么我觉得最有的策 ...
DraculaW 回复于：2006-12-11 20:16:03
黃金分割法....
一梦如是 回复于：2006-12-11 21:24:54
考虑不周。编辑掉
[ 本帖最后由 一梦如是 于 2006-12-11 21:33 编辑 ]
assiss 回复于：2006-12-11 21:36:49
我觉得ArXoR 和 emacsnw 的算法是对的。
r2007 回复于：2006-12-11 23:13:22
笨办法推演了一下，平均测试次数为10.3次
如果一直不碎，提升层数如下，第一次为14层，不碎则在爬高13层，以此类推
14 13 12 11 10 9 8 7 5 4 3 2 1
heaso 回复于：2006-12-12 08:22:08
100是10的平方.
第一个10层一扔. 第2个1层一扔.
最多也扔不过20次.
jronald 回复于：2006-12-12 08:42:43
引用：原帖由 heaso 于 2006-12-12 08:22 发表
100是10的平方.
第一个10层一扔. 第2个1层一扔.
最多也扔不过20次.
如果第一次扔就碎了，你怎么用另一颗确定是哪一层？
不用马甲 回复于：2006-12-12 08:48:34
玻璃棋子，一般到不了四五层就碎了:lol:
[ 本帖最后由 不用马甲 于 2006-12-12 08:49 编辑 ]
finddream 回复于：2006-12-12 09:00:33
看了那个老哥分析的，相当不错的解释，受益非浅！
r2007 回复于：2006-12-12 09:58:33
引用：原帖由 r2007 于 2006-12-11 23:13 发表
笨办法推演了一下，平均测试次数为10.3次
如果一直不碎，提升层数如下，第一次为14层，不碎则在爬高13层，以此类推
14 13 12 11 10 9 8 7 5 4 3 2 1
已经找到了如何证明这是最优解的方法了，这段时间紧，过后总结一下丢上来。
基本概念：
定义什么最优解: 100层中任意一层都可能是临界层，c(n)表示临界层为n层时该算法需要的测试次数，那么(c(1)+c(2)+...+c(100))/100为平均测试次数，其值最小的算法既为最优算法。
定理一：
若：a(m,n)表示有m个玻璃球，n层楼时的最优算法的测试平均值
则：a(m,n)<<a(m-1,n)
a(m,n)<<a(m,n+1)
必然存在k使 a(m,n)=(a(m-1,k)*k+a(m,n-k)*(n-k))/n +1
bruceteen 回复于：2006-12-12 10:03:38
既然还没看到正确答案，那我就贴一下：
http://blog.vckbase.com/Panic/archive/2006/12/07/23399.html
cmoscmos 回复于：2006-12-12 10:15:43
引用：原帖由 cugb_cat 于 2006-12-11 16:03 发表
这一条我感觉怎么不太对啊～～～
如果是在第4层碎了的话，那你能确定是第3层为临界面还是第4层为临界面吗？
个人意见:仅供参考
我觉得..因为碎与不碎只有两个结果.
按你说的.第4层碎.第二层不碎.的确是不能确定第三层是不是会碎.
重要的是临界点是碎与不碎间.是两个点.可以讲碎的那层是临界.也可以讲不碎的那层是临界.
这样子的话
如果第3层没碎.那临界在第3层~第4层间.就如我前面所讲.第3第4层都能讲是临界
如果第3层碎了.那临界在第2层~第3层间.就如我前面所讲.第2第3层都能讲是临界
嘿嘿.我的观点就是临界在碎与不碎间.那两层都能认为是临界
自己想法.大家不要砸我.
cugb_cat 回复于：2006-12-12 11:49:03
引用：原帖由 jronald 于 2006-12-12 08:42 发表
如果第一次扔就碎了，你怎么用另一颗确定是哪一层？
如果第一次扔就碎了，用第二颗棋子从第二层开始扔，一层一层的向上走，就的出来了～～
cugb_cat 回复于：2006-12-12 11:50:10
引用：原帖由 heaso 于 2006-12-12 08:22 发表
100是10的平方.
第一个10层一扔. 第2个1层一扔.
最多也扔不过20次.
再优化一下，最多9＋7＝16次。
[ 本帖最后由 cugb_cat 于 2006-12-12 13:24 编辑 ]
jronald 回复于：2006-12-12 12:12:27
引用：原帖由 cugb_cat 于 2006-12-12 11:49 发表
如果第一次扔就碎了，用第二颗棋子从第二层开始扔，一层一层的向上走，就的出来了～～
恩，多谢提醒
lookee 回复于：2006-12-12 14:48:57
14应该是正解
mlmyf 回复于：2006-12-12 16:21:59
为什么不考虑从100楼开始丢呢，首先丢到98楼，如果粹了再丢第二个到99楼，如果粹了就是答案就是1层。如果100到98没碎，那么至少可以确定2层不会碎，从100把第二颗丢到98-3=95，如果碎了下到98丢到94楼。如果这样丢到1楼还没有得到结果，那么要根据当前得到的结果回溯到相应位置再继续。其中要设几个用于计数和回溯的变量，按这个策略这样推下去，其基本思想是动态规划法，回朔法，和剪枝的综合应用可得最优策略。（注：个人认为最优策略并没有明确指明所用的次数最少，所以应考虑人走的楼层最少为最优策略。想想搜索中都是需要总的搜索时间最小而不是搜索次数最小，大家应想到会到楼下捡棋子再爬楼是很费力而且不必要重复的，我用100楼开始丢可以避掉这些不必要的回朔。另外可能会有人问开始都要爬到100楼不是费了很多时间吗。现实世界中是，100是肯定有电梯的，费不了多少时间；对计算机世界来说，存储访问可以随机访问，对问题的初始化来说也不需要费多少时间）以上是我对这个问题的看法，希望有兴趣的朋友按此思路去建模。不要陷入连续数学函数论上去了。
r2007 回复于：2006-12-12 16:48:03
引用：原帖由 mlmyf 于 2006-12-12 16:21 发表
为什么不考虑从100楼开始丢呢，首先丢到98楼，如果粹了再丢第二个到99楼，如果粹了就是答案就是1层。如果100到98没碎，那么至少可以确定2层不会碎，从100把第二颗丢到98-3=95，如果碎了下到98丢到94楼。如果这样丢 ...
怎么知道可以丢到指定的楼层？，难道这楼是错层的？
既然可以从100楼准确的丢到任意楼层，是不是可以设计一个弹弓，从一楼发射，只要掌握好力度就可以让最高点是几楼就是几楼，掉下来看看碎没碎。所以如果优化策略考虑的是人上下楼的话，这个方案就可以。:mrgreen:
cugb_cat 回复于：2006-12-12 17:11:08
引用：原帖由 r2007 于 2006-12-12 16:48 发表
怎么知道可以丢到指定的楼层？，难道这楼是错层的？
既然可以从100楼准确的丢到任意楼层，是不是可以设计一个弹弓，从一楼发射，只要掌握好力度就可以让最高点是几楼就是几楼，掉下来看看碎没碎。所以如果优化 ...
嘎嘎，这个有趣～～～:em02::em03::m01:
mlmyf 回复于：2006-12-12 17:28:28
呵呵，楼上的这个问题问得好。好在比较实际。但针对这个问题我还可以提出另外一个看似一样荒谬的问题，那就是如果用于做实验的楼层各层高度并不一样，那么怎么做都会得出错误的结果。对于数学模型来说是不用考虑楼的样子怎么样，我这个模型是假设可以实现从某楼丢到下面任意层楼（因为下面我将讲道为了遵从数学模型，现实模型不至于面面都去为了堵这个数学模型，而相反应该设想（或简化）现实模型来归纳数学模型。而题目也没有作这样的限制，题目并没有说这个房子密不透风，也没有限制说试验者不可以从5楼丢到3楼来实现从2楼丢到底楼这一思想。相反，我认为题目的意思是要我们来实现找出（或算出）楼层这个“地址”或c语言的指针，而不是说一定要访问到某个地址。而实际上，在计算机中找出某个数据的地址后进行访问常常是快捷的）。事实上，我认为，在做本题这样的实验或者更复杂的实验的时候，实验设计者可能更多的是考虑怎样最快的实现这个实验，为了实现这个快速的策略，实验设计者会找到满足他的策略的100层楼，或者是在找不到在楼层设点东西也行，或两个人配合就可以实现策略。是的，如果问题规模很小，这些设置可能会更加浪费时间。但我要指出，计算机解问题的模型常常应考虑大规模的计算，这样做某些设置也许是划算的。
r2007 回复于：2006-12-12 17:42:44
那么楼上主张从100层开始的依据是什么？为什么解释自己的主张时就可以想用实际就用实际，想用模型解释就用模型？这不是双重标准吗？
ghostwwl 回复于：2006-12-12 17:58:23
引用：
想了一下，如果是两个玻璃球，最少次数m确定楼高为N的哪一层开始能使这个玻璃球摔碎这个问题，等价于求最小的m，使得 1+2+...+m >= N 。
14楼的对 我觉得应该是这样一个问题
mlmyf 回复于：2006-12-12 18:05:54
问题可描述为，查找某数a=b=x（1<=x<=n）在表K[1，2，3...，n]中的位置，其中K[k]=k（1<=k<=n）。当K[k]>=a时，a=0（表示a球碎了或a变量不再可用）（切不可用是否K[k]==a来判断是否正确位置k，这样就不能模拟题目的问题（体会一下，在确定下一个球是否碎之前是不能确定正确结果是否k）），接下来判断，如果K[k-1]<b,则结果为k，否则，结果只能为k-1；当K[k]<a时，者继续按某一策略搜索（即我上面所讲的策略或其他更好的策略）。这就是我对问题的精确描述，有了这样的描述可能问题就比较好考虑了，有时候问题转化可能就是答案哟！！！
mlmyf 回复于：2006-12-12 18:19:36
我主张从100楼开始的唯一目的是减少重复上下楼的动作（可能也有点钻牛角尖了），如果有其他办法减少也可以（比如用橡皮筋弄住玻璃珠子，让它蹦极，似乎扯远了，但出题者是不是允许让我们来扩展这些条件了不得而知）。至于双重标准说法我认为有嫌疑但并不确，我认为数学模型需要简化，但不能简化到偏离主题，或简化到实际不可行，那么就应该用实际来阻止进一步简化，我认为这就是我的标准。我上面的简化模型是实际可操作的模型，并非不着边际。感谢大家对我的想法提出意见。我甚至感觉应该重新严格考虑这个有趣的题目。同志们，大家努力吧，我感觉很有趣。
cugb_cat 回复于：2006-12-12 18:56:20
如果是数学建模竞赛，楼上的这个想法肯定能拿全国一等奖，如果是google招聘的话，我还是觉得楼上想偏了～～
在数学建模竞赛中，只要模型假设到位并能自圆其说就能拿到奖。
yjh777 回复于：2006-12-12 19:36:14
M = 临界层
m = step
需要扔的次数 = M/m + M%m
不知道怎么解。
感觉m应该是根号100 ：10
如果是77层，次数就是 7 + 7 次
如果是39层，次数就是 3 + 9 次
现在只是猜想：yjh猜想
没有证明。
r2007 回复于：2006-12-12 23:10:23
基本概念：
大前提：
1）临界层
使玻璃球破碎的最低的楼层。
2）最优解
100层中任意一层都可能是临界层，c(n)表示临界层为n层时该算法需要的测试次数，那么(c(1)+c(2)+...+c(100))/100为平均测试次数，平均测试次数最小的算法既为最优算法。
定理1：
若：a(n,m)表示有m个玻璃球，n层楼时的最优算法的测试平均值
则：a(n,m)<=a(n,m-1) a(n,m)<=a(n+1,m)
例：a(100,2)<=a(100,1) a(100,2)<=a(101,2)
定理2：
必然存在1<=k<n使
a(n,m)=(a(k,m-1)*k+a(n-k,m)*(n-k))/n +1
例如：a(100,2)为2个玻璃球100层的最小平均测试次数。因为第一次测试点选择100层是无意义的（必然会碎，所以无任何测试价值），所以第一次测试点k是1-99中的一个数。测试结果只有两种，碎了或没碎。
如果碎了,则临界层为[1，k]中的一个数，由于减少了一个测试球，所以接下来的测试等价于求解用m-1=1个球测试k个层的最优算法，其最小测试平均值为a(k,1)
若没碎,则临界层为[k+1，100]中的一个数，当然测试球没有减少，后续的测试等价于求解用2个球测试(100-k)个层的最优算法，其最小测试平均值为a(100-k,2)。
所以：必定存在k，使（因为已经测试了一次，所以a(k,1)要加1，同理a(100-k,2)+1）
a(100,2)=((a(k,1)+1)*k+(a(100-k,2)+1)*(100-k))/100=(a(k,1)*k+a(100-k,2)*(100-k))/100+1
定理3：
设t(n,m)=a(n,m)*n，那么t(n,m)最小的算法即为最优算法
同理
必然存在1<=k<n使
t(n,m)=t(k,m-1)+t(n-k,m) +n
本题m=2,则
t(n,2)=t(k,1)+t(n-k,2)+n
====================================================
显然t(1,0)=t(1,1)=t(1,2)=0
n=2时，k只能为1
t(2,2)=t(1,1)+t(1,2)+2=2
t(2,1)=t(1,0)+t(1,1)+2=2
n=3时，k=1 or 2用穷举法算出口k=1时最小（k=2时同样最小，取一个即可），记为k[3]=1
t(3,2)=t(1,1)+t(2,2)+3=0+2+3=5
t(3,1)=t(1,0)+t(2,1)+3=5
n=4时，k=1 , 2 or 3 用穷举法算出口k=2时最小,记为k[4]=2
t(4,2)=t(2,1)+t(2,2)+4=2+2+4=8
t(4,1)=t(1,0)+t(3,1)+4=9
循环至100时，得出k=14时最小，记为k[100]=14
即
t(100,2)=t(14,1)+t(100-14,2)+100
到这里方案已经出来了
首先在14层测试
若碎，执行用1球测14层楼的方案，即从1层开始逐层测试
若不碎，执行用2球测86层的方案，测试层为14+k[86]=14+13=27
最后在电子表格中演算了一下：若一直不碎，依次所选的测试楼层为
14，13，12，11，10，9，8，7，5，4，3，2，1
其中数字代表每次上升的楼层数。
t(100,2)=1030
临界层为任意楼层的情况下,测试的平均次数为1030/100=10.3
[ 本帖最后由 r2007 于 2006-12-13 09:29 编辑 ]
mlmyf 回复于：2006-12-13 08:34:58
呕，事实证明我上面给的方法效率底得很，昨晚终于想出一个我认为终极的算法，没上面的那么复杂，其实很简单。
1）首先测试当前最小可能的1层和”根号下的n“层，即测1层和10层。
如果都碎了，不用说就是1层了（测试次数1次），结束。
如果只有第10层的碎了，我们很幸运的把范围缩小到（2-10）同时，那么只有老老实实的用剩下的一颗从2层到9层来判断是哪一层。
如果都没有碎，我们又很幸运的把范围缩小到11-100之间的数。为什么幸运呢，因为我们还是有两颗棋子，而问题规模缩小了很多。
本次循环平均测试次数为10/2=5
2）把当前的最小层可能层设为”根号下的n“+1（这里设为11），测试11-（１１＋”根号下（１００－１０）“）（即测试１１－２０的层面）按１）作相同的循环
。。。
同样，本次循环的平均测试次数为１＋１０／２＝６次
３
mlmyf 回复于：2006-12-13 08:42:10
３）同样，如果有的话，第３次循环的平均测试次数可能为７（为什么说可能呢，根号的原因）。。。。。
总之这样逐步缩小范围用不到２０次循环次数即可结束，也就是最坏情况约为２０次测试。平均测试次数可以减小到１０次。
大家看看这个想法是不是比较好，请热烈讨论
jack9981 回复于：2006-12-13 09:37:07
个人观点：
1：爬到1楼跟爬到100楼的代价是不一样的，所以应该把楼层作为权重。
假设上或下一层楼的代价为X，在只有一个球的情况下，测出第 i（1<i<100） 层为目标需要的代价为： 【2*[1+2+...+(i-1)] + i】*X
第1层的代价为X，第100层代价＝第99层代价。
2：在求出临界层为K时
手中有2个球的代价 <= 手中有一个球的代价
3：假设手中有2个球，人在m层，扔下第一个球，如果没有碎，可以爬到m+1层，扔下第二个球，如果碎了，临界层为m+1,否则下楼拣2个球继续。。
[ 本帖最后由 jack9981 于 2006-12-13 09:45 编辑 ]
r2007 回复于：2006-12-13 09:52:53
如果测试者是人猿泰山或者格拉斯呢？:mrgreen:
开玩笑
gb8007 回复于：2006-12-13 11:34:38
引用：原帖由 isjfk 于 2006-12-11 13:58 发表
他没说你不能到楼底下把棋子拣上来再扔...
949494 哈哈
mlmyf 回复于：2006-12-13 14:07:53
1）首先测试当前最小可能的1层和”根号下的n“层，即测1层和10层。
如果都碎了，不用说就是1层了（测试次数1次），结束。
如果只有第10层的碎了，我们很幸运的把范围缩小到（2-10）同时，那么只有老老实实的用剩下的一颗从2层到9层来判断是哪一层。
如果都没有碎，我们又很幸运的把范围缩小到11-100之间的数。为什么幸运呢，因为我们还是有两颗棋子，而问题规模缩小了很多。
本次循环平均测试次数为10/2=5
2）把当前的最小层可能层设为”根号下的n“+1（这里设为11），测试11-（１１＋”根号下（１００－１０）“）（即测试１１－２０的层面）按１）作相同的循环
。。。
同样，本次循环的平均测试次数为１＋１０／２＝６次
３）同样，如果有的话，第３次循环的平均测试次数可能为７（为什么说可能呢，根号的原因）。。。。。
总之这样逐步缩小范围用不到２０次循环次数即可结束，也就是最坏情况约为２０次测试。平均测试次数可以减小到１０次。
大家看看这个想法是不是比较好，请热烈讨论
4).....
r2007 回复于：2006-12-13 15:01:47
前100层的计算表，t1表示t(楼层,1)，t2表示t(楼层,2),k为首次测试选则的楼层。
测试方案
13,12,11,10,9,8,8,7,6,5,4,3,2,1 每次若不碎则上升n层
或14，13，12，11，10，9，8，7，5，4，3，2，1 因为k值可以有多个。
楼层 t1 t2 k
-------------------------
1 0 0 0
2 2 2 1
3 5 5 1
4 9 8 2
5 14 12 2
6 20 16 2
7 27 20 3
8 35 25 3
9 44 30 3
10 54 35 3
11 65 40 4
12 77 46 4
13 90 52 4
14 104 58 4
15 119 64 4
16 135 70 5
17 152 77 5
18 170 84 5
19 189 91 5
20 209 98 5
21 230 105 5
22 252 112 6
23 275 120 6
24 299 128 6
25 324 136 6
26 350 144 6
27 377 152 6
28 405 160 6
29 434 168 7
30 464 177 7
31 495 186 7
32 527 195 7
33 560 204 7
34 594 213 7
35 629 222 7
36 665 231 7
37 702 240 8
38 740 250 8
39 779 260 8
40 819 270 8
41 860 280 8
42 902 290 8
43 945 300 8
44 989 310 8
45 1034 320 8
46 1080 330 9
47 1127 341 9
48 1175 352 9
49 1224 363 9
50 1274 374 9
51 1325 385 9
52 1377 396 9
53 1430 407 9
54 1484 418 9
55 1539 429 9
56 1595 440 10
57 1652 452 10
58 1710 464 10
59 1769 476 10
60 1829 488 10
61 1890 500 10
62 1952 512 10
63 2015 524 10
64 2079 536 10
65 2144 548 10
66 2210 560 10
67 2277 572 11
68 2345 585 11
69 2414 598 11
70 2484 611 11
71 2555 624 11
72 2627 637 11
73 2700 650 11
74 2774 663 11
75 2849 676 11
76 2925 689 11
77 3002 702 11
78 3080 715 11
79 3159 728 12
80 3239 742 12
81 3320 756 12
82 3402 770 12
83 3485 784 12
84 3569 798 12
85 3654 812 12
86 3740 826 12
87 3827 840 12
88 3915 854 12
89 4004 868 12
90 4094 882 12
91 4185 896 12
92 4277 910 13
93 4370 925 13
94 4464 940 13
95 4559 955 13
96 4655 970 13
97 4752 985 13
98 4850 1000 13
99 4949 1015 13
100 5049 1030 13
[ 本帖最后由 r2007 于 2006-12-13 15:04 编辑 ]
木刀客 回复于：2006-12-13 15:37:14
答案越多越看不懂
lbt5210 回复于：2006-12-13 21:38:33
2层以上100以下都有可能摔碎```嘎嘎```
sugarrose 回复于：2006-12-14 10:26:43
就是想要看谁能用最少的棋子来找到这个答案.
sendqmail 回复于：2006-12-14 13:05:14
高手啊！高手
mlmyf 回复于：2006-12-14 13:50:30
问题已解决：
1）首先测试当前最小可能的1层和”根号下的n“层，即测1层和10层。
如果都碎了，不用说就是1层了（测试次数1次），结束。
如果只有第10层的碎了，我们很幸运的把范围缩小到（2-10）同时，那么只有老老实实的用剩下的一颗从2层到9层来判断是哪一层。
如果都没有碎，我们又很幸运的把范围缩小到11-100之间的数。为什么幸运呢，因为我们还是有两颗棋子，而问题规模缩小了很多。
本次循环平均测试次数为10/2=5
2）把当前的最小层可能层设为”根号下的n“+1（这里设为11），测试11-（１１＋”根号下（１００－１０）“）（即测试１１－２０的层面）按１）作相同的循环
。。。
同样，本次循环的平均测试次数为１＋１０／２＝６次
３）同样，如果有的话，第３次循环的平均测试次数可能为７（为什么说可能呢，根号的原因）。。。。。
总之这样逐步缩小范围用不到２０次循环次数即可结束，也就是最坏情况约为２０次测试。平均测试次数可以减小到１０次。
大家看看这个想法是不是比较好，请热烈讨论
4).....
谁能找到比这更快的。
poize 回复于：2006-12-14 22:13:50
如果是第１０层是临界的话，如果你第８层扔下去以后，再到第九层扔，它有碎的可能，毕竟摔过一次有些损坏
认为最好的方法是，让google的面试官告诉你答案，然后你再去别的公司应聘，呵呵，开玩笑
cugb_cat 回复于：2006-12-14 22:26:59
引用：原帖由 poize 于 2006-12-14 22:13 发表
如果是第１０层是临界的话，如果你第８层扔下去以后，再到第九层扔，它有碎的可能，毕竟摔过一次有些损坏
这个想法太实际了吧？我到觉得既然是考试(笔试)题，应该是理想化了的，这么实际的东西不应该考虑吧。
cugb_cat 回复于：2006-12-14 22:29:44
引用：原帖由 mlmyf 于 2006-12-14 13:50 发表
问题已解决：
1）首先测试当前最小可能的1层和”根号下的n“层，即测1层和10层。
如果都碎了，不用说就是1层了（测试次数1次），结束。
如果只有第10层的碎了，我们很幸运的把范围缩小到（2-10）同时 ...
你得到的是20次啊，前面都得到14次了啊～～～
按照你的思路，最坏情况其实也到不了20，有16次就差不多了。
|
