应该是图论算法问题吧_数学吧

数学吧关注：939,891贴子：9,242,761

n个人，每人手里一份信息，两个人之间通一次电话，就会将两个人手里的信息全部交换。例如A手里有3份，B手里有5份不一样的，AB通话之后两人手里都有8份。最少要多少次电话才能让所有人都有n份信息
搞计算机的学弟问我的，当n>3时给了一个2n-4,但不保证2n-4是最小

送TA礼物

1楼2009-01-19 23:38回复

2n-4都有算法了，2n纯属开玩笑。
abcd4个人，所有其他人和a通话，共n-4次，然后ab,cd,ac,bd4次通话之后abcd4个人知道所有信息，共4次,然后a再和其他所有人通话，共n-4次。故总数为:n-4+4+n-4=2n-4

3楼2009-01-20 00:01

不感兴趣

开通SVIP免广告

没看懂，什么N个？语文不好，说明白点好吗？

5楼2009-01-20 00:25

问题是怎么证明4个人向其余N-4个人传播,至少N-4次，如果有两个人手里信息正好互补，一沟通不就又出来了2个N信息的？这样就少一次。

7楼2009-01-20 14:43

下载贴吧APP
看高清直播、视频！

贴吧热议榜

发表回复

内容:

使用签名档查看全部

发表

保存至快速回贴