怎样找到第一个未出现的自然数怎样找到第一个未出现的自然数.pdf

怎样找到第一个未出现的自然数？ by CS Sun 目 录 （一） ………………………………………………… 1 算法思想 （二） ………………………………………………… 4 运行结 果 （三） ………………………………………………… 5 复杂度分析 （四） ………………………………………………… 6 正确性证明 （五） ………………………………………………… 7 实验总结 （六） ………………………………………………… 7 参考文献 §1 算法思想 第一次上机实验要求我们编程解决的问题是：输入一亿个无序排列的自然数（数之间可能 有重复），输出第一个没有在这些数中出现的自然数，或称为未出现的最小自然数。为了解决 这个问题，我们需要设计两个算法：一是生成无序排列的自然数，例如伪随机序列的算法；二 是找到第一个没有在这些数中出现的自然数的算法。 一、产生一串无序序列。其中我们定义两个参数和 ，分别代表产生序列的长度和序列的 范围，可将这串序列和参数表示如下： (,) = 2,4,3,4,7,1,8,5,3,9, … … ( ) { = length ( ) ( ) = max − min 参数和在编写程序时分别对应数组大小和序列范围，为必须设定项，也作为后续分析算 法复杂度的参数变量。在这里我们将 “无序”理解为随机，设计对应随机算法。当然 “无序” 并不完全意味着随机：例如在有序序列中随意插入一些数，打乱序列顺序，这也是一种无序， 但如此序列就不是随机的。很多情况下，算法在随机输入情况下的性能要优于最坏输入情况下 的性能。例如，随机输入下快速排序的时间复杂度为()；但在大部分输入有序，个别无 2 序的情况下，快速排序的时间复杂度反而退化为( ) 。可以说，随机序列比无序序列数学定 义更严格，前者是后者的一个子集。我们把无序输入单纯理解为随机序列是一种简化假设，是 为了方便地生成大规模测试集，但照此分析出的算法复杂度，只是平均情况下的复杂度。为保 证分析的完整性，最后也了考虑该随机算法在最坏无序输入情况下的算法复杂度。 在Java 环境下，编写一段产生伪随机序列长度为 、数据范围为 的程序。我们使用Math 类，它包含用于执行基本数学运算的方法，如初等指数、对数、平方根和三角函数等。其中用 到两个方法，一是random ，它返回带正号的 double 值，该值大于等于 0.0 且小于 1.0，是一 个伪随机选择的数，在该范围内近似均匀分布。二是round(double a) ，它返回一个最接近参数 的long ，将结果舍入为整数。生成随机序列伪代码如下： Algorithm 1 Generator of Random Numbers in range (0, ) 1 RANDOM (Array[], , ) 2 ← number 3 ← range 4 for ← 0 to − 1 5 Array[] = Math.round