本节书摘来自华章计算机《算法基础》一书中的第2章，第2.8节，作者：（美）罗德·斯蒂芬斯（Rod Stephens）著，更多章节内容可以访问云栖社区“华章计算机”公众号查看
2.8 练习
星号表示特别困难的问题。
1.写一个使用一个均匀的六面骰子来产生硬币翻转的算法。
- 2.1.1节中的第3大点“从有偏的数据源中获得公平”中解释了通过翻转硬币两次，你能够从有偏的硬币中获得公平的硬币。但有时做两个翻转不能达到目地，所以需要重复这个过程。假设正面向上的结果占了四分之三而背面向上的结果占了四分之一。在这种情况下，进行两次翻转后没有得到公平硬币而要再试一次的概率是多少？
3.再考虑练习题2中介绍的硬币。这时假设你错了，因为硬币其实是均匀的，但仍然使用那个从偏颇的硬币来获得公平硬币的翻转的算法。在这种情况下，在进行两次翻转后没有得到结果而需要再试一次的概率是多少？
4.写一个算法使用一个不均匀的六面骰子生成1到6之间的公平值。这个算法的效率有多高？
5.写一个算法，从包含N个项的数组中选取M个随机值（其中M≤N）。它的运行时间复杂度是多少？这个算法如何应用于下文描述的例子—把书给从100个人中挑选出来的五个人？如果有10 000个人呢？
6.写一个算法来解决给玩家发五张牌的扑克程序。每轮发一张牌给每个玩家直到所有的玩家都有五张牌，或者轮流地给每个玩家一次性发五张牌，这两种方法有区别吗？
- 编写一个程序，模拟掷两个六面的骰子，并绘制条形图或曲线以展现每个投掷结果所产生的次数。将每个值出现的次数与之前所期望的两个均匀的骰子在那样多的投掷次数后会出现的次数作比较。在结果符合预期之前，需要做多少次实验？
- 如果最开始A＜B，那么欧几里得算法会怎么样执行呢？
- 整数A和B的最小公倍数（LCM）是A和B两个数的共有倍数中最小的一个。如何使用GCD来计算LCM？
10.本章节中所描述的快速求幂算法是在十分理论化的水平上的。写一个能够实际操作的细节一些的算法。 - 如何改写在练习10中所编写的算法来实现快速模幂运算？
- *写出一个程序来计算一系列伪随机数的GCD，并且绘制曲线图描述计算两个数的GCD所需要的步骤数和这两个数的均值之间的关系。是否结果成对数关系？
13.下面的伪代码显示了埃拉托色尼的筛子如何越过了素数next_prime的倍数：
划掉的第一个值是next_prime*2，但是要知道，这个数值已经划掉了，因为它是2的倍数；该算法所做的第一件事就是划掉2的倍数。如何修改此循环，以避免重新访问这个值和许多其他已经被划掉的值？
- *在被称为卡迈克尔数的无穷合数集中，每个互素的数中相对较小的数是一个费马谎言。换句话说，如果对每个n（其中1＜n＜p且GCD(p, n)＝1）是费马骗子。那么p是一个卡迈克尔数，写一个算法，列出1和10 000之间的卡迈克尔数和他们的素因子。
15.当使用矩形规则，一些矩形的一部分落在曲线上方，增加了估计的区域的面积，而一些矩形的部分在曲线以下，减少了估计的面积。如果用矩形的中点的函数值作为矩形的高度，而不是用矩形左边缘的函数值，那么会产生什么情况？编写一个程序来检查这个假设。 - 可以使用自适应蒙特卡罗积分设计一个程序吗？该算法是否高效的呢？
- 写一个概要算法，用于使用蒙特卡罗积分找到一个三维形状的体积。
- 如何用牛顿法来找到两个函数相交的点？