Re: [請益] 今天去面試IC設計軟體工程師被打爆的題目
※ 引述《grassboy2 (小胖子．吳草兒)》之銘言：
: (手殘按成回信，原 po sorry 0rz)
: 獻醜了XD
: 來個確定會中，但不保證是最少張的思考模式
: 把 1~49 個號碼分成25組：
: 分別是 {1,2} {3,4} {5,6} .... {45,46} {47,48} {49,1}
: 然後我們把這 25 組當中，"任取三組"的所有可能都買下來…
: 也就是 C(25,3) = 25 * 24 * 23 / 6 = 2300
: 如此，我認為這樣一定會中獎
這想法是對的, 不過本質上離 bound 差很遠.
你用的技巧是 grouping.
把兩個號碼弄成一組, 然後把 C(49,6) 轉成 C(49/2, 6/2) = C(25,3)..
舉個簡單的例子給你,
6 個號碼, 取四個, 我要買多少張, 才能保證會中兩個號碼?
Based on you grouping algorithm..
{1,2}, {3,4}, {5,6}.. -> C(3,2) = 3.
但實際上你只需要買 1 張就夠了.
這題目是 Graph 上面的 Vertex Covering,
有興趣的人可以去看這篇
Z. Furedi, G. J. Szekely, and Z. Zubor:
On the lottery problem,
J. Combinatorial Designs 4 (1996), 5-10.
http://www.math.uiuc.edu/~z-furedi/publ.html
不過用程式去解應該會很有趣.
--
一簫一劍平生意
負盡狂名十五年
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 96.41.13.29
推
11/25 22:08, , 1F
11/25 22:08, 1F
→
12/12 12:03, , 2F
12/12 12:03, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 18 之 18 篇)：