趣题, 第8道来了。

〇〇

〇〇 发表于 2012-5-16 16:59
1个人至少打n-1次才能知道n个消息，再打n-1次告诉其他人所有消息，所以最大2n-2

多算一个，其实他跟第n人打电话时就有了所有消息，所以不用再打给第n人

hudingchen

tree_new_bee 发表于 2012-5-16 16:58
前面总结的f(n)是错的。
比如f(4)5, 应该只要4次就可以了。
比如abcd四人， ab打一次，cd打一次， ac打 ...

恩，你说的对，我再考虑考虑啊

〇〇

hudingchen 发表于 2012-5-16 16:31
趣题6：
n           f(n)
1            0

4个人打4次电话就够了
人（消息）
初始化：1(1) 2(2) 3（3） 4（4）
第1个电话1打给2
地2个电话3打给4
状态 1(12) 2(12) 3(34) 4(34)
第3个电话1打给3
地4个电话2打给4
状态 1(1234) 2(1234) 3(3412) 4(3412)

〇〇

第6题分析
一开始6个消息，最后36个消息
一个电话只能使2个人持有的消息加倍，如：1打给2 总消息即2*2+4=8
要尽快完成36，必须让加倍的是消息多的人

tree_new_bee

第5题，我的方法是靠朴素的直觉：
假设第一个蛋测试m1,m1+m2,...层，那么如果第一次蛋破后要试m1-1次， 总次数就是1+m1-1=m1次
第二次蛋破后要试m2-1次， 总次数就是2+m2-1次
...
为了要让总次数最少， 应在无论第一个蛋什么时候破都让总测试次数尽量一样(相等或者近似)
所以应m1 = m2+1 = m3+2=...,  即m2=m1-1, m3=m1-2....
这样, m1+ (m1-1) + (m1-2) + ... 1 = 36
得到：m1*(m1+1) /2 = 36
m1=8

推广到N,则是 m1*(m1+1）/2 = N
解得m1 = Sqrt(2N +0.25) - 0.25
向上取整即可。

hudingchen

猜测应该分两种情况，
1)当人数n是2的k次幂.
2)当人数n不是2的k次幂.
但需要证明 晚上回家研究下

lugionline

这样？反正不会比这个大


f[1] = 0
f[2k] = k + 2f[k]
f[2k + 1] = k + 2f[k + 1]

f[6] = 3 + 2 f[3] = 9

〇〇

lugionline 发表于 2012-5-16 18:56
这样？反正不会比这个大

1.12* 12* 3 4 5 6
2.12 12 34* 34* 5 6
3.12 12 34 34 56* 56*
4.1234* 12 1234* 34 56 56
5.1234 1234* 1234 1234* 56 56
6 123456* 1234 1234 1234 123456* 56
7 123456 123456* 1234 1234 123456 123456*
8 123456 123456* 123456* 1234 123456 123456
9 123456 123456* 123456 123456* 123456 123456

〇〇

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

jixch

F[6]好像可以等于8啊
1*2  3*4  5*6 结果：12   12    34   34   56   56
1*3  4*5         结果：1234    12    1234    3456    3456  56
1*6  2*4  3*5 结果：123456      123456    123456    123456    123456    123456
一共8次