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