今天去面試IC設計軟體工程師被打爆的題目 - 工程師

※ 引述《irishcafee (愛爾蘭咖啡)》之銘言：
: 哈一堆鄉民說不難，那鄉民幫忙解吧!!
: 稍微喵了一下，要答得好確實需要觀念和一點實力。
: 但是面試考這種大概要測驗你的反應吧，答不出來只要給出想法應該ok。
: 高中有在比競賽或是大學有在比ACM的，第二題大概解答就直接背出來了。
: C43取6 + C43取5 x C6取1 + C43取4 x C6取2 +1 = 13723193
: 我很弱，才工作三年，剩下的就交給鄉民高手嚕!!


純討論 說一下我的想法
因為題目是說"最少"要買幾張就可以中3個號碼以上
直覺上不用買這麼多

如果我們把題目稍微簡化一點
假設是6個號碼(1~6)任選3個開獎 只要2個與開獎號碼相同即有獎
一樣是求最少要買幾張可以保證中獎

如果按照上面的算法應該是:
C3取0 x C3取3 + C3取1 x C3取2 + 1 = 11

但實際
你只需要買2張
123
456
就可以保證中獎了

為什麼呢
因為開獎的第一個號碼必定落在上面兩張其中一張
如果要不中獎的話
那麼接下來的號碼就不能開出那一張剩下的兩個號碼
但這代表著
剩下要開出的兩個號碼必定會落在第二張
所以第二張必中獎


所以這題應該可以買更少的張數來保證中獎吧?

歡迎討論




--