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

作者: grassboy2 (小胖子.吳草兒)   2013-11-22 17:42:31
(手殘按成回信,原 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
如此,我認為這樣一定會中獎
證明如下:
因為我分的這25組當中,每一組最多就兩個號碼
所以不管樂透的開獎號碼為何
這六個號碼一定會至少座落在這25組當中的三組
而我已經把25組中任三組的所有可能都買下來了
所以不論樂透號碼怎麼開,這2300組一定會中獎 #
※ 引述《pinkowa (pinkowa)》之銘言:
: 今天鼻塞,腦袋頓頓的,
: 之前上一篇有錯誤的地方請原諒我...
: 解題思路:
: 我們先建立起基本牌組. 共九組,一組六個.
: 一.{1,2,3,4,5,6} 二.{7,8,9,10,11,12}
: 以此類推...
: 三.{13,14,...,16} 四.{17, .... , 24}
: 五.{25,...,30} 六.{31,...,36}
: 七.{37,...,42} 八.{43,44,45,46,47,48}
: 但是...
: 九.{49,48,47,1,2,3}
: 接下來要把牌組間的漏網之魚抓起來...
: 牌組一,二之間的漏網之魚:
: 含一張對方的牌:6種 + 含兩張對方的牌:15種= 共21種
: 有七組牌組間的關係都是這樣...
: 牌組八,九之間的漏網之魚:
: 含一張對方的牌:4種 + 含兩張對方的牌:6種= 共10種
: 牌組九,一之間的漏網之魚:
: 含一張對方的牌:3種 + 含兩張對方的牌:3種= 共6種
: 我們把結論組合起來...
: 21種X7組 + 10種 + 6種 + 原始牌組9種 = 172種 但是這還不是最好的結果...
: 優化後的新牌組:
: 一.{1,2,3,4,5,6} 二.{6,7,8,9,10,11} 三.{11,14,...,16}
: 彼此間有些會重疊一個就好.
: 四.{17, .... ,22} 五.{22,...,27} 六.{28,...,33}
: 七.{33,...,38} 八.{39,....,44} 九.{44,...,49}
: 我們開始抓漏網之魚...
: 牌組一,二之間的漏網之魚:
: 含一張對方的牌:5種 + 含兩張對方的牌:10種= 共15種
: 牌組二,三之間的漏網之魚:
: 含一張對方的牌:5種 + 含兩張對方的牌:10種= 共15種
: 牌組三,四之間的漏網之魚:
: 含一張對方的牌:6種 + 含兩張對方的牌:15種= 共21種
: 以此關係推算
: 15 + 15 + 21 + 15 + 21 + 15 + 21 + 15 + 21 + 原始牌組9種 = 168 種
: 這應該是最優化的數字...
:
作者: hayden2111 (hayden)   2012-01-22 18:11:00
這算法跟我一樣....但我是去掉三個數字用剩下46個做
作者: hayden2111 (hayden)   2012-01-22 18:12:00
c(23,3) 答案應該是1771
作者: Ayukawayen (亞布里艾爾發芽>//<)   2012-01-22 18:12:00
可以分1~24和25~48買,因為這兩群至少有一群有3個號碼
作者: Ayukawayen (亞布里艾爾發芽>//<)   2012-01-22 18:13:00
這樣只要C(12,3)*2=440張。還有分三群的買法,可以降到350張以下。
作者: hayden2111 (hayden)   2012-01-22 18:17:00
樓上高手...@@
作者: grassboy2 (小胖子.吳草兒)   2012-01-22 18:27:00
三樓分兩組的買法好威啊! 不過分三組的買法似乎就無法
作者: grassboy2 (小胖子.吳草兒)   2012-01-22 18:28:00
確保至少有一群有三個號碼了?
作者: Ayukawayen (亞布里艾爾發芽>//<)   2012-01-22 18:59:00
對 但三群沒中可以確保2/2/2 然後拿較少的兩群組合就好
作者: Ayukawayen (亞布里艾爾發芽>//<)   2012-01-22 19:02:00
比方分8/20/21買 再加買第1群的C(4,2)乘第2群的C(10,1)
作者: Ayukawayen (亞布里艾爾發芽>//<)   2012-01-22 19:03:00
的60張就可以確保在2/2/2情況下中3個號碼
作者: qloolp (=(^.^)=)   2012-01-22 19:11:00
假如三群是1/1/4會不會不能用了?
作者: Ayukawayen (亞布里艾爾發芽>//<)   2012-01-22 19:12:00
1/1/4第三群的那C(11,3)張裡就有中的了
作者: pinkowa (pinkowa)   2012-01-22 19:43:00
可是有人的論文上下界是 87<最少張數<163 苦惱啊...
作者: pinkowa (pinkowa)   2012-01-22 19:50:00
作者: hrjesus (H R)   2012-01-22 20:07:00
想問為什麼是C(12,3)*2? 有點想不通
作者: hrjesus (H R)   2012-01-22 20:09:00
另外我贊同C(25,3) 把49個號碼分兩組 一定有某組有三個
作者: hrjesus (H R)   2012-01-22 20:10:00
所以最好分法就是1~24 25~49 隨意搭配
作者: grassboy2 (小胖子.吳草兒)   2012-01-22 20:12:00
原來分三組有這種取法!受教了 m(_ _)m
作者: hrjesus (H R)   2012-01-22 20:13:00
分三群 8/20/21 如果組合那兩群必中的沒配到第三群有中的就沒有得獎了不是嗎?
作者: BlazarArc (Midnight Sun)   2012-01-23 00:26:00
2N個號碼只要買C(N,3)就可確保一定中,不用C(2N,3)
作者: BlazarArc (Midnight Sun)   2012-01-23 00:27:00
忘了加上前提,至少3個號碼在2N中
作者: BlazarArc (Midnight Sun)   2012-01-23 00:29:00
已知:至少3個號碼在1~24中
作者: BlazarArc (Midnight Sun)   2012-01-23 00:30:00
把1~24分成G1:1~12跟G2:13~24
作者: BlazarArc (Midnight Sun)   2012-01-23 00:31:00
每張買G1 C(12,3)3個號碼跟G2 3個,比如(1,7,8,13,19,20G1 G2怎麼對應不是重點,只要G2 C(12,3)都存在
作者: grassboy2 (小胖子.吳草兒)   2012-01-23 00:32:00
驚!為什麼至少3個號碼在1~24?開獎號碼為 28 29 30 31 32 33 的話?
作者: BlazarArc (Midnight Sun)   2012-01-23 00:33:00
然後舉證, 3個號碼在(G1,G2)是(3,0) or (0,3)已經被包含(1,2)跟(2,1) 因為你已經列舉 C(12,3) 必定能找到一組
作者: BlazarArc (Midnight Sun)   2012-01-23 00:34:00
剛好對應 這三個的組合,所以也必中
作者: BlazarArc (Midnight Sun)   2012-01-23 00:35:00
"如果他在1~24中有3個" 那一定可以cover的買數是C(12,3)
作者: BlazarArc (Midnight Sun)   2012-01-23 00:36:00
所以要C(12,3)*2啊 XD
作者: grassboy2 (小胖子.吳草兒)   2012-01-23 00:55:00
喔~懂了~樓上在和 h 大解釋XD
作者: hrjesus (H R)   2012-01-23 09:22:00
為什麼會說1,2 和2,1會必定找到一組剛好對應@@a?
作者: StaticVortex   2012-01-23 12:57:00
假設 u in G1 對應 u' in G2, (1,2)組合譬如 u,v',w'
作者: StaticVortex   2012-01-23 12:59:00
則 這張(u,v,w,u',v',w')就中了
作者: Alexis (阿銓)   2012-01-23 22:35:00
如果要確保(1,2)和(2,1)不會漏掉,
作者: Alexis (阿銓)   2012-01-23 22:36:00
應該買C(12,3)*C(12,3)張彩券,而非C(12,3)*2吧!?
作者: StaticVortex   2012-01-24 01:04:00
舉例, 設G1對應G2方法: 1:13, 2:14... (mod 12 相同)
作者: StaticVortex   2012-01-24 01:06:00
若出(1,2)譬如 {4,18,20}, 必有{4,6,8,16,18,20}這張
作者: StaticVortex   2012-01-24 01:08:00
式子其實是: C(12,3)*1 + C(12,3)*1
作者: StaticVortex   2012-01-24 01:10:00
G1:1~12選3, G2:13~24根據G1一一對應;
作者: StaticVortex   2012-01-24 01:12:00
G3:25~36選3, G4:37~48根據G3一一對應;
作者: StaticVortex   2012-01-24 01:17:00
從G1&G2選6碼:C(12,3)*1,再加買G3&G4選6碼:C(12,3)*1
作者: Alexis (阿銓)   2012-01-24 14:32:00
如果出{1,18,20},哪張彩券會中獎?
作者: StaticVortex   2012-01-25 12:43:00
{1,6,8,13,18,20}
作者: Alexis (阿銓)   2012-01-25 18:11:00
懂了,謝謝
作者: pinkowa (pinkowa)   2013-02-12 12:03:00
我的答案是 133種~~~

Links booklink

Contact Us: admin [ a t ] ucptt.com