avatar
一道老题目 (转载)# BrainTeaser - 大脑工作室
c*s
1
【 以下文字转载自 Quant 讨论区 】
发信人: chtoucas (王秭和龚洙), 信区: Quant
标 题: 一道老题目
发信站: BBS 未名空间站 (Sun Jan 20 11:14:28 2008)
可是我想不起来了, 大意是说你有很多数要输入,
但存储空间不够, 所以只能存n个的样子,
当存满之后又有新的数进来, 就得有旧的数被踢出去。
但我们只需要知道平均数, 怎样来得到这个平均数?
不知道我记住了多少, 错了多少, 谁能帮忙回忆一下, 多谢。。。
avatar
h*0
2
为啥不用一个空间存数的个数,剩下的空间把数加上去。

【在 c******s 的大作中提到】
: 【 以下文字转载自 Quant 讨论区 】
: 发信人: chtoucas (王秭和龚洙), 信区: Quant
: 标 题: 一道老题目
: 发信站: BBS 未名空间站 (Sun Jan 20 11:14:28 2008)
: 可是我想不起来了, 大意是说你有很多数要输入,
: 但存储空间不够, 所以只能存n个的样子,
: 当存满之后又有新的数进来, 就得有旧的数被踢出去。
: 但我们只需要知道平均数, 怎样来得到这个平均数?
: 不知道我记住了多少, 错了多少, 谁能帮忙回忆一下, 多谢。。。

avatar
c*s
3
呵呵。。。我是想知道原题长什么样子,
误导你了, 不好意思。

【在 h*****0 的大作中提到】
: 为啥不用一个空间存数的个数,剩下的空间把数加上去。
avatar
c*s
4
太感谢了...这正是我要找的题目.
换成数字版本, 再把存储一行推广到K行, 应该可以这样来问:
有很多但不知道确切数目的数据要读入, 每次读一个, 但系统只能存K个.
要求这K个数是从已经读取的数据中随机的选出来的,
每一个被读取过的数据被选中的概率要相等.

去。
avatar
h*0
5
这个怎么乍一看觉得不可能呢?

【在 c******s 的大作中提到】
: 太感谢了...这正是我要找的题目.
: 换成数字版本, 再把存储一行推广到K行, 应该可以这样来问:
: 有很多但不知道确切数目的数据要读入, 每次读一个, 但系统只能存K个.
: 要求这K个数是从已经读取的数据中随机的选出来的,
: 每一个被读取过的数据被选中的概率要相等.
:
: 去。

avatar
c*g
6
可能,好好想想
拿两个,三个数的例子做一做

【在 h*****0 的大作中提到】
: 这个怎么乍一看觉得不可能呢?
avatar
h*0
7
就考虑最简单的,一次只能读入一个数,有N个数,但不知道N是几,怎么以相同概率输
出任意一个数?

【在 c*****g 的大作中提到】
: 可能,好好想想
: 拿两个,三个数的例子做一做

avatar
c*g
8
ft, 这不是跟原题一样吗

【在 h*****0 的大作中提到】
: 就考虑最简单的,一次只能读入一个数,有N个数,但不知道N是几,怎么以相同概率输
: 出任意一个数?

avatar
h*0
9
啊?这个还能有简化版?要知道有几个数那不就简单了吗。

【在 c*****g 的大作中提到】
: ft, 这不是跟原题一样吗
avatar
c*g
10
我的意思是从简单的例子开始考虑,再总结规律
读到第一个数的时候肯定要保留下来。
读到第二个数的时候,如果一共就2个数,那么选择第一个和第二个的概率各为50%,
所以50%的概率用第二个数替换原来保留的数。
读到第三个数的时候,...

【在 h*****0 的大作中提到】
: 啊?这个还能有简化版?要知道有几个数那不就简单了吗。
avatar
n*n
11
太老了,不做,就是1/2,1/3的弄下去,发包子把

【在 c******s 的大作中提到】
: 【 以下文字转载自 Quant 讨论区 】
: 发信人: chtoucas (王秭和龚洙), 信区: Quant
: 标 题: 一道老题目
: 发信站: BBS 未名空间站 (Sun Jan 20 11:14:28 2008)
: 可是我想不起来了, 大意是说你有很多数要输入,
: 但存储空间不够, 所以只能存n个的样子,
: 当存满之后又有新的数进来, 就得有旧的数被踢出去。
: 但我们只需要知道平均数, 怎样来得到这个平均数?
: 不知道我记住了多少, 错了多少, 谁能帮忙回忆一下, 多谢。。。

avatar
n*n
12
当然可能了,给我包子高速你

【在 h*****0 的大作中提到】
: 这个怎么乍一看觉得不可能呢?
avatar
h*0
13
赞。那这样的话N个数留K个就直接是1/N概率保留,1/K * (N-1)/N的概率换掉前面的某
个数,没啥新东西呀。

【在 c*****g 的大作中提到】
: 我的意思是从简单的例子开始考虑,再总结规律
: 读到第一个数的时候肯定要保留下来。
: 读到第二个数的时候,如果一共就2个数,那么选择第一个和第二个的概率各为50%,
: 所以50%的概率用第二个数替换原来保留的数。
: 读到第三个数的时候,...

avatar
c*s
14
kao...简单粗暴啊

【在 n*n 的大作中提到】
: 太老了,不做,就是1/2,1/3的弄下去,发包子把
avatar
n*n
15
很暴力,很....

【在 c******s 的大作中提到】
: kao...简单粗暴啊
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。