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

看板Tech_Job作者 (楓霧)時間10年前 (2013/11/20 20:15), 編輯推噓10(10推 0噓 15→)
留言25則, 15人參與, 最新討論串10/18 (看更多)
: (2)大樂透的規則是 49 個號碼當中，取 6 個號碼開獎；只要彩券有 3 個以上的號碼與 : 開獎結果相同，就是中獎。依此規則請問： : a. 最少需買幾張才可以保證中一張？ : b. 概述如何以程式驗證 a.的答案。 其實如果能解出這題的話，可以去MIT當數學教授， 真正的解答還沒有人解出來， 有找到一篇文章， 目前找到的上界為163張，解法如下： 參考請google：Betting Wheels, Lotteries & Lotto Designs We can get an upper bound by noticing the construction that gives: L(49,6,6,3) <= L(22,6,3,3) + L(27,6,4,3) <= 77+86 = 163. Proof: Take any p=6-set out of the 49 elements. Either there are at least 3 elements from the 22 elements and we have one of the 77 blocks intersecting the 6-set in at least three elements or there are at least 4 elements from the 27 elements and there is a block intersecting the 6-set in at least 3 elements. Now LD(22,6,3,3;77) is a well-known combinatorial design and you could not get a better lotto design. Whereas LD(27,6,4,3;86) was found by a computer program using a simulated annealing algorithm. It can probably be improved. But even if LD(27,6,4,3;86) was the best you could do, there may be better ways to split the 49 elements or better different constructions. 所以原PO被洗臉別太難過，因為主管連自己也不知道答案 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.250.45.74
推
11/20 21:04, , 1F
還不少人嗆原PO說不難 大一學生就會了ww
11/20 21:04, 1F
推
11/20 21:45, , 2F
講得出這篇內容的應該馬上就錄取了吧 主管:你當我主管吧
11/20 21:45, 2F
→
11/20 21:48, , 3F
拜託...板上一堆MIT書卷 這題一行算式就可解出...
11/20 21:48, 3F
→
11/20 21:52, , 4F
鍵盤書卷
11/20 21:52, 4F
→
11/20 21:54, , 5F
原PO不是只是轉PO而已嗎 而且重點是那篇文章大概只是人家的
11/20 21:54, 5F
→
11/20 21:54, , 6F
期末報告而已吧
11/20 21:54, 6F
→
11/20 21:55, , 7F
這題不就是鴿籠原理而已嗎?
11/20 21:55, 7F
→
11/20 21:56, , 8F
不然假設一箱有十顆球 八黑 二白 至少需拿幾球出來
11/20 21:56, 8F
→
11/20 21:56, , 9F
才能保證拿到白球?
11/20 21:56, 9F
→
11/20 22:21, , 10F
難在你考完研究所，兩個月後就忘光離散數學了。
11/20 22:21, 10F
推
11/20 22:28, , 11F
鴿籠解是至多解，這題是要解最少吧？
11/20 22:28, 11F
→
11/20 22:47, , 12F
用鴿籠會解出那種大到靠北的數字
11/20 22:47, 12F
推
11/20 23:44, , 13F
google了一下 答案在87~163之間 有空再問問黃子嘉
11/20 23:44, 13F
→
11/20 23:57, , 14F
這種分群解法 前面有大大提到的樣子
11/20 23:57, 14F
推
11/20 23:59, , 15F
小黃都當天使一年多了,你有空也問不到(觀落陰例外)
11/20 23:59, 15F
推
11/21 00:10, , 16F
很多人連題目都看不懂 還在說什麼高中就會了XD
11/21 00:10, 16F
推
11/21 00:16, , 17F
這算打臉嗎? XD
11/21 00:16, 17F
推
11/21 00:38, , 18F
回r00919大，不是轉PO也不是期末報告，是面試考題...
11/21 00:38, 18F
推
11/21 01:12, , 19F
原諒小蛇愚鈍 現在才知道我錯了XD
11/21 01:12, 19F
→
11/21 01:14, , 20F
跑錯版 以為這是期末考題= = 而且面試擺這個也太難了吧
11/21 01:14, 20F
推
11/21 09:45, , 21F
難不是問題，通常主管是看你思考的方向，以及給完提示後
11/21 09:45, 21F
→
11/21 09:45, , 22F
是不是就能用更正確的方式來解題，考驗思考及邏輯能力
11/21 09:45, 22F
→
11/21 09:46, , 23F
不過前提是主管本身也有這種智商，而不是上網隨便抓考題
11/21 09:46, 23F
→
11/21 21:47, , 24F
面試問題不一定要完美解，因為工作多的是這種的問題
11/21 21:47, 24F
→
12/12 13:15, , 25F
133張 ,想知道可以問我 ^^
12/12 13:15, 25F
‣ 更多 maplefog 的文章
文章代碼(AID): #1IZAV_fd (Tech_Job)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 10 之 18 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共18篇)
‣ 更多 maplefog 的文章
文章代碼(AID): #1IZAV_fd (Tech_Job)