`
lavafree
  • 浏览: 539006 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

10000个球中随机取出1000个球

    博客分类:
  • Java
阅读更多

前几天看到一个算法题,说有10000个球,从中随机取出1000个,要求高性能?

 

 

刚开始我的想法是,循环0-1000 每次在0-10000中产生随机数,如果map中不存在,就放入map中,基数加1,如果存在,不加。这个方式基本能实现,但是效率不高,而且理论上有可能死循环。

 

还有一个方式就是,循环1000次,每次产生0-9的随机数,然后基数*10+随机数,存入map中。这样1000次肯定产生不同的球,第二个算法就是每次概率减少1/1000,最后一个概率只有1/10.而前一种最后一个是1/9001.

 

周末无聊,学python,顺便来一个python实现

 

 

import random

map = {}
for i in range(0,1000):
    t = random.randint(i*10,i*10+9)
    map[t]=t

for k in map.iterkeys():
    print k
0
6
分享到:
评论
4 楼 lavafree 2011-03-07  
zcsuntt 写道
for(i = 0; i < 10000; i++)
{
x[i] = i;
}
for(i = 0; i < 1000; i++)
{
t = rand(i,10000-1);
swap(x[i], x[t]);
out(x[i]);
}


既然是从10000个球中区出1000个,所以取出的球可定不能重复,你的代码可定有问题,比如第一次随机数是100,第二次随机数还是100。还有,你第一次循环10000次,第二次又循环1000次,还要做交换,代码效率极差!
3 楼 lavafree 2011-03-07  
贫僧不吃肉 写道
7  * 10 + 20 == 6 * 10 + 30


不会出现你那种情况,每次i为i+1,而且随机数是在0-9范围内。
2 楼 zcsuntt 2011-03-07  
for(i = 0; i < 10000; i++)
{
x[i] = i;
}
for(i = 0; i < 1000; i++)
{
t = rand(i,10000-1);
swap(x[i], x[t]);
out(x[i]);
}
1 楼 贫僧不吃肉 2011-03-06  
7  * 10 + 20 == 6 * 10 + 30

相关推荐

    PHP实现在数据库百万条数据中随机获取20条记录的方法

    2.根据总条数,随机1次,1次性取出20条记录(当然这个就相当于分页了,要求不高的话,这个最快,我用的就是这个); 还有一种方法,随机20次,重复执行20次。 例如: $sum=800000;//得到总条数 /

    2018年秋九年级数学上册第25章随机事件的概率25.2随机事件的概率25.2.1概率及其意义同步练习新版华东师大版201808

    7. **从混合颜色球的袋中抽取特定颜色球的概率**:如果随机摸出一个蓝球的概率是,那么红球的概率可以通过1减去蓝球和黄球的概率来计算,因为总概率应为1。 8. **从特定数量球中抽取特定颜色球的概率**:摸到红球的...

    操作系统课设消息的发送与接收实现

    在这个课设中,我们将使用C语言来模拟实现这一机制。通过理解并实现消息的发送与接收,你可以深入学习操作系统内核如何协调并发执行的任务。 首先,我们需要了解基本的消息队列概念。消息队列是存储消息的数据结构...

    操作系统 进程通信

    它提供了一种异步通信的方式,使得进程可以在任意时刻发送消息,并且消息会被存储在一个特殊的队列中,等待其他进程取出。 #### 2. 实现细节 本实验还提供了一个基于消息队列的通信示例,同样包括发送方(sndfile.c...

    进程通信

    3. **消息队列(Message Queue)**:消息队列允许进程间异步通信,每个进程可以发送消息到队列,接收方可以从队列中取出消息。这种方式支持消息的存档和优先级设定。 4. **信号量(Semaphore)**:信号量主要用于...

    湖南省茶陵县第三中学2017_2018学年高一数学作业8无答案

    在高中数学的学习中,概率是重要的一个章节,主要探讨随机事件发生的可能性。以下是对题目中涉及的几个概率问题的详细解析: 1. 第一题,从数字1到11中任选一个数字,奇数的概率是6/11,因为11个数字中有6个奇数(1...

    冒泡,插入,快速和选择排序C源码

    2. **逐个插入**:从未排序部分取出一个元素,通过向已排序部分的前面移动元素来为新元素腾出空间,并将新元素插入到正确位置。 3. **逐步扩展**:逐步将未排序部分的元素插入到已排序部分中,直到整个数组排序完成...

    进程管理与通信总结

    - **消息队列**:为进程间通信提供了一种方法,可以在队列中插入消息项,接收进程可以从队列中取出消息。 - **信号灯(Semaphore)**:一种同步机制,用于控制多个进程对共享资源的访问。使用`ftok`函数获取键值,...

    初二下册数学期中考试题.docx

    例如,“在1,3,5,7,9中任取出两个数,组成一个奇数的两位数”,这是一个必然事件,因为所有的数都是奇数,无论怎么组合,结果都是奇数。 3. **概率的基本性质**:概率在0到1之间,其中0表示不可能事件,1表示...

    (word完整版)高中数学概率大题(经典二).docx

    - 二项分布:第二题中,从10个灯泡中取出2个正品,这是一个典型的二项分布问题。 - 几何分布:第六题中,求解至少有一人采用1期付款的概率,涉及到几何分布。 - 泊松分布:第九题中,保险公司至少支付10000元赔偿...

    创新编程思维训练趣味题(附答案)

    你随机选择一个盒子并从中取出一个球。如果取出的是红球,那么这个球来自第一个盒子的概率是多少? **解答**: - 设事件 A 表示取出的球是红球,事件 B 表示球来自第一个盒子。 - \( P(B|A) \) 表示在取出的球是红...

    北师大版五年级数学上册期末考试题及答案_三套.docx

    - 口袋里有8个红球和4个黄球,随机取出一个球,求取出红球和黄球的概率。 - **解答**:取出红球的概率为\( \frac{8}{12} = \frac{2}{3} \);取出黄球的概率为\( \frac{4}{12} = \frac{1}{3} \)。由于红球数量多于...

    信息论与编码习题解答(待校200812)

    - **广播员描述图像的信息量**:如果广播员从10000个汉字中选取1000个汉字来描述此图像,并假设汉字等概率出现,那么每个汉字的信息量为 \(-\log_2 \left(\frac{1}{10000}\right) = 13.32\) 比特。描述整帧图像的...

    数据结构排序.rar

    初始时,我们可以把数组看作是未排序的扑克牌堆,每次取出一张牌(数组的一个元素),找到它应该插入的位置,然后将其插入到已排序的部分中。这个过程会重复直到所有元素都被插入到正确的位置。插入排序的时间复杂度...

    《信息论与编码》答案 沈连丰,叶芝惠

    - **问题3**:广播员从10000个汉字中选取1000个字来描述这帧图像。每个汉字的信息量为\[ H(Y) = \log_2 10000 = 13.29 \]比特。广播员描述整帧图像的信息量为\[ 13.29 \times 1000 \]比特。为了准确描述这帧图像,...

    4.13-C++周作业.docx

    根据给定文件的信息,我们可以将相关...以上四个部分覆盖了文件中提到的所有知识点,包括基本的输入输出、循环、条件判断以及随机数生成等。这些示例代码不仅帮助理解和解决题目中的问题,也是学习C++编程的基础案例。

    A*算法求解八数码问题_C#语言

    下图是解决随机生成的100中状态中,两个生成函数的生成节点与扩展节点统计图: 由上述图表可以看到,将P(n)作为启发函数比将W(n)作为启发函数时,生成节点数与扩展节点数更稳定,相比较来说,采用P(n)作为启发...

    哈希表的应用,介绍了一些哈希表的用例

    假设有一个哈希表用于存储学生学号,学号范围为10000-20000,哈希表大小为1000。使用除留余数法作为哈希函数,即`H(k) = k mod 1000`。当遇到学号10200和11200时,它们都会被映射到索引200处,这时可以采用开放定址...

    PHP查找数值数组中不重复最大和最小的10个数的方法

    //随机生成1万个元素的数组 for($i=0;$i&lt;10000;$i++){ $ary[]=rand(1,100000); } $ary=array_unique($ary); //去重复数值 sort($ary);//顺序排序 $min_10=array_slice($ary,0, 10);//取出最小的10个数值 $max_10...

    江西省上饶市 高二数学上学期期中联考试题 理(统招班) 试题.doc

    题目中提到要从10000名小观众中抽取10名,抽样距应为10000/10=1000,所以答案是C。 3. **线性回归**:线性回归是分析两个变量之间线性关系的方法。题目中说变量x与y负相关,即x增加时y减少。样本平均x=2,y=2.5,...

Global site tag (gtag.js) - Google Analytics