※ 引述《jknm0510a (Kang)》之銘言：
: 1. Show that at least 19 cables are needed for connecting eight computers to
: four printers such that four computers can directly access four different
: printer at the same time.
這題意思是有八台電腦要和四台印表機連接，
假若同一時間有四個人要印文件，請問至少需要設置多少連接線，
讓這四個人可以同時使用四台不同的電腦列印文件(分別從四台印表機列印出來)。
可是我算出來答案是20條，也不太清楚到底是不是我看錯題目了
方法：
第一步：
先連[1]->(1)，[2]->2，[3]->(3)，[4]->(4)
電腦 [1] [2] [3] [4] [5] [6] [7] [8]
| | | |
| | | |
| | | |
印表機 (1) (2) (3) (4)
此時有4條連接線了
第二步：
剩下的電腦要連到全部的印表機，也就是
[5]->(1)，[5]->(2)，[5]->(3)，[5]->(4)；
[6]->(1)，[6]->(2)，[6]->(3)，[6]->(4)；
[7]->(1)，[7]->(2)，[7]->(3)，[7]->(4)；
[8]->(1)，[8]->(2)，[8]->(3)，[8]->(4)。
此時有16條連接線。
第三步：
很明顯地，4+16=20條連接線可以滿足題意。
第四步：
要說明最少需要20條，先假設如果有19條的話
這意味著至少有一台印表機連接到四台電腦(或者更少)，因為19/4 < 5
不失一般性，假設連接到四台電腦的印表機為(1)，其連到電腦[1]、[2]、[3]和[4]
電腦 [1] [2] [3] [4] [5] [6] [7] [8]
\ | / /
\ | / /
\| | /
印表機 (1) (2) (3) (4)
現在剛好有四個人分別到[5]、[6]、[7]、[8]要印文件，可是卻只有三台印表機可以使用
故得19條連接線是不夠的，所以20條是答案。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.64.76.237