Re: [请益] 今天去面试IC设计软件工程师被打爆的题目
楼主: Alexis (阿铨) 2013-11-22 00:15:16
我跟J一样想法
总张数 X = C(49, 6)
中奖张数 Y = C(6,6)*C(43,0)+C(6,5)*C(43,1)+C(6,4)*C(43,2)+C(6,3)*C(43,3)
杠龟张数 Z = X - Y
想像自己正在对奖，最倒楣要对几张才会中
一直对不中的机率 = Z/X * (Z-1)/(X-1) * (Z-2)/(X-2) * ......* (Z-n)/(X-n) = 0
理论上，买 Z+1 张必中
实际上，看n为多少可以让不中的机率趋近于0
那买n+1张大概就会中了
※ 引述《javatea (:))》之铭言：
: MIT教授没那么简单 好吗...
: 这不是什么难解的问题吧
: 英文看起来有比较高级吗? 有几个人是真的看过这到底是写什么?
: 今天问你49个号码选6个号码开奖 (中奖定义:3个以上相同球)
: 问你最少要买几张可以期望中一张
: 这应该只是数字大了一点而已
: 把问题简化成 6个号码开2个号码开奖 (中奖定义:1个以上相同球)
: 大家会算不出来?
: ex:把所有中奖机率算出来 得到一个机率, 就可以算期望值了
: 面试遇到问题很复杂数字很大 别一开始就被吓到
: 试着去拆问题 简化问题
: 面试也就是看你处理问题的想法而已
: 另外英文不好就别乱用google
: ※ 引述《maplefog (枫雾)》之铭言：
: : 其实如果能解出这题的话，可以去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被洗脸别太难过，因为主管连自己也不知道答案
总张数 X = C(49, 6)
中奖张数 Y = C(6,6)*C(43,0)+C(6,5)*C(43,1)+C(6,4)*C(43,2)+C(6,3)*C(43,3)
杠龟张数 Z = X - Y
想像自己正在对奖，最倒楣要对几张才会中
一直对不中的机率 = Z/X * (Z-1)/(X-1) * (Z-2)/(X-2) * ......* (Z-n)/(X-n) = 0
理论上，买 Z+1 张必中
实际上，看n为多少可以让不中的机率趋近于0
那买n+1张大概就会中了
※ 引述《javatea (:))》之铭言：
: MIT教授没那么简单 好吗...
: 这不是什么难解的问题吧
: 英文看起来有比较高级吗? 有几个人是真的看过这到底是写什么?
: 今天问你49个号码选6个号码开奖 (中奖定义:3个以上相同球)
: 问你最少要买几张可以期望中一张
: 这应该只是数字大了一点而已
: 把问题简化成 6个号码开2个号码开奖 (中奖定义:1个以上相同球)
: 大家会算不出来?
: ex:把所有中奖机率算出来 得到一个机率, 就可以算期望值了
: 面试遇到问题很复杂数字很大 别一开始就被吓到
: 试着去拆问题 简化问题
: 面试也就是看你处理问题的想法而已
: 另外英文不好就别乱用google
: ※ 引述《maplefog (枫雾)》之铭言：
: : 其实如果能解出这题的话，可以去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被洗脸别太难过，因为主管连自己也不知道答案
作者: drkkimo (花猫~ 努力工作) 2012-01-22 00:47:00
完全错误吧 买完Z张后是必中没错,但不等于没有更少张的买法
作者: drkkimo (花猫~ 努力工作) 2012-01-22 00:49:00
而且这问题和机率完全没关系
作者: pinkowa (pinkowa) 2012-01-22 09:59:00
其实这些题目都还蛮简单的...
作者: pinkowa (pinkowa) 2012-01-22 10:02:00
最早原PO的那四题,大学教科书上都有解答...
作者: PUTOUCHANG (自己的废文自己发) 2012-01-22 10:27:00
大学教科书没教我怎么用程式实做，跪求楼上大大指点
作者: poeoe 2012-01-22 10:52:00
..这不是最少阿 题目是要问"最少"
作者: poeoe 2012-01-22 10:56:00
如果有解答 想请问第二题的最少张数是多少?
作者: pinkowa (pinkowa) 2012-01-22 11:29:00
程式题是大学部的"数学实验"有修数学系的课应该就会
作者: pinkowa (pinkowa) 2012-01-22 11:41:00
[(49!/43!)-(8X46X45X44)+1] <---我认为要买的必中张数
作者: pinkowa (pinkowa) 2012-01-22 11:42:00
打错[(49!/43!)-(2X5X4X46X45X44)+1]
作者: pinkowa (pinkowa) 2012-01-22 11:51:00
又打错了...OTZ 打错[(49!/43!)-(5X4X46X45X44)+1]
作者: poeoe 2012-01-22 12:13:00
这数字是最少张数吗? 之前有篇文提到上界是163张~
作者: pinkowa (pinkowa) 2012-01-22 12:24:00
poeoe 等等我看错题目
作者: pinkowa (pinkowa) 2012-01-22 12:31:00
保证中一张<---是这样吧? 怎么会是163张?
作者: poeoe 2012-01-22 12:35:00
意思就是用规划过的买法最少买163张可以中一张
作者: pinkowa (pinkowa) 2012-01-22 12:48:00
等等我漏算中四五六个的中奖,但是163张?
作者: BlazarArc (Midnight Sun) 2012-01-22 12:53:00
有没有搞不清楚题意的八卦...
作者: pinkowa (pinkowa) 2012-01-22 12:56:00
不对啊,我已经包进去了... 怎么会是163张?
作者: pinkowa (pinkowa) 2012-01-22 12:58:00
maplefog 那篇我看到了,算我错吧~~~ OTZ....
作者: pinkowa (pinkowa) 2012-01-22 13:23:00
" target="_blank" rel="nofollow"> 如果我没记错游森棚是高大学数学系作者: pinkowa (pinkowa) 2012-01-22 13:25:00
系统之中，只要买123张，就保证至少可以对3个号码...
作者: pinkowa (pinkowa) 2012-01-22 13:27:00
说错了,他是台湾师范大学... OTZ
作者: hoppy0626 (Hoppy) 2012-01-22 14:44:00
123张是42选6 这题是49选6
作者: hayden2111 (hayden) 2012-01-22 16:05:00
可以请教123张搭配的选号法或证明吗...有看没有懂
作者: pinkowa (pinkowa) 2012-01-22 16:30:00
我重PO一篇了,请参考我的新回文,推文部份应该是我错了