`

【编程珠玑】第十二章 取样问题

 
阅读更多

一,概述

问题描述:如何生成0~n-1内的m个随机整数(不重复

需求:按序输出,并且保证每个子集被选中的可能性相等。

1)给出下面代码


其中for循环保证 按序输出,rand()%(n-i) 保证输出概率符合要求。

算法时间复杂度 O(n)

2)非常规求法:

将n个数写到大小相等的纸片上,摇匀。然后取出m个纸片,按序输出m个纸片


3)解决算法时间复杂度问题,提出以下优化方案

给定一个集合S,每次插入一个元素。插入之前检查S中个数是否达到m,且随机数在不在m中。


C++模板插入操作在O(logm)时间内完成,而遍历集合需要O(m)时间。所以完整程序需要O(mlogm)时间

4)生成随机数的另一种方式:把包含0 - n-1的数组顺序打乱,然后把前m个元素输出。

更好的方式是,我们只需要打乱前m个元素,然后排序输出。

或者生成大于n个1 - n范围的随机数,然后去掉重复的,输出前面的m个元素


二,习题

1)


2)选择的m子集的概率相等,如何做?

在1 - n范围内随机选择一个数,然后其后的m-1 个数为所选择的子集(有可能到头,然后从0开始)


3)

当m < n/2时,

总共试了k次,则前面k-1次找到的数都是在集合中,那么只有第k次不在里面,那么概率

p = (m/n)^(k-1) * (n-m)/n

那么期望是 连加 k = 1至无穷大,根据二项式分布可知,期望等于

n/(n-m) < 2

从而可知得证

4)参考算法导论中文版64页。

搜集n张随机赠送的赠券,需要多少次? nlogn次


7)先输出再递归,改成先递归再输出

9)给出一个算法,在最坏情况下只使用m个随机数。而不用丢弃已经生成的随机数


10)问题:如何随机从n个对象中选择一个对象,这n个对象是按序排列的,但是在此之前你并不知道n的值?具体些说,在事先并不知道行数的情况下,如何读一个文本文件,随机选择并输出一行?

解答:我们总是选择第一行,并使用二分之一的概率选择第二行,使用三分之一的概率选择第三行,以此类推。在该过程结束的时候,每一行具有相同的选中概率(1/n,其中n是文件的总行数):


i = 0
while more input lines
with probability 1.0/++i
choice = this input line //如果前面做了选择,并不会break,而是直到最后一个为止。
print choice


这里比较有些疑惑的是第一行:总是选第一行 为什么概率还是1/n?

概率=1*(1/2)*(2/3)*(3/4)……(n-1/n) =1/n

证明:
当做第i步选择(选择第i行)时,选择该行的概率为1/i,则不选择的概率为(i-1)/i


对于一篇有n行的文档,现需证明最终选定第i行的概率为1/n。
当最终选择第i行,前(i-1)步的选择对最终结果不会产生影响,第i步选择的概率为1/i,即选择第i行,第(i+1~n)步中均采取不选择的动作,即对于任意j(i+1<=j<=n),当前步的概率为(j-1)/j,那么最终的概率为:
(1/i)*((i)/(i+1))*...*((n-1)/n) = 1/n


以一篇只有6行的文档为例,最终选择第2行的概率为:
1/2*(2/3)*(3/4)*(4/5)*(5/6) = 1/6


扩展:
原问题可简化为:
如何从n个有序对象中等概率地任意抽取1个,简记为sample(n,1),其中n未知;
若将该问题改为:
如何从n个有序对象中等概率地任意抽取m个,简记为sample(n,m),其中n未知;


分析:
若n已知,sample(n,m)是普通的抽样问题;当n未知时,可否根据上述算法进行相应的转化求解?


解决方案:
将sample(n,m)问题转化为m个sample(n*,1)问题,更具体一点是,转化为
sample(n,1);sample(n-1,1);sample(n-2,1)....;sample(n-m+1,1)问题。


仍然以一篇6行文档为例,任取其中2行,做法如下:
第一遍,以如下概率选中一行:
1(1) 2(1/2) 3(1/3) 4(1/4) 5(1/5) 6(1/6)


假设选中第2行,接着概率修改如下:
3(1) 4(1/2) 5(1/3) 6(1/4) 1(1/5)


【说明】:当选中第2行,从第3行开始修改概率,并将第2行排除在外,继续扫描,这样能保证在剩下的5个数中仍然以等概率抽取其中的一个。

11)这个题看似很复杂,其实很简单。只需要关注1,2,3如何输出即可。要想获胜,只需要1,2先输出,三个数的全排列中这种情况有2种。所以获胜概率为2/6

=1/3




分享到:
评论

相关推荐

    编程珠玑 编程珠玑 编程珠玑 编程

    书中涵盖了一系列实用的编程问题和解决方案,这些“珠玑”般的编程智慧,无论对于初学者还是经验丰富的开发者,都有着极高的参考价值。 编程珠玑的核心概念之一是数据结构与算法的选择和设计。书中的例子多以实际...

    编程珠玑.pdf

    第12章 对调查的研究 113 12.1 有关民意调查的问题 113 12.2 语言 114 12.3 图片 117 12.4 原理 119 12.5 习题 120 第四部分 算 法 第13章 绝妙的取样 123 13.1 取样算法一瞥 123 13.2 Floyd算法 124 13.3 随机排列 ...

    编程珠玑源码下载编程珠玑书后源代码

    3. **问题解决策略**:书中提出了解决编程问题的一些通用方法,如预处理、分治法、动态规划等,帮助读者建立系统化的思维模式。 4. **性能分析**:讲解如何分析和改进程序性能,包括时间复杂度和空间复杂度的计算,...

    编程珠玑 第2版(修订版)_编程珠玑修订_资料_

    《编程珠玑 第2版(修订版)》是一本深受程序员喜爱的经典著作,它不仅提供了丰富的编程实践经验,还深入探讨了程序设计的艺术与智慧。这本书的修订版更是在原版基础上进行了更新和完善,旨在帮助程序员提升编程技能,...

    编程珠玑(续)

    《编程珠玑(续)》是计算机科学方面的经典名著《编程珠玑》的姊妹篇,讲述了对于程序员有共性的知识。书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例,这些内容组成一个有机的整体,...

    编程珠玑 编程珠玑续

    在《编程珠玑》中,作者Jon Bentley将编程问题比喻为“珍珠”,强调解决这些问题的过程如同寻找珍贵的珍珠,需要深思熟虑和精心打磨。书中的主要知识点包括: 1. **问题解决策略**:如何分析问题,确定合适的算法,...

    编程珠玑之第二章questionC 测试数据

    "第二章questionC"提及的问题是关于"求变位词",这是一个常见的字符串处理问题,涉及到字符统计、排序以及字符串比较等基础知识。 变位词,又称为同字母异序词,是指两个或多个单词由完全相同的字母组成,但字母...

    编程珠玑续本

    编程珠玑续、编程珠玑续本、编程珠玑续本、编程珠玑续本

    编程珠玑 第二版 修订版

    第12章 取样问题 119 12.1 问题 119 12.2 一种解决方案 120 12.3 设计空间 121 12.4 原理 123 12.5 习题 124 12.6 深入阅读 125 第13章 搜索 127 13.1 接口 127 13.2 线性结构 129 13.3 二分搜索树 132 ...

    编程珠玑(第二版)答案

    根据提供的标题“编程珠玑(第二版)答案”和描述“编程珠玑(第二版)答案”,我们可以推测出这是关于《编程珠玑》这本书的相关解答资料。《编程珠玑》是一本经典的计算机科学书籍,作者为Jon Bentley。本书旨在...

    编程珠玑及其源码

    为此,本书给出了一些精心设计的有趣而且颇具指导意义的程序,这些程序能够为那些复杂的编程问题提供清晰而且完备的解决思路,书中还充满了对实用程序设计技巧及基本设计原则的清晰而睿智的描述。

    编程珠玑 Programming Pearls 第二版(中文版+源代码)

    1. **问题解决策略**:书中通过一系列精心设计的编程问题,引导读者学习如何有效地分析问题,找出最优解。这些问题通常涉及数据结构的选择、算法效率的提升以及资源的优化利用。 2. **算法设计与分析**:《编程珠玑...

    编程珠玑(PDF带目录)

    这本书的主要内容围绕算法展开,旨在帮助读者掌握如何有效地解决编程问题,尤其是数据结构和算法设计方面的技巧。 在编程领域,算法是解决问题的核心工具,它们是程序的“智慧”。《编程珠玑》不仅涵盖了基础的排序...

    《编程珠玑》第二版(Programming Pearls,2nd Edition)(英文版+中文版+源码)高清PDF.rar

    Jon Bentley,世界著名计算机科学家,被誉为影响算法发展的十位大师之一。他先后任职于卡内基—梅隆大学(1976—1982)、贝尔实验室(1982—2001)和Avaya实验室(2001年至今)。在卡内基—梅隆大学担任教授期间,他培养了...

    《编程珠玑》源代码

    《编程珠玑》第一版是我早期职业生涯中阅读过的对我影响较大的书籍之一,在书中首次接触到的很多观点都让我长期受益。作者在这一版本中做了重要更新。新增加的很多例子让我耳目一新。 ——Steve McConnell,《代码...

    编程珠玑源代码

    《编程珠玑》是计算机科学领域的一本经典著作,作者是Jon Bentley,它以其深入浅出的讲解方式,探讨了程序设计中的一些核心问题。这本书不仅涵盖了算法和数据结构,还涉及了问题解决、程序效率优化以及软件工程的...

    编程珠玑II(编程珠玑·续) 扫描版6.56M pdf格式

    编程珠玑II(编程珠玑·续) 扫描版6.56M pdf格式

    编程珠玑习题集锦

    《编程珠玑》是计算机科学领域的一本经典之作,...以上是《编程珠玑》中涉及的一些核心知识点,这些问题和方法展示了如何运用巧妙的算法和数据结构来解决实际编程问题。这本书对于提升编程思维和技能有着极高的价值。

Global site tag (gtag.js) - Google Analytics