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