助教，讓我問個問題，這題(99)的 cable 到底是什麼呢？ 據我認為：
假設一個 computer 和 一個 printer 間只能連結一個cable(一台computer不會用兩條以上的線連結到同一個printer)。
100台computer和20台printer，要保證有20台computer連結到所有(20)台printer，應當：
先將每台computer都連接19台printer，接著再任給20條，必可保證必定存在20台computer連結到所有printer，其他80台連接19台printer。需要： 100*19+20 = 1920，與解答不同。
煩請解惑。
4 則留言:
cable就是連線, 這題題目是要求要"任取"20台電腦, 都可以access到20台printer, 不是存在20台就可以了, 因為題目問最少要幾條cable, 所以如果你求出來的值大於解答給的, 顯然會太多
這題比較難, 想法大致上是這樣: 是先讓20台用20條cable連到20台不同的printer (來達到盡量省), 但剩下的80台就都要連的滿滿的, 而這個方法共需20+80*20=1620條cable, 並且這個值確實是最小值, 因為如果只有1619, 則不可能每台電腦都連到至少81台電腦 (因為20*81 > 1619), 也就是說必存在一台printer x連到最多80台電腦, 那麼取20台不與 x 相連的電腦, 那20台電腦最多就只會與19台printer相鄰
任取20台電腦，每台電腦都可以access到20台printer嗎？ 還是只要加起來可以access20台printer就好了呢？
例如取一開始的那20台電腦，他們每台都只連到一台printer，這樣不符合題目要求(題目說都要連到20台printer)
加起來可以access 20台printer就好
了解了，看來我英文還要加強。感謝助教
張貼留言