c******s
发帖数: 270 | 1 【 以下文字转载自 Quant 讨论区 】
发信人: chtoucas (王秭和龚洙), 信区: Quant
标 题: 一道老题目
发信站: BBS 未名空间站 (Sun Jan 20 11:14:28 2008)
可是我想不起来了， 大意是说你有很多数要输入，
但存储空间不够， 所以只能存n个的样子，
当存满之后又有新的数进来， 就得有旧的数被踢出去。
但我们只需要知道平均数， 怎样来得到这个平均数？
不知道我记住了多少， 错了多少， 谁能帮忙回忆一下， 多谢。。。 |
h*****0
发帖数: 4889 | 2 为啥不用一个空间存数的个数，剩下的空间把数加上去。
【在 c******s 的大作中提到】
: 【 以下文字转载自 Quant 讨论区 】
: 发信人: chtoucas (王秭和龚洙), 信区: Quant
: 标 题: 一道老题目
: 发信站: BBS 未名空间站 (Sun Jan 20 11:14:28 2008)
: 可是我想不起来了， 大意是说你有很多数要输入，
: 但存储空间不够， 所以只能存n个的样子，
: 当存满之后又有新的数进来， 就得有旧的数被踢出去。
: 但我们只需要知道平均数， 怎样来得到这个平均数？
: 不知道我记住了多少， 错了多少， 谁能帮忙回忆一下， 多谢。。。
|
c******s
发帖数: 270 | 3 呵呵。。。我是想知道原题长什么样子，
误导你了， 不好意思。
【在 h*****0 的大作中提到】
: 为啥不用一个空间存数的个数，剩下的空间把数加上去。
|
c******s
发帖数: 270 | 4 太感谢了...这正是我要找的题目.
换成数字版本, 再把存储一行推广到K行, 应该可以这样来问:
有很多但不知道确切数目的数据要读入, 每次读一个, 但系统只能存K个.
要求这K个数是从已经读取的数据中随机的选出来的,
每一个被读取过的数据被选中的概率要相等.
去。 |
h*****0
发帖数: 4889 | 5 这个怎么乍一看觉得不可能呢？
【在 c******s 的大作中提到】
: 太感谢了...这正是我要找的题目.
: 换成数字版本, 再把存储一行推广到K行, 应该可以这样来问:
: 有很多但不知道确切数目的数据要读入, 每次读一个, 但系统只能存K个.
: 要求这K个数是从已经读取的数据中随机的选出来的,
: 每一个被读取过的数据被选中的概率要相等.
:
: 去。
|
c*****g
发帖数: 1137 | 6 可能，好好想想
拿两个，三个数的例子做一做
【在 h*****0 的大作中提到】
: 这个怎么乍一看觉得不可能呢？
|
h*****0
发帖数: 4889 | 7 就考虑最简单的，一次只能读入一个数，有N个数，但不知道N是几，怎么以相同概率输
出任意一个数？
【在 c*****g 的大作中提到】
: 可能，好好想想
: 拿两个，三个数的例子做一做
|
c*****g
发帖数: 1137 | 8 ft, 这不是跟原题一样吗
【在 h*****0 的大作中提到】
: 就考虑最简单的，一次只能读入一个数，有N个数，但不知道N是几，怎么以相同概率输
: 出任意一个数？
|
h*****0
发帖数: 4889 | 9 啊？这个还能有简化版？要知道有几个数那不就简单了吗。
【在 c*****g 的大作中提到】
: ft, 这不是跟原题一样吗
|
c*****g
发帖数: 1137 | 10 我的意思是从简单的例子开始考虑，再总结规律
读到第一个数的时候肯定要保留下来。
读到第二个数的时候，如果一共就2个数，那么选择第一个和第二个的概率各为50%，
所以50%的概率用第二个数替换原来保留的数。
读到第三个数的时候，...
【在 h*****0 的大作中提到】
: 啊？这个还能有简化版？要知道有几个数那不就简单了吗。
|
|
|
n*n
发帖数: 202 | 11 太老了，不做，就是1/2,1/3的弄下去，发包子把
【在 c******s 的大作中提到】
: 【 以下文字转载自 Quant 讨论区 】
: 发信人: chtoucas (王秭和龚洙), 信区: Quant
: 标 题: 一道老题目
: 发信站: BBS 未名空间站 (Sun Jan 20 11:14:28 2008)
: 可是我想不起来了， 大意是说你有很多数要输入，
: 但存储空间不够， 所以只能存n个的样子，
: 当存满之后又有新的数进来， 就得有旧的数被踢出去。
: 但我们只需要知道平均数， 怎样来得到这个平均数？
: 不知道我记住了多少， 错了多少， 谁能帮忙回忆一下， 多谢。。。
|
n*n
发帖数: 202 | 12 当然可能了，给我包子高速你
【在 h*****0 的大作中提到】
: 这个怎么乍一看觉得不可能呢？
|
h*****0
发帖数: 4889 | 13 赞。那这样的话N个数留K个就直接是1/N概率保留，1/K * (N-1)/N的概率换掉前面的某
个数，没啥新东西呀。
【在 c*****g 的大作中提到】
: 我的意思是从简单的例子开始考虑，再总结规律
: 读到第一个数的时候肯定要保留下来。
: 读到第二个数的时候，如果一共就2个数，那么选择第一个和第二个的概率各为50%，
: 所以50%的概率用第二个数替换原来保留的数。
: 读到第三个数的时候，...
|
c******s
发帖数: 270 | 14 kao...简单粗暴啊
【在 n*n 的大作中提到】
: 太老了，不做，就是1/2,1/3的弄下去，发包子把
|
n*n
发帖数: 202 | 15 很暴力，很....
【在 c******s 的大作中提到】
: kao...简单粗暴啊
|
