出个题给大家活动活动脑子# Joke - 肚皮舞运动
l*s
1 楼
有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔，
5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
请问在最差的情况下最少要扔几次能找出这个N？怎么找？
5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
请问在最差的情况下最少要扔几次能找出这个N？怎么找？
Z*g
2 楼
面试题吧。
你这有漏洞，没说扔坏后能不能再扔，如果还能扔，一个球就够了。
你这有漏洞，没说扔坏后能不能再扔，如果还能扔，一个球就够了。
l*s
3 楼
好吧，加进去了
【在 Z**********g 的大作中提到】
: 面试题吧。
: 你这有漏洞，没说扔坏后能不能再扔，如果还能扔，一个球就够了。
【在 Z**********g 的大作中提到】
: 面试题吧。
: 你这有漏洞，没说扔坏后能不能再扔，如果还能扔，一个球就够了。
c*w
4 楼
还是要多做leetcode
【在 l*******s 的大作中提到】
: 有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔，
: 5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
: 从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
: 请问在最差的情况下最少要扔几次能找出这个N？怎么找？
【在 l*******s 的大作中提到】
: 有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔，
: 5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
: 从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
: 请问在最差的情况下最少要扔几次能找出这个N？怎么找？
H*g
5 楼
循环单元：
假如手里有n个好球 未知楼层藏在（n+1）！层楼里 那从下面开始每隔n！扔一下
可以吧未知定位在n！层里 最坏需要扔 n下 并销耗一个球 （这时候球藏在第n个n
！组里
末端情况：
n=2 时 假如有6层需要确定 每隔2层扔一下 即 扔2 楼 4楼 最坏情况下是4楼时球
坏 （扔了2下）手里剩一个球 但知道 3或4楼是目标 那3楼再一下就得结果（也就
是n=1的测试，扔一下） 若4楼时球没坏 6楼或者在n=3时已经测过 或者只需要在5楼
再扔一下便可确定
类似的 n=3时 假如24層需確定 每6层扔一下 可把范围缩小到6层内 剩两球 最
坏需要扔 3次（目标在13-18层）
所以：
有5个球时 首先把1000层分为9组 前八组每组120层 最后一组40层 扔8下 最坏情
况是第8下的时候坏了 知道在 841-960层之间
于是把120层分 5个（24层组） 进入n=4 最坏扔4下....然后扔3，2，1下知道答案，
共扔8+4+3+2+1=18下
而且最坏情况是目标在 960-24-6-2=928或927层 其中927层还略坏 因为球都死了
【在 l*******s 的大作中提到】
: 有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔，
: 5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
: 从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
: 请问在最差的情况下最少要扔几次能找出这个N？怎么找？
假如手里有n个好球 未知楼层藏在（n+1）！层楼里 那从下面开始每隔n！扔一下
可以吧未知定位在n！层里 最坏需要扔 n下 并销耗一个球 （这时候球藏在第n个n
！组里
末端情况：
n=2 时 假如有6层需要确定 每隔2层扔一下 即 扔2 楼 4楼 最坏情况下是4楼时球
坏 （扔了2下）手里剩一个球 但知道 3或4楼是目标 那3楼再一下就得结果（也就
是n=1的测试，扔一下） 若4楼时球没坏 6楼或者在n=3时已经测过 或者只需要在5楼
再扔一下便可确定
类似的 n=3时 假如24層需確定 每6层扔一下 可把范围缩小到6层内 剩两球 最
坏需要扔 3次（目标在13-18层）
所以：
有5个球时 首先把1000层分为9组 前八组每组120层 最后一组40层 扔8下 最坏情
况是第8下的时候坏了 知道在 841-960层之间
于是把120层分 5个（24层组） 进入n=4 最坏扔4下....然后扔3，2，1下知道答案，
共扔8+4+3+2+1=18下
而且最坏情况是目标在 960-24-6-2=928或927层 其中927层还略坏 因为球都死了
【在 l*******s 的大作中提到】
: 有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔，
: 5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
: 从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
: 请问在最差的情况下最少要扔几次能找出这个N？怎么找？
o*p
6 楼
这没有原题难
【在 l*******s 的大作中提到】
: 有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔，
: 5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
: 从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
: 请问在最差的情况下最少要扔几次能找出这个N？怎么找？
【在 l*******s 的大作中提到】
: 有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔，
: 5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
: 从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
: 请问在最差的情况下最少要扔几次能找出这个N？怎么找？
d*i
7 楼
不是二分法？
：有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔
，5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
：从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
：有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔
，5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
：从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
l*s
8 楼
我的答案是11次。
：
：
：
：
l*s
9 楼
1 2 3 4 5
1 1 1 1 1 1
2 2 3 3 3 3
3 3 6 7 7 7
4 4 10 14 15 15
5 5 15 25 30 31
6 6 21 41 56 62
7 7 28 63 98 119
8 8 36 92 162 218
9 9 45 129 255 381
10 10 55 175 385 637
11 11 66 231 561 1023
第一行：可用试验的球数m
第一列：总试验次数n
其他： m球n次能测出最高c层高度。
【在 l*******s 的大作中提到】
: 我的答案是11次。
:
: ：
: ：
1 1 1 1 1 1
2 2 3 3 3 3
3 3 6 7 7 7
4 4 10 14 15 15
5 5 15 25 30 31
6 6 21 41 56 62
7 7 28 63 98 119
8 8 36 92 162 218
9 9 45 129 255 381
10 10 55 175 385 637
11 11 66 231 561 1023
第一行：可用试验的球数m
第一列：总试验次数n
其他： m球n次能测出最高c层高度。
【在 l*******s 的大作中提到】
: 我的答案是11次。
:
: ：
: ：
H*g
10 楼
1球1下岂非2层乎？
2球2下岂非4层乎？
2球下：1下从2层扔，没坏：N=3或4，第二下从3楼扔可知N是3还是4. 坏了：第二下从1
楼扔可知N是1 还是2
换句话说，二分法的话，n球n下至少可以分出2的n次方，不需减1吧。
【在 l*******s 的大作中提到】
: 1 2 3 4 5
: 1 1 1 1 1 1
: 2 2 3 3 3 3
: 3 3 6 7 7 7
: 4 4 10 14 15 15
: 5 5 15 25 30 31
: 6 6 21 41 56 62
: 7 7 28 63 98 119
: 8 8 36 92 162 218
: 9 9 45 129 255 381
2球2下岂非4层乎？
2球下：1下从2层扔，没坏：N=3或4，第二下从3楼扔可知N是3还是4. 坏了：第二下从1
楼扔可知N是1 还是2
换句话说，二分法的话，n球n下至少可以分出2的n次方，不需减1吧。
【在 l*******s 的大作中提到】
: 1 2 3 4 5
: 1 1 1 1 1 1
: 2 2 3 3 3 3
: 3 3 6 7 7 7
: 4 4 10 14 15 15
: 5 5 15 25 30 31
: 6 6 21 41 56 62
: 7 7 28 63 98 119
: 8 8 36 92 162 218
: 9 9 45 129 255 381
l*s
11 楼
我用的是c层高度，不是第c层。
所以减一
从1
【在 H********g 的大作中提到】
: 1球1下岂非2层乎？
: 2球2下岂非4层乎？
: 2球下：1下从2层扔，没坏：N=3或4，第二下从3楼扔可知N是3还是4. 坏了：第二下从1
: 楼扔可知N是1 还是2
: 换句话说，二分法的话，n球n下至少可以分出2的n次方，不需减1吧。
所以减一
从1
【在 H********g 的大作中提到】
: 1球1下岂非2层乎？
: 2球2下岂非4层乎？
: 2球下：1下从2层扔，没坏：N=3或4，第二下从3楼扔可知N是3还是4. 坏了：第二下从1
: 楼扔可知N是1 还是2
: 换句话说，二分法的话，n球n下至少可以分出2的n次方，不需减1吧。
H*g
12 楼
哦，错了，一下如果死了，是不知道N是否等于2的，所以1下就能分一层。
在2球2下的情况，如果第二下需要分3 和4， 第二下如果也死了， 是分不清3和4的
所以确实是n球n下只能分2的n次方减一
从1
【在 H********g 的大作中提到】
: 1球1下岂非2层乎？
: 2球2下岂非4层乎？
: 2球下：1下从2层扔，没坏：N=3或4，第二下从3楼扔可知N是3还是4. 坏了：第二下从1
: 楼扔可知N是1 还是2
: 换句话说，二分法的话，n球n下至少可以分出2的n次方，不需减1吧。
在2球2下的情况，如果第二下需要分3 和4， 第二下如果也死了， 是分不清3和4的
所以确实是n球n下只能分2的n次方减一
从1
【在 H********g 的大作中提到】
: 1球1下岂非2层乎？
: 2球2下岂非4层乎？
: 2球下：1下从2层扔，没坏：N=3或4，第二下从3楼扔可知N是3还是4. 坏了：第二下从1
: 楼扔可知N是1 还是2
: 换句话说，二分法的话，n球n下至少可以分出2的n次方，不需减1吧。
H*g
13 楼
你是对的，我那里想错了
【在 l*******s 的大作中提到】
: 我用的是c层高度，不是第c层。
: 所以减一
:
: 从1
【在 l*******s 的大作中提到】
: 我用的是c层高度，不是第c层。
: 所以减一
:
: 从1
l*s
14 楼
c(n,m)=1, n=1
c(n,m)=n, m=1
c(n,m)=c(n-1,m-1)+c(n-1,m)+1, m>1,n>1
【在 l*******s 的大作中提到】
: 我用的是c层高度，不是第c层。
: 所以减一
:
: 从1
c(n,m)=n, m=1
c(n,m)=c(n-1,m-1)+c(n-1,m)+1, m>1,n>1
【在 l*******s 的大作中提到】
: 我用的是c层高度，不是第c层。
: 所以减一
:
: 从1
H*g
15 楼
2球3下，第一次肯定得从2层扔，没死，第二次从4层扔，没死，第三次从5层扔，又没
死，那只能知道N>=6吧，还是不能确定N是不是6，所以扔三下似乎只能确定5层
2球4下，我就想不出来怎么可以确定10层了。我的做法只能确定7层: 因为最后一个球
只能用来判别1层，所以第一个球每次只能两层两层往上走，扔3次怎么能弄到8层呢？
【在 l*******s 的大作中提到】
: c(n,m)=1, n=1
: c(n,m)=n, m=1
: c(n,m)=c(n-1,m-1)+c(n-1,m)+1, m>1,n>1
死，那只能知道N>=6吧，还是不能确定N是不是6，所以扔三下似乎只能确定5层
2球4下，我就想不出来怎么可以确定10层了。我的做法只能确定7层: 因为最后一个球
只能用来判别1层，所以第一个球每次只能两层两层往上走，扔3次怎么能弄到8层呢？
【在 l*******s 的大作中提到】
: c(n,m)=1, n=1
: c(n,m)=n, m=1
: c(n,m)=c(n-1,m-1)+c(n-1,m)+1, m>1,n>1
H*g
16 楼
你这字母选的，很老大爷啊
【在 l*******s 的大作中提到】
: c(n,m)=1, n=1
: c(n,m)=n, m=1
: c(n,m)=c(n-1,m-1)+c(n-1,m)+1, m>1,n>1
【在 l*******s 的大作中提到】
: c(n,m)=1, n=1
: c(n,m)=n, m=1
: c(n,m)=c(n-1,m-1)+c(n-1,m)+1, m>1,n>1
H*g
17 楼
c 层 m 球 n 扔
c 层 q 球 r 扔 ceng qiu reng
c 层 b 球 t 扔 ceng ball toss（throw）
f 层 m 球 t 扔 floor marble toss
【在 H********g 的大作中提到】
: 你这字母选的，很老大爷啊
c 层 q 球 r 扔 ceng qiu reng
c 层 b 球 t 扔 ceng ball toss（throw）
f 层 m 球 t 扔 floor marble toss
【在 H********g 的大作中提到】
: 你这字母选的，很老大爷啊
H*g
18 楼
层（扔，球）=层（扔-1，球-1）+层（扔-1，球）+1 ，当 球>1,扔>1
我还得仔细想想
【在 l*******s 的大作中提到】
: c(n,m)=1, n=1
: c(n,m)=n, m=1
: c(n,m)=c(n-1,m-1)+c(n-1,m)+1, m>1,n>1
我还得仔细想想
【在 l*******s 的大作中提到】
: c(n,m)=1, n=1
: c(n,m)=n, m=1
: c(n,m)=c(n-1,m-1)+c(n-1,m)+1, m>1,n>1
H*g
19 楼
6层 3扔 2球的时候，能确定的为啥是 2扔1球（2层） + 2扔2球（3层） +1
层 呢？
【在 H********g 的大作中提到】
: 层（扔，球）=层（扔-1，球-1）+层（扔-1，球）+1 ，当 球>1,扔>1
: 我还得仔细想想
层 呢？
【在 H********g 的大作中提到】
: 层（扔，球）=层（扔-1，球-1）+层（扔-1，球）+1 ，当 球>1,扔>1
: 我还得仔细想想
H*g
20 楼
哦，6层 3扔 2球的时候
第一下从3层扔【1扔知道一层】，死了的话，剩下一个球扔两下可以用来确定1，2 【2扔
1球（2层）】 。没死的话，还有两球两下，可以用来确定4，5，6 【 2扔2球（3层）】
所以是
3扔2球 = 【死一球】2扔1球（2层） + 【未死一球】2扔2球（3层） + 1扔(1层)
同理
n扔m球的时候
n扔m球 = 【用一扔，死一球】(n-1)扔(m-1)球 + 【用一扔，未死一球】(n-1)扔m球
+ 1扔(1层)
所以用熊大公式迭代制表就可以了
1扔1球(1层)
【在 H********g 的大作中提到】
: 6层 3扔 2球的时候，能确定的为啥是 2扔1球（2层） + 2扔2球（3层） +1
: 层 呢？
第一下从3层扔【1扔知道一层】，死了的话，剩下一个球扔两下可以用来确定1，2 【2扔
1球（2层）】 。没死的话，还有两球两下，可以用来确定4，5，6 【 2扔2球（3层）】
所以是
3扔2球 = 【死一球】2扔1球（2层） + 【未死一球】2扔2球（3层） + 1扔(1层)
同理
n扔m球的时候
n扔m球 = 【用一扔，死一球】(n-1)扔(m-1)球 + 【用一扔，未死一球】(n-1)扔m球
+ 1扔(1层)
所以用熊大公式迭代制表就可以了
1扔1球(1层)
【在 H********g 的大作中提到】
: 6层 3扔 2球的时候，能确定的为啥是 2扔1球（2层） + 2扔2球（3层） +1
: 层 呢？
l*s
21 楼
先拿一个球在c(n-1,m-1)+1层往下扔。
如果坏了，剩下c(n-1,m-1)个低层，还有m-1个球，n-1扔。
如果没坏，剩下c(n-1,m)个高层，还有m个球，n-1扔。
如果坏了，剩下c(n-1,m-1)个低层，还有m-1个球，n-1扔。
如果没坏，剩下c(n-1,m)个高层，还有m个球，n-1扔。
H*g
22 楼
还好我提前一分钟自己想明白了，可以去玩别的了。
【在 l*******s 的大作中提到】
: 先拿一个球在c(n-1,m-1)+1层往下扔。
: 如果坏了，剩下c(n-1,m-1)个低层，还有m-1个球，n-1扔。
: 如果没坏，剩下c(n-1,m)个高层，还有m个球，n-1扔。
【在 l*******s 的大作中提到】
: 先拿一个球在c(n-1,m-1)+1层往下扔。
: 如果坏了，剩下c(n-1,m-1)个低层，还有m-1个球，n-1扔。
: 如果没坏，剩下c(n-1,m)个高层，还有m个球，n-1扔。
l*s
23 楼
我前面发了一次，系统出错，没发成功。
然后我看见你想明白了，
【在 H********g 的大作中提到】
: 还好我提前一分钟自己想明白了，可以去玩别的了。
然后我看见你想明白了，
【在 H********g 的大作中提到】
: 还好我提前一分钟自己想明白了，可以去玩别的了。
H*g
24 楼
老邢助我
【在 l*******s 的大作中提到】
: 我前面发了一次，系统出错，没发成功。
: 然后我看见你想明白了，
【在 l*******s 的大作中提到】
: 我前面发了一次，系统出错，没发成功。
: 然后我看见你想明白了，
f*x
25 楼
不是二分法？
：有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔
，5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
：从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
----------------
我正在看的剧:
火星生活
https://daxiv.com/sc/detail/5b847269e401aa0008c206d7
韩版《火星生活》由OCN翻拍自同名英剧，讲述了因突发事故而穿越回到过去的刑警为
了回归自己原先的生活而解决连环杀人案的故事。
【在 l*******s 的大作中提到】
: 我前面发了一次，系统出错，没发成功。
: 然后我看见你想明白了，
：有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔
，5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
：从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
----------------
我正在看的剧:
火星生活
https://daxiv.com/sc/detail/5b847269e401aa0008c206d7
韩版《火星生活》由OCN翻拍自同名英剧，讲述了因突发事故而穿越回到过去的刑警为
了回归自己原先的生活而解决连环杀人案的故事。
【在 l*******s 的大作中提到】
: 我前面发了一次，系统出错，没发成功。
: 然后我看见你想明白了，
l*s
26 楼
不是bisection
是divide and conquer
中文二分法是什么？
【在 f***x 的大作中提到】
: 不是二分法？
:
: ：有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔
: ，5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
: ：从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
: ----------------
: 我正在看的剧:
: 火星生活
: https://daxiv.com/sc/detail/5b847269e401aa0008c206d7
: 韩版《火星生活》由OCN翻拍自同名英剧，讲述了因突发事故而穿越回到过去的刑警为
是divide and conquer
中文二分法是什么？
【在 f***x 的大作中提到】
: 不是二分法？
:
: ：有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔
: ，5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
: ：从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
: ----------------
: 我正在看的剧:
: 火星生活
: https://daxiv.com/sc/detail/5b847269e401aa0008c206d7
: 韩版《火星生活》由OCN翻拍自同名英剧，讲述了因突发事故而穿越回到过去的刑警为
d*a
27 楼
码农们只知道二分法
却不知道材料断裂强度跟冲击力不是线性的
也不知道坠地速度也不是线性的
知道球的材料 一个也不需要摔碎 手就能算出来
: 不是二分法？
: ：有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼
往下扔
: ，5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
: ：从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
:
: ----------------
: 我正在看的剧:
: 火星生活
: https://daxiv.com/sc/detail/5b847269e401aa0008c206d7
: 韩版《火星生活》由OCN翻拍自同名英剧，讲述了因突发事故而穿越回到过去的
刑警为
【在 f***x 的大作中提到】
: 不是二分法？
:
: ：有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔
: ，5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
: ：从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
: ----------------
: 我正在看的剧:
: 火星生活
: https://daxiv.com/sc/detail/5b847269e401aa0008c206d7
: 韩版《火星生活》由OCN翻拍自同名英剧，讲述了因突发事故而穿越回到过去的刑警为
却不知道材料断裂强度跟冲击力不是线性的
也不知道坠地速度也不是线性的
知道球的材料 一个也不需要摔碎 手就能算出来
: 不是二分法？
: ：有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼
往下扔
: ，5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
: ：从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
:
: ----------------
: 我正在看的剧:
: 火星生活
: https://daxiv.com/sc/detail/5b847269e401aa0008c206d7
: 韩版《火星生活》由OCN翻拍自同名英剧，讲述了因突发事故而穿越回到过去的
刑警为
【在 f***x 的大作中提到】
: 不是二分法？
:
: ：有5只强度一样的球，从一个1000层高的楼往下扔，在第N层及往上的任一层楼往下扔
: ，5个球都会摔坏，并且一次就坏,摔坏了就不能再扔了。
: ：从低于第N层的任何楼层往下扔，怎么扔都不摔坏。
: ----------------
: 我正在看的剧:
: 火星生活
: https://daxiv.com/sc/detail/5b847269e401aa0008c206d7
: 韩版《火星生活》由OCN翻拍自同名英剧，讲述了因突发事故而穿越回到过去的刑警为
相关阅读
Re: 码工是米帝的脊梁 (转载)到底有没有磁单极嘛一人到警察局自首，他剪掉他小狗的耳朵刷试管之余终于感受了一下小留的青春 (转载)锹甲虫大战大黄蜂Re: 盘点全球12种奇葩饺子 (转载)[bssd]我就是靠男人的主儿 (转载)奥巴马没啥政绩就专搞破坏啊有多少颗痣？寄生虫就是递归（转）美国统治：反犹财团和犹太财团之间的历史缠斗 (转载)是买买提又抽风了？？关于中西方普通人中的帅哥，我有发言权 (转载)读笑版那个《老公的三个笑话》有感 (转载)毛泽东金正日他们怎公都不长胡子求助： 这种情况该不该告诉她男盆友（fiance）转载自南京大学小 (转载)学术：为什么总看见转帖到学术版，不见学术版的帖子出口呢？刷试管之余终于感受了一下小留的青春 (转载)美版小龙女P民被临时解除枷锁引发的思考zz