算法(4th ed)(65):基础——基础编程模型 3.15

阅读数:18 2019 年 10 月 30 日 07:09

算法(4th ed)(65):基础——基础编程模型 3.15

(实验题)

1.1.35 模拟掷骰子。以下代码能够计算每种两个骰子之和的准确概率分布:

复制代码
int SIDES = 6;
double[] dist = new double[2*SIDES+1];
for (int i = 1; i <= SIDES; i++)
for (int j = 1; j <= SIDES; j++)
dist[i+j] += 1.0;
for (int k = 2; k <= 2*SIDES; k++)
dist[k] /= 36.0;

dist[i] 的值就是两个骰子之和为 i 的概率。用实验模拟 N 次掷骰子,并在计算两个 1 到 6 之间的随机整数之和时记录每个值的出现频率以验证它们的概率。N 要多大才能够保证你的经验数据和准确数据的吻合程度达到小数点后三位?

1.1.36 乱序检查。通过实验检查表 1.1.10 中的乱序代码是否能够产生预期的效果。编写一个程序 ShuffleTest,接受命令行参数 MN,将大小为 M 的数组打乱 N 次且在每次打乱之前都将数组重新初始化为a[i] = i。打印一个 M×M 的表格,对于所有的列 j,行 i 表示的是 i 在打乱后落到 j 的位置的次数。数组中的所有元素的值都应该接近于 N/M

1.1.37 糟糕的打乱。假设在我们的乱序代码中你选择的是一个 0N-1 而非iN-1 之间的随机整数。证明得到的结果并非均匀地分布在 N! 种可能性之间。用上一题中的测试检验这个版本。

1.1.38 二分查找与暴力查找。根据 1.1.10.4 节给出的暴力查找法编写一个程序BruteForceSearch,在你的计算机上比较它和 BinarySearch 处理 largeW.txt 和 largeT.txt 所需的时间。

1.1.39 随机匹配。编写一个使用 BinarySearch 的程序,它从命令行接受一个整型参数 T,并会分别针对 N=103104105106 将以下实验运行 T 遍:生成两个大小为 N 的随机 6 位正整数数组并找出同时存在于两个数组中的整数的数量。打印一个表格,对于每个 N,给出 T 次实验中该数量的平均值。

评论

发布