解2： 还可以采用前面随机排列数组的思想，先对前 m 个数字进行随机排列，然后排序这 m 个数字并输出即可。代码如下：
void randomMArray(int n, int m) { int i, j; int *x = (int *)malloc(sizeof(int) * n); <span>for</span> (i = 0; i < n; i++) x[i] = i; // 随机数组 <span>for</span> (i = 0; i < m; i++) { j = randInt(i, n-1); swapInt(x, i, j); } // 对数组前 m 个元素排序 <span>for</span> (i = 0; i < m; i++) { <span>for</span> (j = i+1; j>0 && x[j-1]>x[j]; j--) { swapInt(x, j, j-1); } } <span>for</span> (i = 0; i < m; i++) { <span>printf</span>(<span>"%d "</span>, x[i]); } <span>printf</span>(<span>"\n"</span>);}
复制代码
题： 已知一个函数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); <span>return</span> 1 + (idx-1) % 10;}
复制代码
由于row范围为1-7，col范围为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) k=1 = (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-3，rand7 产生 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 - 63 idx = b + (a-1)*7; if (idx <= 60) return 1 + (idx-1)%10; a = idx-60; b = randInt(1, 7); // get uniform dist from 1-21 idx = 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)。