沧州市宇通网站建设公司能否提供专业西樵地区网站设计制作服务？

沧州市宇通网站建设公司,西樵网站设计制作,深圳附近做个商城网站找哪家公司好,17网站一起做网店深圳0 概述 随机算法涉及大量概率论知识#xff0c;有时候难得去仔细看推导过程#xff0c;当然能够完全了解推导的过程自然是有好处的#xff0c;如果不了解推导过程#xff0c;至少记住结论也是必要的。本文总结最常见的一些随机算法的题目#xff0c;是几年前找工作的时候…0 概述 随机算法涉及大量概率论知识有时候难得去仔细看推导过程当然能够完全了解推导的过程自然是有好处的如果不了解推导过程至少记住结论也是必要的。本文总结最常见的一些随机算法的题目是几年前找工作的时候写的。需要说明的是这里用到的随机函数 randInt(a, b) 假定它能随机的产生范围 [a,b] 内的整数即产生每个整数的概率相等虽然在实际中并不一定能实现不过不要太在意这个世界很多事情都很随机。 1 随机排列数组 假设给定一个数组 A它包含元素 1 到 N我们的目标是构造这个数组的一个均匀随机排列。 一个常用的方法是为数组每个元素 A[i] 赋一个随机的优先级 P[i]然后依据优先级对数组进行排序。比如我们的数组为 A {1 2 3 4}如果选择的优先级数组为 P {36 3 97 19}那么就可以得到数列 B{2, 4, 1, 3}因为 3 的优先级最高为97而 2 的优先级最低为3。这个算法需要产生优先级数组还需使用优先级数组对原数组排序这里就不详细描述了还有一种更好的方法可以得到随机排列数组。 产生随机排列数组的一个更好的方法是原地排列in-place给定数组可以在 O(N) 的时间内完成。伪代码如下 RANDOMIZE-IN-PLACE ( A , n ) for i ←1 to n do swap A[i] ↔ A[RANDOM(i , n )]如代码中所示第 i 次迭代时元素 A[i] 是从元素 A[i...n]中随机选取的在第 i 次迭代后我们就再也不会改变 A[i]。 A[i] 位于任意位置j的概率为 1/n。这个是很容易推导的比如 A[1] 位于位置 1 的概率为 1/n这个显然因为 A[1] 不被1到n的元素替换的概率为 1/n而后就不会再改变 A[1] 了。而A[1] 位于位置 2 的概率也是 1/n因为 A[1] 要想位于位置2则必须在第一次与 A[k] (k2…n) 交换同时第二次 A[2] 与 A[k]替换第一次与 A[k] 交换的概率为(n-1)/n而第二次替换概率为 1/(n-1)所以总的概率是 (n-1)/n * 1/(n-1) 1/n。同理可以推导其他情况。 当然这个条件只能是随机排列数组的一个必要条件也就是说满足元素 A[i] 位于位置 j 的概率为1/n 不一定就能说明这可以产生随机排列数组。因为它可能产生的排列数目少于 n!尽管概率相等但是排列数目没有达到要求算法导论上面有一个这样的反例。 算法 RANDOMIZE-IN-PLACE可以产生均匀随机排列它的证明过程如下 首先给出k排列的概念所谓 k 排列就是从n个元素中选取k个元素的排列那么它一共有 n!/(n-k)! 个 k 排列。 循环不变式for循环第i次迭代前对于每个可能的i-1排列子数组A[1…i-1]包含该i-1排列的概率为 (n-i1)! / n!。 初始化在第一次迭代前i1则循环不变式指的是对于每个0排列子数组A[1…i-1]包含该0排列的概率为 (n-11)! / n! 1。A[1…0]为空的数组0排列则没有任何元素因此A包含所有可能的0排列的概率为1。不变式成立。 维持假设在第i次迭代前数组的i-1排列出现在 A[1...i-1] 的概率为 (n-i1) !/ n!那么在第i次迭代后数组的所有i排列出现在 A[1...i] 的概率为 (n-i)! / n!。下面来推导这个结论 考虑一个特殊的 i 排列 p {x1, x2, … xi}它由一个 i-1 排列 p’ {x1, x2,…, xi−1} 后面跟一个 xi 构成。设定两个事件变量E1和E2 E1为该算法将排列 p 放置到 A[1...i-1]的事件概率由归纳假设得知为 Pr(E1) (n-i1)! / n!。 E2为在第 i 次迭代时将 xi 放入到 A[i] 的事件。 因此我们得到 i 排列出现在 A[1...i] 的概率为 Pr {E2 ∩ E1} Pr {E2 | E1} Pr {E1}。而Pr {E2 | E1} 1/(n − i 1)所以 Pr {E2 ∩ E1} Pr {E2 | E1} Pr {E1} 1 /(n − i 1) * (n − i 1)! / n! (n − i )! / n!。 结束结束的时候 in1因此可以得到 A[1...n] 是一个给定 n 排列的概率为 1/n。 C实现代码如下 void randomInPlace(int a[], int n) {int i;for (i 0; i n; i) {int rand randInt(i, n-1);swapInt(a, i, rand);} }扩展 如果上面的随机排列算法写成下面这样是否也能产生均匀随机排列 PERMUTE-WITH-ALL( A , n ) for i ←1 to n do swap A[i] ↔A[RANDOM(1 , n )]注意该算法不能产生均匀随机排列。假定 n3则该算法可以产生3*3*327个输出而3个元素只有3!6个不同的排列要使得这些排列出现概率等于 1/6则必须使得每个排列出现次数 m 满足m/271/6显然没有这样的整数符合条件。而实际上各个排列出现的概率如下如 {1,2,3} 出现的概率为4/27不等于 1/6。 排 列概 率1, 2, 34/271, 3, 25/272, 1, 35/272, 3, 15/27❤️, 1, 24/27❤️, 2, 14/27 2 随机选取一个数字 题 给定一个未知长度的整数流如何随机选取一个数所谓随机就是保证每个数被选取的概率相等 解1 如果数据流不是很长可以存在数组中然后再从数组中随机选取。当然题目说的是未知长度所以如果长度很大不足以保存在内存中的话这种解法有其局限性。 解2 如果数据流很长的话可以这样 如果数据流在第1个数字后结束那么必选第1个数字。如果数据流在第2个数字后结束那么我们选第2个数字的概率为1/2我们以1/2的概率用第2个数字替换前面选的随机数得到新的随机数。…如果数据流在第n个数字后结束那么我们选择第n个数字的概率为1/n即我们以1/n的概率用第n个数字替换前面选的随机数得到新的随机数。 一个简单的方法就是使用随机函数 f(n)bigrand()%n其中 bigrand() 返回很大的随机整数当数据流到第 n 个数时如果 f(n)0则替换前面的已经选的随机数这样可以保证每个数字被选中的概率都是 1/n。如当 n1 时则f(1)0则选择第 1 个数当 n2 时则第 2 个数被选中的概率都为 1/2以此类推当数字长度为 n 时第 n 个数字被选中的概率为 1/n。代码如下(注在 Linux/MacOS 下rand() 函数已经可以返回一个很大的随机数了就当做bigrand()用了) void randomOne(int n) {int i, select 0;for (i 1; i n; i) {int rd rand() % n;if (rd 0) {select i;}}printf(%d\n, select); }3 随机选取M个数字 题 程序输入包含两个整数 m 和 n 其中 mn输出是 0~n-1 范围内的 m 个随机整数的有序列表不允许重复。从概率角度来说我们希望得到没有重复的有序选择其中每个选择出现的概率相等。 解1 先考虑个简单的例子当 m2n5 时我们需要从 0~4 这 5 个整数中等概率的选取 2 个有序的整数且不能重复。如果采用如下条件选取bigrand() % 5 2则我们选取 0 的概率为2/5。但是我们不能采取同样的概率来选取 1因为选取了 0 后我们应该以 1/4 的概率来选取1而在没有选取0的情况下我们应该以 2/4 的概率选取1。选取的伪代码如下 select m remaining n for i [0, n)if (bigrand() % remaining select)print iselect--remaining--只要满足条件 mn则程序输出 m 个有序整数不多不少。不会多选因为每选择一个数select--这样当 select 减到 0 后就不会再选了。同时也不会少选因为每次都会remaining--当 select/remaining1 时一定会选取一个数。每个子集被选择的概率是相等的比如这里5选2则共有 C(5,2)10 个子集如 {01}{02}...等每个子集被选中的概率都是 1/10。 更一般的推导n选m的子集数目一共有 C(n,m) 个考虑一个特定的 m 序列如0...m-1则选取它的概率为m/n * (m-1)/(n-1)*....1/(n-m1)1/C(n,m)可以看到概率是相等的。 Knuth 老爷爷很早就提出了这个算法他的实现如下 void randomMKnuth(int n, int m) {int i;for (i 0; i n; i) {if ((rand() % (n-i)) m) {printf(%d , i);m--;}} }解2 还可以采用前面随机排列数组的思想先对前 m 个数字进行随机排列然后排序这 m 个数字并输出即可。代码如下 void randomMArray(int n, int m) {int i, j;int *x (int *)malloc(sizeof(int) * n);for (i 0; i n; i)x[i] i;// 随机数组for (i 0; i m; i) {j randInt(i, n-1);swapInt(x, i, j);}// 对数组前 m 个元素排序for (i 0; i m; i) {for (j i1; j0 x[j-1]x[j]; j--) {swapInt(x, j, j-1);}}for (i 0; i m; i) {printf(%d , x[i]);}printf(\n); }4 rand7 生成 rand10 问题 题 已知一个函数rand7()能够生成1-7的随机数每个数概率相等请给出一个函数rand10()该函数能够生成 1-10 的随机数每个数概率相等。 解1 要产生 1-10 的随机数我们要么执行 rand7() 两次要么直接乘以一个数字来得到我们想要的范围值。如下面公式(1)和2。 idx 7 * (rand7()-1) rand7() ---(1) 正确 idx 8 * rand7() - 7 ---(2) 错误上面公式 (1) 能够产生 1-49 的随机数为什么呢因为 rand7() 的可能的值为 1-7两个 rand7() 则可能产生 49 种组合且正好是 1-49 这 49 个数每个数出现的概率为 1/49于是我们可以将大于 40 的丢弃然后取 (idx-1) % 10 1 即可。公式2是错误的因为它生成的数的概率不均等而且也无法生成49个数字。 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 2 8 9 10 1 2 3 4 3 5 6 7 8 9 10 1 4 2 3 4 5 6 7 8 5 9 10 1 2 3 4 5 6 6 7 8 9 10 * * 7 * * * * * * *该解法基于一种叫做拒绝采样的方法。主要思想是只要产生一个目标范围内的随机数则直接返回。如果产生的随机数不在目标范围内则丢弃该值重新取样。由于目标范围内的数字被选中的概率相等这样一个均匀的分布生成了。代码如下 int rand7ToRand10Sample() {int row, col, idx;do {row rand7();col rand7();idx col (row-1)*7;} while (idx 40);return 1 (idx-1) % 10; }由于row范围为1-7col范围为1-7这样idx值范围为1-49。大于40的值被丢弃这样剩下1-40范围内的数字通过取模返回。下面计算一下得到一个满足1-40范围的数需要进行取样的次数的期望值 E(# calls to rand7) 2 * (40/49) 4 * (9/49) * (40/49) 6 * (9/49)2 * (40/49) ...∞ ∑ 2k * (9/49)k-1 * (40/49)k1 (80/49) / (1 - 9/49)2 2.45解2 上面的方法大概需要2.45次调用 rand7 函数才能得到 1 个 1-10 范围的数下面可以进行再度优化。对于大于40的数我们不必马上丢弃可以对 41-49 的数减去 40 可得到 1-9 的随机数而rand7可生成 1-7 的随机数这样可以生成 1-63 的随机数。对于 1-60 我们可以直接返回而 61-63 则丢弃这样需要丢弃的数只有3个相比前面的9个效率有所提高。而对于61-63的数减去60后为 1-3rand7 产生 1-7这样可以再度利用产生 1-21 的数对于 1-20 我们则直接返回对于 21 则丢弃。这时丢弃的数就只有1个了优化又进一步。当然这里面对rand7的调用次数也是增加了的。代码如下优化后的期望大概是 2.2123。 int rand7ToRand10UtilizeSample() {int a, b, idx;while (1) {a randInt(1, 7);b randInt(1, 7);idx b (a-1)*7;if (idx 40)return 1 (idx-1)%10;a idx-40;b randInt(1, 7);// get uniform dist from 1 - 63idx b (a-1)*7;if (idx 60)return 1 (idx-1)%10;a idx-60;b randInt(1, 7);// get uniform dist from 1-21idx b (a-1)*7;if (idx 20)return 1 (idx-1)%10;} }5 趣味概率题 1称球问题 题 有12个小球其中一个是坏球。给你一架天平需要你用最少的称次数来确定哪个小球是坏的并且它到底是轻了还是重了。 解 之前有总结过二分查找算法我们知道二分法可以加快有序数组的查找。相似的比如在数字游戏中如果要你猜一个介于 1-64 之间的数字用二分法在6次内肯定能猜出来。但是称球问题却不同。称球问题这里 12 个小球坏球可能是其中任意一个这就有 12 种可能性。而坏球可能是重了或者轻了这2种情况于是这个问题一共有 12*2 24 种可能性。每次用天平称天平可以输出的是 平衡、左重、右重 3 种可能性即称一次可以将问题可能性缩小到原来的 1/3则一共 24 种可能性可以在 3 次内称出来(3^3 27)。 为什么最直观的称法 6-6 不是最优的在 6-6 称的时候天平平衡的可能性是0而最优策略应该是让天平每次称量时的概率均等这样才能三等分答案的所有可能性。 具体怎么实施呢 将球编号为1-12采用 4, 4 称的方法。 我们先将 1 2 3 4 和 5 6 7 8 进行第1次称重。如果第1次平衡则坏球肯定在 9-12 号中。则此时只剩下 9-12 4个球可能性为 9- 10- 11- 12- 9 10 11 12 这8种可能。接下来将 9 10 11 和 1 2 3称第2次如果平衡则 12 号小球为坏球将12号小球与1号小球称第3次即可确认轻还是重。如果不平衡则如果重了说明坏球重了继续将9和10号球称量重的为坏球平衡的话则11为坏球。如果第1次不平衡则坏球肯定在 1-8号中。则还剩下的可能性是 1 2 3 4 5- 6- 7- 8- 或者 1- 2- 3- 4- 5 6 7 8如果是1 2 3 4 这边重则可以将 1 2 6 和 3 4 5 称如果平衡则必然是 7 8 轻了再称一次7和1便可以判断7和8哪个是坏球了。如果不平衡假定是 1 2 6 这边重则可以判断出 1 2 重了或者 5 轻了为什么呢因为如果是3 4 6-则 1 2 3 4 比 5 6 7 8 重但是 1 2 6 应该比 3 4 5 轻。其他情况同理最多3次即可找出坏球。 下面这个图更加清晰说明了这个原理。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NecW12n8-1682522423467)(null)] 2生男生女问题 题 在重男轻女的国家里男女的比例是多少在一个重男轻女的国家里每个家庭都想生男孩如果他们生的孩子是女孩就再生一个直到生下的是男孩为止。这样的国家男女比例会是多少 解 还是11。在所有出生的第一个小孩中男女比例是11在所有出生的第二个小孩中男女比例是11… 在所有出生的第n个小孩中男女比例还是11。所以总的男女比例是11。 3约会问题 题 两人相约5点到6点在某地会面先到者等20分钟后离去求这两人能够会面的概率。 解 设两人分别在5点X分和5点Y分到达目的地则他们能够会面的条件是 |X-Y| 20而整个范围为 S{(x, y): 0 x 60, 0 y 60}如果画出坐标轴的话会面的情况为坐标轴中表示的面积概率为 (60^2 - 40^2) / 60^2 5/9。 4帽子问题 题 有n位顾客他们每个人给餐厅的服务生一顶帽子服务生以随机的顺序归还给顾客请问拿到自己帽子的顾客的期望数是多少 解 使用指示随机变量来求解这个问题会简单些。定义一个随机变量X等于能够拿到自己帽子的顾客数目我们要计算的是 E[X]。对于 i1, 2 ... n定义 Xi I {顾客i拿到自己的帽子}则 XX1X2…Xn。由于归还帽子的顺序是随机的所以每个顾客拿到自己帽子的概率为1/n即 Pr(Xi1)1/n从而 E(Xi)1/n所以E(X)E(X1 X2 …Xn) E(X1)E(X2)…E(Xn)n*1/n 1即大约有1个顾客可以拿到自己的帽子。 5生日悖论 题 一个房间至少要有多少人才能使得有两个人的生日在同一天 解 对房间k个人中的每一对(i, j)定义指示器变量 Xij {i与j生日在同一天} 则i与j生日相同时Xij1否则 Xij0。两个人在同一天生日的概率 Pr(Xij1)1/n 。则用X表示同一天生日的两人对的数目则 E(X)E(∑ki1∑kji1Xij) C(k,2)*1/n k(k-1)/2n令 k(k-1)/2n 1可得到 k28即至少要有 28 个人才能期望两个人的生日在同一天。 6概率逆推问题 题 如果在高速公路上30分钟内看到一辆车开过的几率是0.95那么在10分钟内看到一辆车开过的几率是多少(假设常概率条件下) 解 假设10分钟内看到一辆车开过的概率是x那么没有看到车开过的概率就是1-x30分钟没有看到车开过的概率是 (1-x)^3也就是 0.05。所以得到方程 (1-x)^3 0.05 解方程得到 x 大约是 0.63。