假定n个人各恰好知道一个消息，而所有n个消息都不相同，每次“A”打电话给“B”，“A”都把所知道的一切告诉“B”，而“B”不告诉“A”什么消息．为了使各人都知道一切消息．求所有

Question

假定n个人各恰好知道一个消息，而所有n个消息都不相同，每次“A”打电话给“B”，“A”都把所知道的一切告诉“B”，而“B”不告诉“A”什么消息．为了使各人都知道一切消息．求所有需要两人之间通话的最少次数．证明你的答案是正确的．

Answer 1

需要两人之间通话的最少次数=(3n)/(2)-3（次）．
给n个人分别编号1～n，他们知道的消息也编上相同的号码．
（1）2～(n)/(2)号每人给1号打1次电话，共(n)/(2)-1次，1，(n)/(2)号得到1--(n)/(2)号消息．
（2）1号和(n+1)/(2)号通1次电话，(n)/(2)号和n号通1次电话，这时1，(n)/(2)，(n+1)/(2)，n号这4个人都知道了1-n号消息．
（3）2～(n)/(2)-1号，(n+1)/(2)～n-1号，每人与1号（或者(n)/(2)，(n+1)/(2)，n号中的任意1人）通1次话，这n-4人也全知道了1～n号消息．
 这个方案打电话次数一共是（(n)/(2)-1）+2+n-4=(3n)/(2)-3（次）．