m****r
发帖数: 141 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: mitcar (mitcar), 信区: JobHunting
标 题: 一道面试题， 挺难的， 求助
发信站: BBS 未名空间站 (Sun May 26 19:46:34 2013, 美东)
把一副扑克牌， 一张一张地随机放到一张大桌子上，
假设， 桌子的面积远远大于扑克牌的面积，
假设， 所有扑克牌都平落在桌子上，
如何计算扑克牌所覆盖的桌子的面积，
注意， 扑克牌可能会重叠， 可能会分散 不连续
请分析算法的复杂度 | s*********y
发帖数: 45 | 2 如果我二了，请你告诉我，因为不理解为什么会有“分析算法复杂度”这个问题,所以
可能完全偏题了。
Let T= table area, C= card area, n= 54= number of cards in a deck.
Define f: {Points on the table} -> {0,1} by
f(p)= 1 if and only if p is covered by some card.
Then
Area Covered = int_{table} f dA.
(here, we think of table as a subset of R^2, so a two dimensional
integration)
Then
E[Area Covered] = E[int_{table}f] = int_{table} E[f].
As "桌子的面积远远大于扑克牌的面积", we may view E[f] as a constant and
E[f]= probability that the point is covered by some card = 1- (1- C/T)^n.
So Area Covered = T(1-(1-C/T)^n).
【在 m****r 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: mitcar (mitcar), 信区: JobHunting
: 标 题: 一道面试题， 挺难的， 求助
: 发信站: BBS 未名空间站 (Sun May 26 19:46:34 2013, 美东)
: 把一副扑克牌， 一张一张地随机放到一张大桌子上，
: 假设， 桌子的面积远远大于扑克牌的面积，
: 假设， 所有扑克牌都平落在桌子上，
: 如何计算扑克牌所覆盖的桌子的面积，
: 注意， 扑克牌可能会重叠， 可能会分散 不连续
: 请分析算法的复杂度
|
|
