呵呵！使用黄金分割法啊！很快就知道了

石头有限呀
不知道用老鼠代替行不

不对啊,虽然我也不知道正确答案,不过我知道有一个20次左右可以测出的方法, 不会很大的.

不能用简单的二分法

如果没碎
是不是可以捡起来

of course!!

哈哈！就是使用黄金分割法得到的啊

[quote]一种石头，在某一高度扔下就会碎，在这个高度以下不会碎，高度以上一定碎 现在有4个石头，1000层的楼房，需要测定这个石头破碎的高度 求最少多少次一定可以测出来  

因为1000大致==2的10次方

而只有4块石头，而且估计碎了之后就不能再扔了。

因此一开始恐怕只好从底下开始，而且每次上升差距不应该

超过16，就是说，不能超过4快石头能够解析的高度。

1、0楼绝对不会碎

2、跑到16楼去扔一块

3、如果碎了，那么8，还是碎了，然后4，还是碎了，那么2

依次类推，需要1000/16+4次


ps：俺没有仔细想清楚边界条件，也许答案会多一次少一次的。

 [/quote]


这个解法不对，我已经找到了一个次数更少的方法，
不过还没有想清楚。

当2分次数太多的时候，如果相对于一级级上升还多的时候，
就不够适用了。


由于我倾向于完全解析性的解决问题，在任何时候都不愿意
使用从下到上的穷举，所以下面提供一个更好的解析方法。

因为有些时候扔下来的时候石头没有碎，所以还可以再次
使用，因为4块石头的分辨率并非只有16。

例如可以是
1+
1+（1+2）+
1+（1+2）+（1+2+4）+
1+（1+2）+（1+2+4）+（1+2+4+8）= 42

因此，1000/42 = 23，分辨率到了42之后，
可以按照26，11，4，1的次序往下扔。
至于用4块石头解析42，最多需要的次数
大致如下：
26：碎了，还有3块
11：没碎，还有3块
18：没碎，还有3块
剩下26到18之间只有8，3块石头足够了
如果18碎了，那么18到11之间有7，还有2块石头，
等价于7层，只有2块石头，然后是4层，
如果碎了，那么是3-1，只有一块石头，
如果没有碎，那么7-4，还有2块石头。


以上的考虑并没有包含到如果最后无法用确定性
方法解析的时候，使用从下到上穷举的方法，而且
似乎这个问题和1000这个数字还有关系，我个人
倾向于这种方法不可能好过上面所提供的完全解析
法，不过我现在还无法证明。

[quote][quote]一种石头，在某一高度扔下就会碎，在这个高度以下不会碎，高度以上一定碎 现在有4个石头，1000层的楼房，需要测定这个石头破碎的高度 求最少多少次一定可以测出来  

因为1000大致==2的10次方

而只有4块石头，而且估计碎了之后就不能再扔了。

因此一开始恐怕只好从底下开始，而且每次上升差距不应该

超过16，就是说，不能超过4快石头能够解析的高度。

1、0楼绝对不会碎

2、跑到16楼去扔一块

3、如果碎了，那么8，还是碎了，然后4，还是碎了，那么2

依次类推，需要1000/16+4次


ps：俺没有仔细想清楚边界条件，也许答案会多一次少一次的。

 [/quote]


这个解法不对，我已经找到了一个次数更少的方法，
不过还没有想清楚。

当2分次数太多的时候，如果相对于一级级上升还多的时候，
就不够适用了。


由于我倾向于完全解析性的解决问题，在任何时候都不愿意
使用从下到上的穷举，所以下面提供一个更好的解析方法。

因为有些时候扔下来的时候石头没有碎，所以还可以再次
使用，因为4块石头的分辨率并非只有16。

例如可以是
1+
1+（1+2）+
1+（1+2）+（1+2+4）+
1+（1+2）+（1+2+4）+（1+2+4+8）= 42

因此，1000/42 = 23，分辨率到了42之后，
可以按照26，11，4，1的次序往下扔。
至于用4块石头解析42，最多需要的次数
大致如下：
26：碎了，还有3块
11：没碎，还有3块
18：没碎，还有3块
剩下26到18之间只有8，3块石头足够了
如果18碎了，那么18到11之间有7，还有2块石头，
等价于7层，只有2块石头，然后是4层，
如果碎了，那么是3-1，只有一块石头，
如果没有碎，那么7-4，还有2块石头。


以上的考虑并没有包含到如果最后无法用确定性
方法解析的时候，使用从下到上穷举的方法，而且
似乎这个问题和1000这个数字还有关系，我个人
倾向于这种方法不可能好过上面所提供的完全解析
法，不过我现在还无法证明。

 [/quote]

当你每扔碎一次，你就会少一块石头，不防先从两块石头考虑。
要上班了，下次再说。

一个思路是：第一个石头先把1000层划分成a块，第二块石头把每块划分成b小块，第三块再化c小块，第四块遍历最小的小块。
 
(a-1)+(b-1)+(c-1)+(1000/abc)-1 最小值

哈哈！碎了石头就从一块变成多块啦

这道题我们应反过来考虑，就是用a块石头扔b次至多一定可分辨层数X(a,b)。

先从最简装的一块石头考虑,很显然,
X(1,1) = 1
X(1,2) = 2
X(1,3) = 3
.
X(1,i) = i

再考虑二块石头,显而易见
X(2,1) = 1

对于X(2,2),我们可这样考虑,当我们扔第一次后,有两种可能:破和不破.

如果石头破了,则

1,我们还剩1块石头.
2,我们下一次只需检查下面的楼层.
3,我们还剩1次机会.
即我们还可分辨下面的 X(1,1) 层.

如果石头没破,则

1,我们还剩2块石头.
2,我们下一次只需检查上面的楼层.
3,我们还剩1次机会.
即我们还可分辨上面的 X(2,1) 层.

我们知道,X(1,1) = 1.所以我们第一次从第二层开始扔,如果石头破了,则再测试第一层.如果没破则再测试第三层.
所以用2块石头扔2次至多一定可分辨
1 + X(1,1) + X(2,1) = 1 + 1 + 1 = 3 层.

不失一般性,我们考虑
X(2,i)

对X(2,i),我们这样考虑,当我们扔第一次后,有两种可能:破和不破.

如果石头破了,则

1,我们还剩1块石头.
2,我们下一次只需检查下面的楼层.
3,我们还剩i-1次机会.
即我们还可分辨下面的 X(1,i-1) 层.

如果石头没破,则

1,我们还剩2块石头.
2,我们下一次只需检查上面的楼层.
3,我们还剩i-1次机会.
即我们还可分辨上面的 X(2,i-1) 层.

则
X(2,i) = 1 + X(1,i-1) + X(2,i-1)

接下来我们考虑
X(i1,i2)

同样,对 X(i1,i2),我们还是这样考虑,当我们扔第一次后,有两种可能:破和不破.

如果石头破了,则
1,我们还剩i1-1块石头.
2,我们下一次只需检查下面的楼层.
3,我们还剩i2-1次机会.

如果石头没破,则
1,我们还剩i1块石头.
2,我们下一次只需检查上面的楼层.
3,我们还剩i2-1次机会.

即
X(i1,i2) = 1 + X(i1-1,i2-1) + X(i1,i2-1)

很明显
无论你有几块石头,扔一次只能测试一层.

即
X(i,1) = 1.

这样,我们可制出如下表:

扔的次数: 1 2 3 04 05 06 007 008 009 010 011 012 013
分辨层数:
一块石头: 1 2 3 04 05 06 007 008 009 010 011 012 013
二块石头: 1 3 6 10 15 21 028 036 045 055 066 078 091
三块石头: 1 3 7 14 25 41 063 092 129 175 231 298 377
四块石头: 1 3 7 15 30 56 098 162 255 385 561 793 1092
五块石头: 1 3 7 15 31 62 119 218 381 637 1023
六块石头: 1 3 7 15 31 63 126 246 465 847 1485

也就是说用4块石头扔12次至多一定可分辨793层,扔13次至多一定可分辨1092层.

所以
1000层的楼房,

用4块石头,扔13次一定可测试出来.
用5块石头,扔11次一定可测试出来.

呵呵！劳烦狼兄再用黄金分割法再看看

呵呵！劳烦狼兄再用黄金分割法再看看

我认为“黄金分割法”是一种基于统计理论的算法。是统计最优，非一定最好。

你看看你列出来的那个表，跟黄金分割法里面算出来的有多少的差别啊！

1000的分界点是382左右！而382的是146，呵呵！这样算下去看看有多少的差别

1000的分界点是382左右！而382的是146，呵呵！这样算下去看看有多少的差别

我的第一个分界点是299，第二个分界点是67，531。而且与石头数有关。

这道题我们应反过来考虑，就是用a块石头扔b次至多一定可分辨层数X(a,b)。

先从最简装的一块石头考虑,很显然,
X(1,1) = 1
X(1,2) = 2
X(1,3) = 3
.
X(1,i) = i

再考虑二块石头,显而易见
X(2,1) = 1

对于X(2,2),我们可这样考虑,当我们扔第一次后,有两种可能:破和不破.

如果石头破了,则

1,我们还剩1块石头.
2,我们下一次只需检查下面的楼层.
3,我们还剩1次机会.
即我们还可分辨下面的 X(1,1) 层.

如果石头没破,则

1,我们还剩2块石头.
2,我们下一次只需检查上面的楼层.
3,我们还剩1次机会.
即我们还可分辨上面的 X(2,1) 层.

我们知道,X(1,1) = 1.所以我们第一次从第二层开始扔,如果石头破了,则再测试第一层.如果没破则再测试第三层.
所以用2块石头扔2次至多一定可分辨
1 + X(1,1) + X(2,1) = 1 + 1 + 1 = 3 层.

不失一般性,我们考虑
X(2,i)

对X(2,i),我们这样考虑,当我们扔第一次后,有两种可能:破和不破.

如果石头破了,则

1,我们还剩1块石头.
2,我们下一次只需检查下面的楼层.
3,我们还剩i-1次机会.
即我们还可分辨下面的 X(1,i-1) 层.

如果石头没破,则

1,我们还剩2块石头.
2,我们下一次只需检查上面的楼层.
3,我们还剩i-1次机会.
即我们还可分辨上面的 X(2,i-1) 层.

则
X(2,i) = 1 + X(1,i-1) + X(2,i-1)

接下来我们考虑
X(i1,i2)

同样,对 X(i1,i2),我们还是这样考虑,当我们扔第一次后,有两种可能:破和不破.

如果石头破了,则
1,我们还剩i1-1块石头.
2,我们下一次只需检查下面的楼层.
3,我们还剩i2-1次机会.

如果石头没破,则
1,我们还剩i1块石头.
2,我们下一次只需检查上面的楼层.
3,我们还剩i2-1次机会.

即
X(i1,i2) = 1 + X(i1-1,i2-1) + X(i1,i2-1)

很明显
无论你有几块石头,扔一次只能测试一层.

即
X(i,1) = 1.

这样,我们可制出如下表:

扔的次数: 1 2 3 04 05 06 007 008 009 010 011 012 013
分辨层数:
一块石头: 1 2 3 04 05 06 007 008 009 010 011 012 013
二块石头: 1 3 6 10 15 21 028 036 045 055 066 078 091
三块石头: 1 3 7 14 25 41 063 092 129 175 231 298 377
四块石头: 1 3 7 15 30 56 098 162 255 385 561 793 1092
五块石头: 1 3 7 15 31 62 119 218 381 637 1023
六块石头: 1 3 7 15 31 63 126 246 465 847 1485

也就是说用4块石头扔12次至多一定可分辨793层,扔13次至多一定可分辨1092层.

所以
1000层的楼房,

用4块石头,扔13次一定可测试出来.
用5块石头,扔11次一定可测试出来.
 

我认为这个解法有错，例如说2块石头，表中说扔6次可以解析
21楼，我认为是不可能的。从第一层开始扔，1，3，6，10，15
5次，都没有碎，到21，碎了，然后一块石头判断21-15，可不是
1次能够搞定的阿。

我认为这个解法有错，例如说2块石头，表中说扔6次可以解析
21楼，我认为是不可能的。从第一层开始扔，1，3，6，10，15
5次，都没有碎，到21，碎了，然后一块石头判断21-15，可不是
1次能够搞定的阿。

不，不从第一层开始扔。
从第6层开始，如果碎了，再从第一层开始；  1 + 5 = 6
如果没碎，再去11楼。如碎，从7楼； 1 + 1 + 4 = 6
如还没碎，再至15楼。碎则从12楼； 1 + 1 + 1 + 3 = 6
如仍没碎，上18楼。碎至16楼； 1 + 1 + 1 + 1 + 2 = 6
又没碎，上20楼。碎去19； 1 + 1 + 1 + 1 + 1 + 1 = 6
没碎，上21楼。 1 + 1 + 1 + 1 + 1 + 1 = 6

[编辑 -  10/21/02 by  u_you]

[quote]
我认为这个解法有错，例如说2块石头，表中说扔6次可以解析
21楼，我认为是不可能的。从第一层开始扔，1，3，6，10，15
5次，都没有碎，到21，碎了，然后一块石头判断21-15，可不是
1次能够搞定的阿。

不，不从第一层开始扔。
从第6层开始，如果碎了，再从第一层开始；  1 + 5 = 6
如果没碎，再去11楼。如碎，从7楼； 1 + 1 + 4 = 6
如还没碎，再至15楼。碎则从12楼； 1 + 1 + 1 + 3 = 6
如仍没碎，上18楼。碎至16楼； 1 + 1 + 1 + 1 + 2 = 6
又没碎，上20楼。碎去19； 1 + 1 + 1 + 1 + 1 + 1 = 6
没碎，上21楼。 1 + 1 + 1 + 1 + 1 + 1 = 6

[编辑 -  10/21/02 by  u_you] [/quote]

呵呵，不错。

我觉的这个解法有问题：
比如说 X(2,6) = 21
而实际上2块石头扔5次就可以解析21楼，方法如下：

1.楼层区间三分为（1，7）（9，14）（16，21）第一块石头从下往上测试8,15楼，无论是否破碎，两次内可选出一个区间，不凡设为（1，7）

2.第二块石头测试4楼，无论是否破碎，一次可选出区间（1，3）（5，7），设为（1，3）

3.余下两块石头扔两次显然可以解析3层的楼

所以总共的次数 2＋1＋2 ＝ 5
即有 X(2,5) >= 21, 而表中X(2,5) = 15

[quote]
我认为这个解法有错，例如说2块石头，表中说扔6次可以解析
21楼，我认为是不可能的。从第一层开始扔，1，3，6，10，15
5次，都没有碎，到21，碎了，然后一块石头判断21-15，可不是
1次能够搞定的阿。

不，不从第一层开始扔。
从第6层开始，如果碎了，再从第一层开始；  1 + 5 = 6
如果没碎，再去11楼。如碎，从7楼； 1 + 1 + 4 = 6
如还没碎，再至15楼。碎则从12楼； 1 + 1 + 1 + 3 = 6
如仍没碎，上18楼。碎至16楼； 1 + 1 + 1 + 1 + 2 = 6
又没碎，上20楼。碎去19； 1 + 1 + 1 + 1 + 1 + 1 = 6
没碎，上21楼。 1 + 1 + 1 + 1 + 1 + 1 = 6

[编辑 -  10/21/02 by  u_you] [/quote]
大哥：――我以到了1000楼，还没碎――怎么办！！ :D :D :D

我觉的这个解法有问题：
比如说 X(2,6) = 21
而实际上2块石头扔5次就可以解析21楼，方法如下：

1.楼层区间三分为（1，7）（9，14）（16，21）第一块石头从下往上测试8,15楼，无论是否破碎，两次内可选出一个区间，不凡设为（1，7）

2.第二块石头测试4楼，无论是否破碎，一次可选出区间（1，3）（5，7），设为（1，3）

3.余下两块石头扔两次显然可以解析3层的楼

所以总共的次数 2＋1＋2 ＝ 5
即有 X(2,5) >= 21, 而表中X(2,5) = 15
 

可你好象用了四块石头. X(4,5) = 30 > 21;

另:
几时按\"改分\"将问题分数改为200分再放给我??? :D :D :D