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

看板Tech_Job作者 (小胖子．吳草兒)時間10年前 (2013/11/22 17:42), 編輯推噓11(11推 0噓 39→)
留言50則, 9人參與, 最新討論串17/18 (看更多)
(手殘按成回信，原 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 種 : 這應該是最優化的數字... : ------------------------------------------- : 如果有錯還請大力鞭打... : 希望各位都能進理想的公司,拿優渥的薪水... : ------------------------------------------- -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.34.136.131
推
11/22 18:11, , 1F
這算法跟我一樣....但我是去掉三個數字用剩下46個做
11/22 18:11, 1F
→
11/22 18:12, , 2F
c(23,3) 答案應該是1771
11/22 18:12, 2F
推
11/22 18:12, , 3F
可以分1~24和25~48買，因為這兩群至少有一群有3個號碼
11/22 18:12, 3F
→
11/22 18:13, , 4F
這樣只要C(12,3)*2=440張。還有分三群的買法，可以降到
11/22 18:13, 4F
→
11/22 18:13, , 5F
350張以下。
11/22 18:13, 5F
推
11/22 18:17, , 6F
樓上高手...@@
11/22 18:17, 6F
→
11/22 18:27, , 7F
三樓分兩組的買法好威啊！ 不過分三組的買法似乎就無法
11/22 18:27, 7F
→
11/22 18:28, , 8F
確保至少有一群有三個號碼了？
11/22 18:28, 8F
推
11/22 18:59, , 9F
對 但三群沒中可以確保2/2/2 然後拿較少的兩群組合就好
11/22 18:59, 9F
→
11/22 19:02, , 10F
比方分8/20/21買 再加買第1群的C(4,2)乘第2群的C(10,1)
11/22 19:02, 10F
→
11/22 19:03, , 11F
的60張就可以確保在2/2/2情況下中3個號碼
11/22 19:03, 11F
推
11/22 19:11, , 12F
假如三群是1/1/4會不會不能用了?
11/22 19:11, 12F
推
11/22 19:12, , 13F
1/1/4第三群的那C(11,3)張裡就有中的了
11/22 19:12, 13F
→
11/22 19:43, , 14F
可是有人的論文上下界是 87<最少張數<163 苦惱啊...
11/22 19:43, 14F
→
11/22 19:50, , 15F
11/22 19:50, 15F
→
11/22 20:07, , 16F
想問為什麼是C(12,3)*2? 有點想不通
11/22 20:07, 16F
→
11/22 20:09, , 17F
另外我贊同C(25,3) 把49個號碼分兩組 一定有某組有三個
11/22 20:09, 17F
→
11/22 20:10, , 18F
所以最好分法就是1~24 25~49 隨意搭配
11/22 20:10, 18F
→
11/22 20:12, , 19F
原來分三組有這種取法！受教了 m(_ _)m
11/22 20:12, 19F
→
11/22 20:13, , 20F
分三群 8/20/21 如果組合那兩群必中的沒配到第三群有中的
11/22 20:13, 20F
→
11/22 20:13, , 21F
就沒有得獎了不是嗎?
11/22 20:13, 21F
推
11/23 00:26, , 22F
2N個號碼只要買C(N,3)就可確保一定中，不用C(2N,3)
11/23 00:26, 22F
→
11/23 00:27, , 23F
忘了加上前提，至少3個號碼在2N中
11/23 00:27, 23F
推
11/23 00:29, , 24F
已知：至少3個號碼在1~24中
11/23 00:29, 24F
→
11/23 00:30, , 25F
把1~24分成G1:1~12跟G2:13~24
11/23 00:30, 25F
→
11/23 00:31, , 26F
每張買G1 C(12,3)3個號碼跟G2 3個，比如(1,7,8,13,19,20
11/23 00:31, 26F
→
11/23 00:31, , 27F
G1 G2怎麼對應不是重點，只要G2 C(12,3)都存在
11/23 00:31, 27F
→
11/23 00:32, , 28F
驚！為什麼至少3個號碼在1~24？
11/23 00:32, 28F
→
11/23 00:32, , 29F
開獎號碼為 28 29 30 31 32 33 的話？
11/23 00:32, 29F
→
11/23 00:33, , 30F
然後舉證, 3個號碼在(G1,G2)是(3,0) or (0,3)已經被包含
11/23 00:33, 30F
→
11/23 00:33, , 31F
(1,2)跟(2,1) 因為你已經列舉 C(12,3) 必定能找到一組
11/23 00:33, 31F
→
11/23 00:34, , 32F
剛好對應 這三個的組合，所以也必中
11/23 00:34, 32F
→
11/23 00:35, , 33F
"如果他在1~24中有3個" 那一定可以cover的買數是C(12,3)
11/23 00:35, 33F
→
11/23 00:36, , 34F
所以要C(12,3)*2啊 XD
11/23 00:36, 34F
→
11/23 00:55, , 35F
喔~懂了~樓上在和 h 大解釋XD
11/23 00:55, 35F
→
11/23 09:22, , 36F
為什麼會說1,2 和2,1會必定找到一組剛好對應@@a?
11/23 09:22, 36F
推
11/23 12:57, , 37F
假設 u in G1 對應 u' in G2, (1,2)組合譬如 u,v',w'
11/23 12:57, 37F
→
11/23 12:59, , 38F
則 這張(u,v,w,u',v',w')就中了
11/23 12:59, 38F
→
11/23 22:35, , 39F
如果要確保(1,2)和(2,1)不會漏掉，
11/23 22:35, 39F
→
11/23 22:36, , 40F
應該買C(12,3)*C(12,3)張彩券，而非C(12,3)*2吧!?
11/23 22:36, 40F
推
11/24 01:04, , 41F
舉例, 設G1對應G2方法: 1:13, 2:14... (mod 12 相同)
11/24 01:04, 41F
→
11/24 01:06, , 42F
若出(1,2)譬如 {4,18,20}, 必有{4,6,8,16,18,20}這張
11/24 01:06, 42F
→
11/24 01:08, , 43F
式子其實是: C(12,3)*1 + C(12,3)*1
11/24 01:08, 43F
→
11/24 01:10, , 44F
G1:1~12選3, G2:13~24根據G1一一對應;
11/24 01:10, 44F
→
11/24 01:12, , 45F
G3:25~36選3, G4:37~48根據G3一一對應;
11/24 01:12, 45F
→
11/24 01:17, , 46F
從G1&G2選6碼:C(12,3)*1,再加買G3&G4選6碼:C(12,3)*1
11/24 01:17, 46F
→
11/24 14:32, , 47F
如果出{1，18，20}，哪張彩券會中獎？
11/24 14:32, 47F
→
11/25 12:43, , 48F
{1,6,8,13,18,20}
11/25 12:43, 48F
推
11/25 18:11, , 49F
懂了，謝謝
11/25 18:11, 49F
→
12/12 12:03, , 50F
我的答案是 133種~~~
12/12 12:03, 50F
‣ 更多 grassboy2 的文章
文章代碼(AID): #1IZoS910 (Tech_Job)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 17 之 18 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共18篇)
‣ 更多 grassboy2 的文章
文章代碼(AID): #1IZoS910 (Tech_Job)