更新时间:2022-09-02 23:25:07
昨天在博问里面看到的一道算法题,原题如下:
给出一个N(0<N<20),在1~N的所有排列中,满足相邻两个数之和是素数的排列输出
比如当N = 4时,满足条件的素数环有如下几种
1 2 3 4
1 4 3 2
2 1 4 3
2 3 4 1
3 2 1 4
3 4 1 2
4 1 2 3
4 3 2 1
常规的做法是,找出这N个数的所有排列,然后依次检查每个排列,筛选出符合条件的排列即可。求排列可以用回溯法的排列树模型,筛选就按照题目要求即可,判断素数的算法也有很多,选择一个即可。注意不要忘记最后一个元素和第一个元素的检测。优化前的代码如下:
题目不难,做完以后,我发现有很多可以优化的地方,可以大幅提高速度。
1. 首先,找出所有排列并逐个检查,这是很浪费时间的,更高效的方法是,一边排列一边检查,这样可以提早发现不满足条件的候选解,提早剪枝,避免不必要的搜索,例如当N=10时,排列到1234的时候,满足条件,下一次选择5,序列变为12345,由于4 + 5 = 9,非素数,所以后面不用再排列了,也就是从当前位置开始,以5为根的子树可以不用再搜索了,直接跳到6,序列变为12346,由于4 + 6 = 10,非素数,同样舍弃6为根的子树。下一次搜索变成12347,这回满足条件,继续排列下一个元素,如此直到10个元素全部排列完成。代码如下:a是储存排列的数组,n是元素个数,t用来控制递归过程。
2. 再看题目的输入范围,1 < N < 20,由于输入规模比较小,所以考虑使用查表法来判定素数,查表法是典型的以空间换时间的方法。20以内两个数之和最大是18 + 19 = 37,而37以内的素数分别是2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,我们可以定义一个38个元素的数组,以i为数组下标。当i为素数时,令a[i] = 1,否则a[i] = 0。这样,要判断一个数是否为素数时,直接判断a[i]是否为1即可。对应的数组如下:
判断i是否为素数的代码也很简单
3. 再考虑输入的特点,如果输入N是奇数的话,由于起点从1开始,那么1-N之间一共有N / 2个偶数,N / 2 + 1个奇数,也就是奇数的个数比偶数多一个,那么把这N个数排成一个环,根据鸽巢原理,必然有两个奇数是相邻的,而两个奇数之和是偶数,偶数不是素数,所以我们得出结论,如果输入N是奇数的话,没有满足条件的排列。这样当N是奇数的时候,直接返回即可。如果1-N之间每个数输入的几率相同,这个判断可以减少一半的计算量。
4. 扩展一下第三点,可以发现,任何一个满足条件的排列都有一个共同点:相邻的两个数奇偶性必然不同,原因是:两个奇数之和或者两个偶数之和都是偶数,而偶数一定不是素数,所以在选取当前元素的时候,比较一下它和前一个元素的奇偶性。再做决定,可以减少一部分计算量。
由 于奇数 + 偶数 = 奇数, 而奇数的二进制表示中,最低位是1, 所以有下面的代码, 其中curValue是当前值, a[lastIndex]是前一个值.
经过上面的优化,代码如下,应该会比原来快很多。还有什么地方可以优化么?欢迎讨论!
本文转自zdd博客园博客,原文链接:http://www.cnblogs.com/graphics/archive/2010/03/27/1698403.html,如需转载请自行联系原作者