Re: [請益] 今天去面試IC設計軟體工程師被打爆的題目

看板Tech_Job作者qllvv (百事檸檬可樂兒)時間10年前 (2013/11/17 00:28)推噓3(3推 0噓 4→)

留言7則, 6人參與討論串6/18 (看更多)

小弟工作三年目前只想到一個上界耶說不定還可以更少一點我的想法是取的張數 <= C24取3 + (C25取3-C24取3)/2 = 2162張理由是這樣把49個號碼分成兩群, 一群25張第二群24張. PigeonHole principle告訴我們至少會有一群有中三個數字所以買的時候請買 1, 2, 3, 26, 27, 28 (第一群的第一種組合+第二群的第一種組合) ...一直到第一群的第C24取3種組合+第二群的第C24取3種組合由於C25取3>=C24取3所以會有一些組合數沒有對應到... 那最簡單的就是兩兩組合買成一張, 因此還需要 (C25取3-C24取3)/2 應該還有浪費的啦...要再研究一下@@ ※ 引述《irishcafee (愛爾蘭咖啡)》之銘言： : 你的想法是對的!!只是你是從自選號碼的角度去思考。 : 要保證中獎應該是我的答案沒錯!! : 因為高中比競賽和大學練ACM都有算到這一題。 : ※ 引述《ejnfu ((-. .-)b)》之銘言： : : 純討論說一下我的想法 : : 因為題目是說"最少"要買幾張就可以中3個號碼以上 : : 直覺上不用買這麼多 : : 如果我們把題目稍微簡化一點 : : 假設是6個號碼(1~6)任選3個開獎只要2個與開獎號碼相同即有獎 : : 一樣是求最少要買幾張可以保證中獎 : : 如果按照上面的算法應該是: : : C3取0 x C3取3 + C3取1 x C3取2 + 1 = 11 : : 但實際 : : 你只需要買2張 : : 123 : : 456 : : 就可以保證中獎了 : : 為什麼呢 : : 因為開獎的第一個號碼必定落在上面兩張其中一張 : : 如果要不中獎的話 : : 那麼接下來的號碼就不能開出那一張剩下的兩個號碼 : : 但這代表著 : : 剩下要開出的兩個號碼必定會落在第二張 : : 所以第二張必中獎 : : 所以這題應該可以買更少的張數來保證中獎吧? : : 歡迎討論 -- 夫兵者不祥之器物或惡之故有道者不處君子居則貴左用兵則貴右兵者不祥之器非君子之器不得已而用之恬淡為上勝而不美而美之者是樂殺人夫樂殺人者則不可得志於天下矣吉事尚左凶事尚右偏將軍居左上將軍居右言以喪禮處之殺人wretch.twbbs.org勝以喪禮處之道常無名樸雖小天下莫能臣侯王若能守之萬物將自賓天地相合以降甘露民莫之令而自均始制有名名亦既有夫亦將知止知止可以不殆qllvv.Dorm12.NCTU.edu.tw海 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.32.140.248

→

qllvv

11/17 00:35, , 1^F

11/17 00:35, 1^F

推

Dsman

11/17 00:47, , 2^F

11/17 00:47, 2^F

推

pasta57

11/19 20:04, , 3^F

11/19 20:04, 3^F