某個村莊中,每天晚上人們便成對地聚集在一起閒談村裡的事,在每次交談中,每個人都將其所知的事告訴對方,請問最少經過幾次交談後,村裡每個人都知道所有消息?
2006-12-26 12:49:29 · 4 個解答 · 發問者 Louis 5 in 教育與參考 ➔ 其他：教育
不是,其實我也在解題,不過還沒想到很合理的答案,突然覺得邏輯思考很難…
2006-12-26 12:55:35 · update #1
在每次交談中，每個人都將其所知的事告訴對方，假設每天每人同時間開始，同時間結束，並與新的交談對象開始交談。
第一次交談後，我有2個人的資訊，我的和對方的。
第二次交談後，我有4個人的資訊，我＋第一個和我交談的＋第二個人＆和他之前交談的。
第三次交談後，我有8個人的資訊，我已有的４人資訊＋他有的４人資訊。
第四次交談後，我有１６個人的資訊，我已有的８人資訊＋他有的８人資訊。
‧
‧
‧
以此類推，５次就是２的５次方＝３２人，６次就是２的６次方＝６４人，
如果村民的人數＝２的Ｎ次方，Ｎ次交談後，村裡每個人都知道所有消息。
結論：最少交談Ｎ次
２的（Ｎ－１）次方＜村民數＜＝２的Ｎ次方
但是如果村民不在同時間開始，同時間結束，並與新的對象交談，計算方式就更複雜了。
2006-12-28 07:00:08 · answer #1 · answered by 文文 3 · 0⤊ 0⤋
X(X-1)=答案 , X是全部的村人,每個人減掉自己再乘上全部的村人就是答案了... ...
應該是吧!
如果是另類答案要讓我知道喲~
2007-01-07 03:09:03 · answer #2 · answered by 光頭 2 · 0⤊ 0⤋
簡單的解答是 Log2(X), X 為村莊的人數
方法如下，假設村民共有8人
1. 先將村民編號，1....8
2. 第一天 1和2交談，3和4交談 ....
3. 第二天 12找34談，56找78談 .... 同組內的順序不重要
4. 第四天 1234找5678談 ← 所有訊息交換完成
證明
1. 由於村民是成對交換「資訊」，所以最快的「資訊」成長率就是兩倍.
2. 本方法取得的「資訊」以2的倍數向上增加，而且增加的「資訊」不會重複，所以是最有效率的方法。至於其他的方法，只要有觀察到「資訊」重複的狀況，自然就不是最佳的方法。
PS. 使用其他的方式，可能也會有一樣快速的結果。前提仍舊是「不能重複」，可以想想看有什麼不同的作法。
2006-12-28 09:29:25 · answer #3 · answered by Zarathustra 7 · 0⤊ 0⤋
這是在考我們嗎?
我的答案是@@"一次吧......
答案對嗎??!!
對了要跟我講唷!!
2006-12-26 12:54:04 · answer #4 · answered by 玉欣 1 · 0⤊ 0⤋