趣题, 第8道来了。

lastwinner

jixch 发表于 2012-5-18 01:28
设定36层时
在策略1下，
如果第一层 摔坏，需要扔的次数为n1；

嗯，分析正确，你可以解出K和n的关系的，可以参考我在141楼的分析

newkid

lastwinner 发表于 2012-5-18 01:29
跑得好辛苦啊，呵呵，我突然有找出推广到n时的最佳方式并证明之的思路了。整理一下思路马上写出来

我也想了一个，有希望用SQL实现，但只是猜测没有证明。

lastwinner

lastwinner 发表于 2012-5-18 01:29
跑得好辛苦啊，呵呵，我突然有找出推广到n时的最佳方式并证明之的思路了。整理一下思路马上写出来

对于n人，最佳方式的通话次数肯定不会超过这种策略：先让两人知晓所有的，然后剩下的人都与这两人通话来获知所有的消息。
在这种策略里，要让两人知晓所有的消息，需通话的总次数为n-1次，此时有2人知晓了所有消息，必然还有2人知晓了完全互补的消息，这2人再通话一次，便可获知所有的消息，而对于剩下的人，由于两两都无法做到完全互补，根据我166楼的思想，两两若不能完全互补，倒不如直接跟知晓所有信息的人直接通话。虽然166楼里没有完全肯定，但现在可以肯定了，因为n个人通过n-1次通话只能让两个人知晓所有信息，当n越大，投入产出比就显得越寒碜，当已经有人知晓了所有信息，并且剩余人知晓的信息都不能做到完全互补，那么他们直接与已知晓所有信息的人直接通话，仅1次就可以知道所有信息，还节省电话费，何乐而不为？于是乎，我们就得出了n个人知晓所有信息所需要的最少通话次数f(n)的表达式(n>=2)：
f(n)=
{
  1, n=2
  n, n in (3,4)
  2*n-4, n>=5
}

上面推理的过程也证明了这就是最少的次数。

lastwinner

newkid 发表于 2012-5-18 01:53
我也想了一个，有希望用SQL实现，但只是猜测没有证明。

还是逻辑处理比较靠谱一点，sql穷举太不靠谱了

newkid

lastwinner 发表于 2012-5-18 01:56
对于n人，最佳方式的通话次数肯定不会超过这种策略：先让两人知晓所有的，然后剩下的人都与这两人通话来获 ...

这不就是OO的方法？
一时也看不出有什么毛病。

tree_new_bee

lastwinner 发表于 2012-5-18 01:56
对于n人，最佳方式的通话次数肯定不会超过这种策略：先让两人知晓所有的，然后剩下的人都与这两人通话来获 ...

2n-4 (n>=5， 实际上n>=4即可) 我看到过这个结论(但没证明)，应该是对的。

tree_new_bee

newkid 发表于 2012-5-18 03:38
这不就是OO的方法？
一时也看不出有什么毛病。

野花与OO的区别就在于，在让两个人获得所有消息的过程中，野花会尽量制造有另外两个人形成互补的机会。
只要产生了一对互补的，就省了一次。

而OO的方案是2n-3次， 其实与2n-4次也就只差这一次而已。

tree_new_bee

这样明确的策略可以这样：
1. 第一个人与2.. n-2通话
2. 然后n-1与n互打通话 (1与n 和 n-2与n-1 分别是互补的)
3. 1与n 通话
4. n-2与n-1通话
5. 1与2..n-3个人通话

总的次数即： (n-3) + 1 + 1 + 1 + (n-4) = 2n -4

lastwinner

tree_new_bee 发表于 2012-5-18 10:19
2n-4 (n>=5， 实际上n>=4即可) 我看到过这个结论(但没证明)，应该是对的。

多打点字我大概能完成90%的证明，比较麻烦的有两处：
1/如何证明对于n，最少需要n－1次才能让两人知晓所有信息。n为2的整数次幂时比较好说明，而不是的时候我觉得有点绕。
2/后续需要证明除了能直接互补的两人之外，其他人直接与知晓全信息的通话比两两互补的通话再知晓全部信息要盛通话次数，这个应该不难证明，不过说起来我也觉得有点绕。

lastwinner

tree_new_bee 发表于 2012-5-18 10:22
野花与OO的区别就在于，在让两个人获得所有消息的过程中，野花会尽量制造有另外两个人形成互补的机会。
...

没错，原来我还认为〇〇的方法很浪费次数，后来才发现其实也不怎么浪费次数

其实这个题要改装一下就更有一次
6个人（n个人），每轮每个人只能与其他人中的一个通话一次，无论知晓信息的多少，通话总需要耗时1分钟，但一轮通话结束后，双飞都需要歇息5分钟（n-1分钟）方能与其他人开始下一轮通话，要让所有人都知道所有消息，最少需要耗时多少分钟？