pascal中级教程第七章搜索

《pascal中级教程第七章搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、pascal中级教程第七章搜索第七章7.1搜索最多因子数divisors.???（pas,c,cpp）divisors.exedivisors.indivisors.out源程序名可执行文件名输入文件名输出文件名【问题描述】数学家们喜欢各种类型的有奇怪特性的数。例如，他们认为945是一个有趣的数，因为它是第一个所有约数之和大于本身的奇数。为了帮助他们寻找有趣的数，你将写一个程序扫描一定范围内的数，并确定在此范围内约数个数最多的那个数。不幸的是，这个数和给定的范围的都比较大，用简单的方法寻找可能需要较多的运行时间。所以请确定你的算法能在几秒内完成最大范围内的扫描。【输入】只有一

2、行，给出扫描的范围，由下界L和上界U确定。满足2≤L≤U≤1000000000。【输出】对于给定的范围，输出该范围内约数个数D最多的数P。若有多个，则输出最小的那个。请输出“BetweenLandU，PhasamaximumofDdivisors．”，其中L，U，P和D的含义同前面所述。【样例】divisors.indivisors.out10002000Between1000and2000,1680hasamaximumof40divisors.【知识准备】深度优先搜索的基本实现方法及剪枝的基本概念。【算法分析】本题的要求是，求出一个给定区间内的含因子数最多的整数。首先，有

3、必要明确一下如何求一个数的因子数。若一个数N满足N=P1N1·P2N2·P3N3·…·PmNm，其中P1,P2,…,Pm是N的m个质因子。则N的约数个数为(N1+1)·(N2+1)·(N3+1)·…·(Nm+1)。这一公式可以通过乘法原理来证明。有了求因子数的公式后，最容易想到的算法就是，枚举区间内的每个整数，统计它们的约数个数。这个算法很容易实现，但是时间复杂度却相当高。因为区间中整数的范围是1～1000000000，整个枚举一遍并计算因子数的代价约为109×(109)0.5=1013.5。这个规模是无法忍受的。所以，我们需要尽量优化时间。分析一下枚举的过程就会发现，如果我

4、们分别枚举两个数n和p·n（p为一相对较大的质数），那么我们将重复计算两次n的因子数。其实，如果枚举顺序得当的话，完全可以在n的基础上去计算p·n，而如果能在n的基础上计算p·n，就相当于计算p·n的因子数只用了O(1)的时间。这是一个比较形象的例子，类似的（可能相对更复杂一些）重复计算在枚举过程中应该是普遍存在的。这就是枚举效率低的根本所在。为了解决这一重复，我们可以选取另一种搜索顺序——枚举质因子。这样的搜索顺序可以避免前面所说了类似n和p·n的重复计算。定义number为当前搜索到的数。初始时，令number=1，然后从最小的质数2开始枚举，枚举因子中包含0个2、1个2

5、、2个2、…、k个2的情况……直至number·2k大于区间的上限(max)。对于每个“2k的情况”，令number:=number*2k，在这个基础上，再枚举因子3的情况。然后在3的基础上枚举因子5的情况，然后是7的情况……整个过程是一个深度搜索的过程，搜索的过程中，利用前面提到的求因子数的公式可以算出当前的number的因子数供下一层枚举继承。当number大于等于区间下限(min)时，我们就找到了一个区间内的数(枚举的过程已保证number不超过上界)。所有枚举得到的区间内的数中，因子数的最大值就是我们要求的目标。这样的枚举完全去除了重复计算，但是这还是不够的，因为光1

6、～1000000000内的数每枚举一遍就有109个单位的操作。所以，我们还需要找到一些剪枝的方法，进一步优化时间。我们看到，如果当前搜索状态为(from,number,total)，其中，from是指当前枚举到的质因子（按从小到大枚举），total是指number中包含的因子数。那么剩下的因子数最多为q=logfrommax/number，这些因子组成的因子个数最大为2q。因此，当前所能取到的（理想情况）最大约数个数就是total·2q。如果这个数仍然无法超过当前最优解，则这一分支不可能产生最优解，可以剪去。此外，如果[(min-1)/number]=[max/number]

7、，则表示以当前状态搜索下去，结果肯定不在区间内了，就无法产生合法解，也可剪去。不过，这一剪枝作用不是很大，因为即使不剪，再搜索一层也就退出了。以上两个剪枝，前一个是最优化剪枝，后一个是合法性剪枝。相比较而言，前一个剪枝的作用要大得多。下面我们用平摊分析的方法来讨论一下搜索的复杂度。由于枚举的过程中没有重复计算，每枚举一个质因子，都可以得到一个不同的number(number≤max)，所以可以将每一个单位的枚举质因子的代价与一个不超过max的number对应，并且还可在两者之间建立双射。不同的numbe