趣题, 第8道来了。

lastwinner · 发表于 2012-5-12 01:23

本帖最后由 lastwinner 于 2012-5-12 04:12 编辑

newkid 发表于 2012-5-11 21:28
蛋不够吧？
两层两层往上走？摔得蛋疼。

哈哈，你也说蛋疼啊
我想到的是三分，12层为一个单位，先在1~12层测，然后在1/3处，即第4层抛，若没碎，就在2/3处，即第8层抛，若碎了，就从1层开始抛。依此类推。

不过这个题问得有问题，假设N楼就刚好会摔坏，那么第一次从N楼扔，碎了，第二次从N-1楼扔，没碎，两次就能测出了。当然，这不符合“保证”，不过也至少说明有歧义
还有一个问题就是万一蛋从36层的天花板往下扔也不会碎，那就怎么也测不出来了

正确的问法应该是“采取什么样的策略才能保证在最少次数内测出高度？”
按我前面的策略，最少2次，最多11次
达到题目要求的策略，应该是无论是1层就碎还是36层才碎（假定36层一定会碎），要保证你的策略总能测出准确的楼层，并且最多测试的那次在所有不同的策略中最小，那么你就回答对了

newkid · 发表于 2012-5-12 02:33

这个“最少”，要和偶然蒙对的比是不可能的，任何一楼层都有可能两次蒙对。
要和其他策略比难度很大，因为你没法穷尽所有策略，实际上就是要求从理论上证明。
先提出一个猜想：假如经过Tn次试验得到了n层不碎，下一次发生在m层时候碎了，那就用剩下的一个蛋从n+1....m-1逐一尝试。
m和n是什么关系呢？猜想m-n=1,2,4,8,....
第一个蛋从2,3,5,9,17,33
如果碎了从前一次+1开始扔第二个。

lastwinner · 发表于 2012-5-12 03:10

newkid 发表于 2012-5-12 02:33
这个“最少”，要和偶然蒙对的比是不可能的，任何一楼层都有可能两次蒙对。
要和其他策略比难度很大，因为 ...

你这个办法明显比我的那个次数要多，例如29层不碎30层才碎

lastwinner · 发表于 2012-5-12 03:57

lastwinner 发表于 2012-5-11 00:22
汗，没注意
select 2+5+14+3+6+12+4+7+13+1 FROM DUAL;
67,这个更小，检查了没问题

写了个很笨的sql，在我的笔记本上跑了90分钟才跑出结果，而且加了N多限制条件，比如首尾必须是1和2、总和不超过67(因为手工已经验证出一个67的结果了)

with t as(select level n from dual connect by level<=18)
select t1.n,t2.n,t3.n,t4.n,t5.n,t6.n,t7.n,t8.n,t9.n,t0.n from
t t1,t t2,t t3,t t4,t t5,t t6,t t7,t t8,t t9,t t0
where t1.n+t2.n+t3.n+t4.n+t5.n+t6.n+t7.n+t8.n+t9.n+t0.n between 55 and 67
and t1.n+t2.n+t3.n>=21 and t2.n+t3.n+t4.n>=21 and t3.n+t4.n+t5.n>=21
and t4.n+t5.n+t6.n>=21 and t5.n+t6.n+t7.n>=21 and t6.n+t7.n+t8.n>=21
and t7.n+t8.n+t9.n>=21 and t8.n+t9.n+t0.n>=21 and t1.n=2
and t2.n not in (1,t1.n)
and t3.n not in (1,t1.n,t2.n)
and t4.n not in (1,t1.n,t2.n,t3.n)
and t5.n not in (1,t1.n,t2.n,t3.n,t4.n)
and t6.n not in (1,t1.n,t2.n,t3.n,t4.n,t5.n)
and t7.n not in (1,t1.n,t2.n,t3.n,t4.n,t5.n,t6.n)
and t8.n not in (1,t1.n,t2.n,t3.n,t4.n,t5.n,t6.n,t7.n)
and t9.n not in (1,t1.n,t2.n,t3.n,t4.n,t5.n,t6.n,t7.n,t8.n)
and t0.n =1
order by t1.n+t2.n+t3.n+t4.n+t5.n+t6.n+t7.n+t8.n+t9.n+t0.n asc

复制代码

得到的结果是

N N_1 N_2 N_3 N_4 N_5 N_6 N_7 N_8 N_9
2 11 8 4 12 6 3 15 5 1
2 10 9 4 12 6 3 15 5 1
2 9 10 4 12 6 3 15 5 1
2 8 11 4 12 6 3 15 5 1
2 13 6 4 11 7 3 15 5 1
2 10 9 4 11 7 3 15 5 1
2 9 10 4 11 7 3 15 5 1
2 6 13 4 11 7 3 15 5 1
2 12 7 4 10 8 3 15 5 1
2 7 12 4 10 8 3 15 5 1
2 6 13 4 10 8 3 15 5 1
2 7 12 4 8 10 3 15 5 1
2 6 13 4 8 10 3 15 5 1
2 9 10 4 7 11 3 15 5 1
2 6 13 4 7 11 3 15 5 1
2 8 11 4 6 12 3 15 5 1
2 11 8 3 12 6 4 15 5 1
2 10 9 3 12 6 4 15 5 1
2 9 10 3 12 6 4 15 5 1
2 8 11 3 12 6 4 15 5 1
2 10 9 3 11 7 4 15 5 1
2 9 10 3 11 7 4 15 5 1
2 6 13 3 11 7 4 15 5 1
2 7 12 3 10 8 4 15 5 1
2 6 13 3 10 8 4 15 5 1
2 7 12 3 8 10 4 15 5 1
2 6 13 3 8 10 4 15 5 1
2 6 13 3 7 11 4 15 5 1
2 12 7 4 13 5 3 14 6 1
2 11 8 4 13 5 3 14 6 1
2 10 9 4 13 5 3 14 6 1
2 9 10 4 13 5 3 14 6 1
2 8 11 4 13 5 3 14 6 1
2 7 12 4 13 5 3 14 6 1
2 10 9 4 11 7 3 14 6 1
2 9 10 4 11 7 3 14 6 1
2 12 7 4 10 8 3 14 6 1
2 7 12 4 10 8 3 14 6 1
2 7 12 4 8 10 3 14 6 1
2 9 10 4 7 11 3 14 6 1
2 7 12 4 5 13 3 14 6 1
2 12 7 3 13 5 4 14 6 1
2 11 8 3 13 5 4 14 6 1
2 10 9 3 13 5 4 14 6 1
2 9 10 3 13 5 4 14 6 1
2 8 11 3 13 5 4 14 6 1
2 7 12 3 13 5 4 14 6 1
2 10 9 3 11 7 4 14 6 1
2 9 10 3 11 7 4 14 6 1
2 7 12 3 10 8 4 14 6 1
2 7 12 3 8 10 4 14 6 1
2 14 5 4 12 6 3 13 7 1
2 11 8 4 12 6 3 13 7 1
2 10 9 4 12 6 3 13 7 1
2 9 10 4 12 6 3 13 7 1
2 8 11 4 12 6 3 13 7 1
2 5 14 4 12 6 3 13 7 1
2 5 14 4 10 8 3 13 7 1
2 5 14 4 8 10 3 13 7 1
2 8 11 4 6 12 3 13 7 1
2 5 14 4 6 12 3 13 7 1
2 11 8 3 12 6 4 13 7 1
2 10 9 3 12 6 4 13 7 1
2 9 10 3 12 6 4 13 7 1
2 8 11 3 12 6 4 13 7 1
2 5 14 3 12 6 4 13 7 1
2 5 14 3 10 8 4 13 7 1
2 5 14 3 8 10 4 13 7 1
2 5 14 3 6 12 4 13 7 1
2 13 6 4 11 7 3 12 8 1
2 10 9 4 11 7 3 12 8 1
2 9 10 4 11 7 3 12 8 1
2 6 13 4 11 7 3 12 8 1
2 5 14 4 11 7 3 12 8 1
2 9 10 4 7 11 3 12 8 1
2 6 13 4 7 11 3 12 8 1
2 5 14 4 7 11 3 12 8 1
2 10 9 3 13 5 4 12 8 1
2 9 10 3 13 5 4 12 8 1
2 10 9 3 11 7 4 12 8 1
2 9 10 3 11 7 4 12 8 1
2 6 13 3 11 7 4 12 8 1
2 5 14 3 11 7 4 12 8 1
2 6 13 3 7 11 4 12 8 1
2 5 14 3 7 11 4 12 8 1
2 12 7 4 10 8 3 11 9 1
2 7 12 4 10 8 3 11 9 1
2 6 13 4 10 8 3 11 9 1
2 5 14 4 10 8 3 11 9 1
2 7 12 4 8 10 3 11 9 1
2 6 13 4 8 10 3 11 9 1
2 5 14 4 8 10 3 11 9 1
2 5 14 4 6 12 3 11 9 1
2 7 12 4 5 13 3 11 9 1
2 5 14 3 12 6 4 11 9 1
2 7 12 3 10 8 4 11 9 1
2 6 13 3 10 8 4 11 9 1
2 5 14 3 10 8 4 11 9 1
2 7 12 3 8 10 4 11 9 1
2 6 13 3 8 10 4 11 9 1
2 5 14 3 8 10 4 11 9 1
2 5 14 3 6 12 4 11 9 1
2 7 12 4 8 10 3 9 11 1
2 6 13 4 8 10 3 9 11 1
2 5 14 4 8 10 3 9 11 1
2 5 14 4 6 12 3 9 11 1
2 7 12 4 5 13 3 9 11 1
2 7 12 3 10 8 4 9 11 1
2 6 13 3 10 8 4 9 11 1
2 5 14 3 10 8 4 9 11 1
2 7 12 3 8 10 4 9 11 1
2 6 13 3 8 10 4 9 11 1
2 5 14 3 8 10 4 9 11 1
2 5 14 3 6 12 4 9 11 1
2 9 10 4 7 11 3 8 12 1
2 6 13 4 7 11 3 8 12 1
2 5 14 4 7 11 3 8 12 1
2 6 13 3 7 11 4 8 12 1
2 5 14 3 7 11 4 8 12 1
2 8 11 4 6 12 3 7 13 1
2 5 14 4 6 12 3 7 13 1
2 5 14 3 8 10 4 7 13 1
2 5 14 3 6 12 4 7 13 1
2 7 12 4 5 13 3 6 14 1

复制代码

总共124行

第一行的各数之和是67，说明最小应该是67

newkid · 发表于 2012-5-12 04:30

lastwinner 发表于 2012-5-12 03:10
你这个办法明显比我的那个次数要多，例如29层不碎30层才碎

那如果12层碎11层不碎呢？
很难找到一种方法每层都最小的。

lastwinner · 发表于 2012-5-12 04:31

lastwinner 发表于 2012-5-12 01:23
哈哈，你也说蛋疼啊
我想到的是三分，12层为一个单位，先在1~12层测，然后在1/3处，即第4层抛，若没碎， ...

由我这个思路，得出一个计算式子
找出一个合适的自然数N，使得36/N＋N/2取最小，那么p=greatest((36/N+ceil(N/2)-1), 36/N-1+N-1)就是题目所求
所以,当N可以被36除尽时，N应当是6，最多10次 (和之前一样，要考虑36层还不碎的情况)
当31~36层才碎，那么次数最多是36/N+ceil(N/2)-1=8（到了30还不碎，那么开始二分，试验33，碎了，31/32逐个试验，最倒霉8次；要不碎，测35，无论碎了与否，均再测一次便可得知，也是8次）
当18/24都不碎，30层才碎，那么次数最多就是29层还不碎，就是36/N-1+N-1=10次

36除以N要是除不尽，那么还要特殊处理一下，睡了，起来再说

newkid · 发表于 2012-5-12 04:33

lastwinner 发表于 2012-5-12 03:57
写了个很笨的sql，在我的笔记本上跑了90分钟才跑出结果，而且加了N多限制条件，比如首尾必须是1和2、总和 ...

只计算18以内的是什么道理？一定包含1，2又是什么道理？
OO还有个BETWEEN 21 AND 24的条件，也没说清楚什么道理。

lastwinner · 发表于 2012-5-12 04:35

newkid 发表于 2012-5-12 04:30
那如果12层碎11层不碎呢？
很难找到一种方法每层都最小的。

看117楼
我之前实际上是分成9份，所以，12层碎，第一只蛋第三次碎了
然后第二只蛋从9开始试验，9/10/11，要3次
所以总共是6次，不过还是比不上我新发现的规律少

lastwinner · 发表于 2012-5-12 04:39

newkid 发表于 2012-5-12 04:33
只计算18以内的是什么道理？一定包含1，2又是什么道理？
OO还有个BETWEEN 21 AND 24的条件，也没说清楚什 ...

三个自然数的值要达到21，除去1和2，最多还需要18
而一个很自然的数列6~15排成一列，肯定满足题设连续三个数的和大于21
所以，最大的数，就是18了

〇〇的24没有道理，21是对的，和至少要到21嘛

newkid · 发表于 2012-5-12 05:06

lastwinner 发表于 2012-5-12 04:31
由我这个思路，得出一个计算式子
找出一个合适的自然数N，使得36/N＋N/2取最小，那么p=greatest((36/N+c ...

题目要求是比较各种方法的最大次数？不是要求每层都最小？
确实这个要求看起来比较合理。

[精华] 趣题, 第8道来了。