趣题, 第8道来了。

tree_new_bee

〇〇 发表于 2012-5-17 09:49
我的10有错？

1. f[8]=10?
   
2. 4次变成4个2
   
3. 2次变成4个4
   
4. 4次变成4个8

复制代码

2次只是变出4个4，而不是8个4.

lastwinner

newkid 发表于 2012-5-16 22:09
36层不碎有什么问题呢？用的是同样方法。
当然37层也可能不碎，这我们就不管了。

方法一样，但结论会有变化，不过也主要是文字上而不是数字上的变化

lastwinner

newkid 发表于 2012-5-16 22:03
思路很清晰！能够证明8最小吗？

不能，但是列举出的三个处理思路在寻找最小中应该很有用
再多一点总结，应该就是在一个人掌握半数信息之前，应该继续跟拥有更多不同信息的人打电话。注意这里说的是“更多”而不是“最多”，因为非常有可能合适的才是最好的

newkid

用SQL证明六人最少需要8次：

最终每人得到所有消息的状态为111111即十进制的63。
因为没有BITOR, 采用A+B-BITAND(A,B)

WITH d AS (
SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=6
)
,p AS (
SELECT d1.n n1,d2.n n2,d1.n||d2.n pair FROM d d1, d d2 WHERE d1.n<d2.n
)
,t2 AS (
SELECT '12,23' AS path
      ,'*030707081632' as bits
FROM DUAL
UNION ALL
SELECT '12,34' AS path
      ,'*030312121632' as bits
FROM DUAL
)
,t(cnt,path,bits) AS (
SELECT 3
      ,t2.path||','||p.pair
      , SUBSTR(bits,1,n1*2-1)
        ||LPAD(SUBSTR(bits,n1*2,2)+SUBSTR(bits,n2*2,2)-BITAND(SUBSTR(bits,n1*2,2),SUBSTR(bits,n2*2,2)),2,'0')
        ||SUBSTR(bits,n1*2+2,(n2-n1-1)*2)
        ||LPAD(SUBSTR(bits,n1*2,2)+SUBSTR(bits,n2*2,2)-BITAND(SUBSTR(bits,n1*2,2),SUBSTR(bits,n2*2,2)),2,'0')
        ||SUBSTR(bits,n2*2+2)
  FROM t2,p
WHERE t2.path='12,23' AND p.pair IN ('14','24','45')
       OR t2.path='12,34' AND p.pair IN ('13','15','56')
UNION ALL
SELECT cnt+1
      ,t.path||','||p.pair
      , SUBSTR(bits,1,n1*2-1)
        ||LPAD(SUBSTR(bits,n1*2,2)+SUBSTR(bits,n2*2,2)-BITAND(SUBSTR(bits,n1*2,2),SUBSTR(bits,n2*2,2)),2,'0')
        ||SUBSTR(bits,n1*2+2,(n2-n1-1)*2)
        ||LPAD(SUBSTR(bits,n1*2,2)+SUBSTR(bits,n2*2,2)-BITAND(SUBSTR(bits,n1*2,2),SUBSTR(bits,n2*2,2)),2,'0')
        ||SUBSTR(bits,n2*2+2)
  FROM t,p
WHERE SUBSTR(bits,n1*2,2)<>SUBSTR(bits,n2*2,2)
       AND cnt<8
       AND bits<>'*636363636363'
)
SELECT * FROM (
SELECT * FROM t WHERE bits='*636363636363' ORDER BY cnt
)
WHERE ROWNUM=1;

       CNT
----------
PATH
----------------------------------
BITS
----------------------------------
         8
12,34,15,46,56,14,13,12
*636363636363

跑了两分多钟，前三层还是用手工排除了拓扑等价的那些组合。

jixch

tree_new_bee 发表于 2012-5-11 14:22
周末两天外出， 把下一题也扔出来，省的大家周末太闲。

趣题5：

最少扔多少次
可不可以理解为：
在某种方案下，
如果第一层 摔坏，需要扔的次数为n1；
如果第二层 摔坏，需要扔的次数为n2；
如果第三层 摔坏，需要扔的次数为n3；
....
如果第36层 摔坏，需要扔的次数为n36；
最后n1+n2+n3+....+n36最小
然后最少次数为：（n1+n2+n3+....+n36）/36
这样理解？

newkid

jixch 发表于 2012-5-17 22:32
最少扔多少次
可不可以理解为：
在某种方案下，

不是这样，你的策略应该是：不管答案在哪层，这个策略能够保证最多不超过N次，就能把这个楼层找出来。

jixch

newkid 发表于 2012-5-17 22:50
不是这样，你的策略应该是：不管答案在哪层，这个策略能够保证最多不超过N次，就能把这个楼层找出来。

那么这题的意思就是：
每个策略都会有一个N值
在所有的策略中，最小的N值是多少？

newkid

jixch 发表于 2012-5-17 22:59
那么这题的意思就是：
每个策略都会有一个N值
在所有的策略中，最小的N值是多少？

就是这么理解的。

jixch

newkid 发表于 2012-5-17 23:43
就是这么理解的。

设定36层时
在策略1下，
如果第一层 摔坏，需要扔的次数为n1；
如果第二层 摔坏，需要扔的次数为n2；
如果第三层 摔坏，需要扔的次数为n3；
....
如果第36层 摔坏，需要扔的次数为n36；
最后n1、n2、n3、....、n36中的最大值为M1
M1即为该策略的N值
所有策略的N值分别为M1、M2、M3、M4....
那么M1、M2、M3、M4....中的最小值K即为所求最少扔多少次

先设定1层也可能会摔碎，那么会有如下结论：
如果是1层，最少扔1次：N=1
如果是2层，最少扔2次（策略：先测试2楼） ：N=2
如果是3层，最少扔2次（策略：先测试2楼） ：N=2
如果是4层，最少扔3次（策略：先测试3楼：碎了的话只剩下一个蛋，从1楼开始往上测试，最多3次；没碎，上面还剩1层，按1层的策略测试，1次，一共最多2次；）：N=3
如果是5层，最少扔3次（策略：先测试3楼：碎了的话只剩下一个蛋，从1楼开始往上测试，最多3次；没碎，上面还剩2层，按2层的策略测试，2次，一共最多3次；）：N=3
如果是6层，最少扔3次（策略：先测试3楼：碎了的话只剩下一个蛋，从1楼开始往上测试，最多3次；没碎，上面还剩3层，按3层的策略测试，2次，一共最多3次；）：N=3
如果是7层，最少扔4次（策略：先测试4楼：碎了的话只剩下一个蛋，从1楼开始往上测试，最多4次；没碎，上面还剩3层，按3层的策略测试，2次，一共最多3次；）：N=4
如果是8层，最少扔4次（策略：先测试4楼：碎了的话只剩下一个蛋，从1楼开始往上测试，最多4次；没碎，上面还剩4层，按4层的策略测试，3次，一共最多4次；）：N=4
如果是9层，最少扔4次（策略：先测试4楼：碎了的话只剩下一个蛋，从1楼开始往上测试，最多4次；没碎，上面还剩5层，按5层的策略测试，3次，一共最多4次；）：N=4
如果是10层，最少扔4次（策略：先测试4楼：碎了的话只剩下一个蛋，从1楼开始往上测试，最多4次；没碎，上面还剩6层，按6层的策略测试，3次，一共最多4次；）：N=4
如果是11层，最少扔5次（策略：先测试5楼：碎了的话只剩下一个蛋，从1楼开始往上测试，最多5次；没碎，上面还剩6层，按6层的策略测试，3次，一共最多4次；）：N=5
依此类推
策略：
将楼层层数K与 1+2+3+....+n 进行比较
K <= 1+2+3+....+n 情况下的最小的 n 值
第一次在第n层上测试
如果碎了，只剩下一个蛋，那么想测出楼层就必须从1层依次往上测，直到n-1层，最多n次
如果没有碎，设定n+1层为第1层，剩下的楼层再按上面的逻辑测试

36层策略：
36 <= 1+2+3+4+5+6+7+8
1. n最小值为8，先在第8层测试：
    a.碎了：从1层依次往上测试，直到第7层
    b.没碎：上面有9至36层，一共28层，28 <= 1+2+3+4+5+6+7  ，此时n最小值为7，再次执行第1步

分析完了
睡觉~~~~

lastwinner

newkid 发表于 2012-5-17 22:24
用SQL证明六人最少需要8次：

最终每人得到所有消息的状态为111111即十进制的63。

跑得好辛苦啊，呵呵，我突然有找出推广到n时的最佳方式并证明之的思路了。整理一下思路马上写出来