顯示廣告
隱藏 ✕
※ 本文為 BruceX 轉寄自 ptt.cc 更新時間: 2013-11-22 17:54:45
看板 Tech_Job
作者 maplefog (楓霧)
標題 Re: [請益] 今天去面試IC設計軟體工程師被打爆的題目
時間 Wed Nov 20 20:15:56 2013



: (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
asleisureto:還不少人嗆原PO說不難  大一學生就會了ww1F 11/20 21:04
tonyhsie:講得出這篇內容的應該馬上就錄取了吧 主管:你當我主管吧2F 11/20 21:45
Onnnnnnnnnnn:拜託...板上一堆MIT書卷 這題一行算式就可解出...3F 11/20 21:48
RolfP:鍵盤書卷4F 11/20 21:52
r00919:原PO不是只是轉PO而已嗎 而且重點是那篇文章大概只是人家的5F 11/20 21:54
r00919:期末報告而已吧
r00919:這題不就是鴿籠原理而已嗎?
r00919:不然假設一箱有十顆球 八黑 二白 至少需拿幾球出來
r00919:才能保證拿到白球?
YunJonWei:難在你考完研究所,兩個月後就忘光離散數學了。10F 11/20 22:21
STRATOS:鴿籠解是至多解,這題是要解最少吧?11F 11/20 22:28
bbbing:用鴿籠會解出那種大到靠北的數字12F 11/20 22:47
tonyhsie:google了一下 答案在87~163之間 有空再問問黃子嘉13F 11/20 23:44
cmjan0608:這種分群解法  前面有大大提到的樣子14F 11/20 23:57
antiasus:小黃都當天使一年多了,你有空也問不到(觀落陰例外)15F 11/20 23:59
cateran:很多人連題目都看不懂 還在說什麼高中就會了XD16F 11/21 00:10
timlu:這算打臉嗎? XD17F 11/21 00:16
wildcupid:回r00919大,不是轉PO也不是期末報告,是面試考題...18F 11/21 00:38
r00919:原諒小蛇愚鈍 現在才知道我錯了XD19F 11/21 01:12
r00919:跑錯版 以為這是期末考題= = 而且面試擺這個也太難了吧
Assyla:難不是問題,通常主管是看你思考的方向,以及給完提示後21F 11/21 09:45
Assyla:是不是就能用更正確的方式來解題,考驗思考及邏輯能力
Assyla:不過前提是主管本身也有這種智商,而不是上網隨便抓考題
bbbing:面試問題不一定要完美解,因為工作多的是這種的問題24F 11/21 21:47

--
※ 看板: Tech_Job 文章推薦值: 0 目前人氣: 0 累積人氣: 2854 
※ 本文也出現在看板: terievv
r)回覆 e)編輯 d)刪除 M)收藏 ^x)轉錄 同主題: =)首篇 [)上篇 ])下篇