现有一完全的P2P共享协议，每次两个节点通讯后都能获取对方已_阿里巴巴笔试题

推荐

miaoha

答案:c

如上图1所示，假设有5个节点，按连线1、2、3、4通讯之后，节点4和5就掌握了所有节点的信息，之后，1、2、3节点只需跟4或5任一节点通讯一次即连线5、6、7就可保证每个节点都知道所有节点的信息，总的通讯次数是(n-1)+(n-2)=2n-3次。
如果将所有节点分成两组，如图2所示，两组中的节点分别按连线1-8顺序通讯之后，节点4和5就掌握了1-5所有节点的信息，节点9和0就掌握了6-0所有节点的信息，再按连线9、10通讯之后，节点4、5、9、0就掌握了1-0所有节点的信息，剩下的节点只需跟4、5、9、0任一节点通讯一次就可保证每个节点知道所有节点信息，和图1相比，多了9和10两次通讯，总的通讯次数是(2n1-3)+(2n2-3)+2=2n-4次(n1和n2分别表示分组中元素个数)。
分3组的情况是(2n1-3)+(2n2-3)+(2n3-3)+6=2n-3次
分4组的情况是(2n1-3)+(2n2-3)+(2n3-3)+(2n4-3)+8=2n-4次

编辑于 2015-02-04 17:15:29 回复(13)

菜鸟ding

c

发表于 2023-09-21 21:47:24 回复(0)

花村橘喵京

2n-4

发表于 2020-06-30 12:35:17 回复(0)

vayne_Huang

编辑于 2017-08-21 16:41:23 回复(0)

多多_

好难这个

发表于 2015-12-13 00:47:52 回复(0)

张佃鹏

假设有n个节点，直观的按照1-2-···-(n-1)-n传播顺序，最后n-1和n获得了所有节点的信息，然后取其中任一节点与1、2、···、n-2这些节点交换信息，即可让所有节点获得所有信息，这样通讯次数=n-1+n-2=2n-3；

如果分成两个组呢，假设两个组的节点个数分别为n1和n2，则每个组首先需要按序传播信息N1=n1-1+n2-1，然后第一组最后两个节点和第二组的最后两个节点就获得了各自组的所有信息，这四个节点两两交换信息，需要N2=2次，则这四个节点获得了两个组所有节点信息，然后取任一节点与每个组剩下的节点（分别是n1-2,n2-2）交换信息N3=n1-2+n2-2，则通讯任务完成，总共通讯次数N=N1+N2+N3=2n1-3+2n2-3+2=2(n1+n2)-4=2n-4;

如果分成三个组，同样的分析N=2n1-3+2n2-3+2n3-3+6=2n-3，其中6表示三个组的最后两个节点交换信息需要6次；

那如果分的组数更多呢，假设分为g组(g>=4)，同上分析N=2n-3g+M，其中M表示g个组的最后两个节点交换信息所需要的最少次数。假设把这些点的通讯按照两个组的模式来处理，则M=2*(2g-4)，N=2n+g-8>=2n-4。假设按三个组的模式来处理，则M=2*(2g-3)，N=2n+g-6>=2n-2，可见它们都是大于等于2n-4，而且随着g的变大通讯次数也会增多。

所以最优的情况就是在分成两个组或者四个组的时候取到，最优情况下通讯次数为2n-4.

发表于 2015-08-12 10:30:30 回复(10)

传琦

答案是C

两次操作：

1、取其中一个元素与其他的元素进行通讯，最后会发现17个中有2个已经获得了所有的信息；16次

2、最少的通讯次数，就是剩余的14个与其中已获得全部信息的2个进行通讯。14次

因此一共至少需要30次

编辑于 2016-06-21 10:52:36 回复(15)

丰乐

第一步：两两配对，8次
第二步：从第一步中的抽出8个，在进行两两配对，4次
第三步：从第二步中的四个两两配对，2次
第四步：从第三步中的两个两两配对，1次，这一步执行完毕后，有两个节点已经拥有全部信息
第五步：第四步的两个和其他两个相互配对，2次，此时，4个完成
第六步：这四个和剩下的4个配对，4此，此时，8个完成
第七部：这8个和剩下的8个配对，此时16个完成
第八步：和最后一个配对，此时17个完成
总计：8+4+2+1+2+4+8+1=15

发表于 2017-08-07 10:25:22 回复(10)

tutuqie

举例来说：1，2，3，4，5五个点进行共享，从左到右1和2、2和3。。4和5，最终4和5获得了五个点全部的信息。若要其余点也同样获得，则只需依次进行4和3、3和2、2和1的信息共享。如此便有4+3=7次通讯。

综上，本题为16+15=31次通讯。

注意：问的是最少需要多少次，不要搞乱点与点交换信息的顺序。

发表于 2015-09-02 22:13:46 回复(4)

随走无涯

选择C。

公式：f(n)=2n-3 (n<=3)； f(n)=2n-4 (n>4)

求解：

多个点之间，如果想让最后一个点n知道，一定要n-1次传递，此时知道完整结果的还有点n-1。

要想让其他点（n-2个点）知道结果，需要再传递n-2次。

结果为：f(n)=n-1+n-2=2n-3

有一种特殊情况，当n>=4时，最后一次可以采用两两配对1-3可使1、3节点都知道，2-4可使2、4节点都知道。此时能够在原公式基础上再减1次。

结果为：f(n)=n-1+n-2-1 = 2n-4 (n>=4)

发表于 2019-10-22 14:43:15 回复(0)

平林新袖

将所有的结点构造一棵二叉树，其中边的数量*2就是所求。这样对吗？

发表于 2015-07-14 00:17:22 回复(0)

我喜欢雨天的清新

奇数组2n-3 偶数组2n-4 最少2n-4

发表于 2017-08-30 13:31:51 回复(0)

reyne-d

思路跟前面的解法差不多，

1. 找到一些节点，获取所有信息，这个过程中要分组，至于与3个节点一组还是4个节点一组为单位，要分类讨论。可以参考以下信息：

节点数：最小联系数

[2,1] , [3,3] , [4,4] [5,6]

2. 节点数=4时，分为4组，每组4个，

第一轮：每个绿色的节点跟他们组其他节点交换信息，绿色节点获得该组节点所有信息，（见图1），4*3=12次

第二轮：4个绿色节点跟1个橙色组成一个组，经过6轮（见图2），5个节点均获得所有信息

第三轮：4个绿色节点把信息返回，4*3=12次

最后，总次数为12 + 6 + 12 = 30次

节点数为3时（赶着吃午饭...，以后补吧~~）

发表于 2018-01-19 12:29:15 回复(2)

_立夏本夏_

首先用最直接的思路去思考，即顺序传递信息，将第1个结点信息传给第2个，然后再将第二个传递给第3个，依次传递下去，第n-1个结点将信息传递给第n个，此时已进行了n-1次传递，且n-1和n结点均有全部信息。再利用n或者n-1结点与其它n-2个结点通信即可。完成整个过程需要2n-3次通信。
如果把结点分成两部分来思考，第一个部分有n1个元素，第二个部分有n2个元素，两组分别按照第一种思路进行通信，共需要n1-1+n2-1 = n-2次通信，此时再将n1-1，n1分别与n2-1,n2进行通信，通过这2次通信后有4个结点有全部信息，只需要取任意一个有全部信息的节点与剩余的n-4个结点分别通信即可。完成整个过程需要n-2+2+n-4=2n-4次通信。
继续将结点分成三部分来思考，第一个部分有n1个元素，第二个部分有n2个元素，第三个部分有n3个元素，，三组分别按照第一种思路进行通信，共需要n1-1+n2-1 +n3-1= n-3次通信,这时还至少需要2次通信使得有两个节点获得全部信息，实际上，此时已经退化成第一种情况了，完成整个过程同样需要2n-3次通信。

综上所述，最少通信次数为2n-4次通信。

--------来源csdn社区

发表于 2020-04-26 22:02:37 回复(0)

认识你是上天注定

为啥都要分组呢，直接找出一个为主节点，然后环形构建，通信16次，主节点再与除去相邻的两个节点通信（16-2）=14次，一共通信16+14=30次不就行了(●°u°●) 」。

发表于 2021-10-19 20:20:30 回复(1)

细雨湿身

假设有n个节点，直观的按照1-2-···-(n-1)-n传播顺序，最后n-1和n获得了所有节点的信息，然后取其中任一节点与1、2、···、n-2这些节点交换信息，即可让所有节点获得所有信息，这样通讯次数=n-1+n-2=2n-3；

如果分成两个组呢，假设两个组的节点个数分别为n1和n2，则每个组首先需要按序传播信息N1=n1-1+n2-1，然后第一组最后两个节点和第二组的最后两个节点就获得了各自组的所有信息，这四个节点两两交换信息，需要N2=2次，则这四个节点获得了两个组所有节点信息，然后取任一节点与每个组剩下的节点（分别是n1-2,n2-2）交换信息N3=n1-2+n2-2，则通讯任务完成，总共通讯次数N=N1+N2+N3=2n1-3+2n2-3+2=2(n1+n2)-4=2n-4;

如果分成三个组，同样的分析N=2n1-3+2n2-3+2n3-3+6=2n-3，其中6表示三个组的最后两个节点交换信息需要6次；

那如果分的组数更多呢，假设分为g组(g>=4)，同上分析N=2n-3g+M，其中M表示g个组的最后两个节点交换信息所需要的最少次数。假设把这些点的通讯按照两个组的模式来处理，则M=2*(2g-4)，N=2n+g-8>=2n-4。假设按三个组的模式来处理，则M=2*(2g-3)，N=2n+g-6>=2n-2，可见它们都是大于等于2n-4，而且随着g的变大通讯次数也会增多。

所以最优的情况就是在分成两个组或者四个组的时候取到，最优情况下通讯次数为2n-4.

发表于 2016-09-11 16:55:08 回复(0)

嘟嘟不说谎

把整体当做一组做，得到结果一共是2*n-3次

然而

分成两组，每组是2n1-3和2n2-3，然后多出来两次通信，一共是2n-4次
同理，分成三组，但是每组最后两者之间又要相互通信，一共通行6次，所以总和2n-3次；
分成四组的时候，在分成三组的基础上再进行通信，多通信8次，总共2n-4次；
分成五组，每组之间的通信代价更加大，组越多，组之间的代价就越大，要付出2(x-1+x-2）次代价，x为组数，所以分成2组或者4组是最划算的。

发表于 2023-04-11 21:17:45 回复(1)

牛客、芒果熊

找出一个为主节点，然后环形构建，通信16次，主节点再与除去相邻的两个节点通信（16-2）=14次，一共通信16+14=30

选C

发表于 2022-11-16 10:01:57 回复(1)

我是大学生请务必给我一个offer

第一步：两两配对，8次，第17个节点没有通信
第二步：从第一步中的8组中每组抽出一个，在进行两两配对，4次
第三步：从第二步中的4组中分别抽出一个，四个两两配对，2次
第四步：从第三步中的两组中个抽出一个，两两配对，1次，这一步执行完毕后，有两个节点已经拥有除第17个节点外的全部信息
第五步：从第四步的两个节点中抽取一个与节点17通信，有两个节点（节点17和抽取出的节点）已经拥有全部信息
第六步：令节点17与剩余的15个节点通信
总计：8+4+2+1+15=30

发表于 2022-09-28 20:41:33 回复(1)

龙1111

1.分两组，分别为1-8和9-17两组。

两个小组内通信。7次后1-8中有2个节点掌握全部本小组信息，8次后9-17中有2个节点掌握全部本小组信息。此时通信了15次。

这4个节点两两配对，这4个节点掌握全部信息，此时总共17次；剩余的13个数字分别与这四个通信，总共30次。

2.分四组，分别为1-4、5-8、9-12、13-17四组。

四个小组内通信。前三个小组都是3次通信后有2个节点掌握全部本小组信息，第四个小组是4次后有2个节点掌握全部本小组信息。此时通信了13次。

4个组各挑出一个节点，这4个节点互相配对，经过4次后这4个节点掌握全部信息，此时总共17次；剩余的13个数字分别与这四个通信，总共30次。

3.分五组，就是单独挑出一个，前四组各自经过3次后出两个掌握本小组全部信息的节点，各挑一个与单独的那个一起，5个经过6次后都掌握全部信息，剩余的12个数字分别与这五个通信，4*3+6+12总共30次.

附：5个匹6次，设为1,2,3,4,5，首先1,2互换1次，其次3,4,5互换2次，3,4掌握全部信息，然后1与3,2与4匹配，这四个掌握全部信息，最后5跟一个匹配，总共是1+2+2+1=6次

发表于 2024-04-12 19:17:39 回复(0)

一个达布刘

不会

发表于 2023-03-28 08:32:41 回复(0)

现有一完全的P2P共享协议，每次两个节点通讯后都能获取对方已

然而

问题信息

热门推荐

相关试题