33.00s和14.27s，两个截然不同的运行时间值，两次提交尝试解决素数回文问题，终于搞定了！用两个字形容’恼人’！算法不复杂，就是要求时间很’紧’，大部分工作都在考虑着如何缩短运行时间。桃花在冷空气袭来的日子都开了，我的心也算可以放下了！
最近项目吃紧，连续两天没有做ACM习题了，手都有些生了^_^！按照Volume1的习题顺序，该轮到1004题了！这是一道关于’素数回文(Prime Palindromes)’的习题，源自’USACO’，估计是什么比赛吧！大家一定都知道什么是素数，或者又叫质数！那么什么是回文(Palindromes)，不用定义，举几个例子大家就明白了，如121、1331、14741、89098等等看起来对称的数都叫做回文数，具体的定义或者数学上的定义我也没找到，好像对解决此题关系也不大！
Ok!我们来看一下题目，题目很简单，找出输入的两个数之间的所有素数回文，并按照数值顺序输出，每行一个数！要求：运行时间在15秒以内。输入值范围[5, 1000000000]。
如果不估计时间，大家脑中一定选中了’遍历’这种方案，而达到目标前所要解决的两个问题包括如何判断一个数是否是一个素数和如何判断一个数是否为一个回文数？
如何判断素数？这个在大学学习C语言的时候好像是习题，不过算法早已经忘到了’九霄云外’，这样自己就顺手写了一个宏：
#define IS_PRIMER(i) \
((i <= 10) \
? (i == 2 || i == 3 || i == 5 || i == 7) \
: (((i % 2 == 0) || (i % 3 == 0) || (i % 5 == 0) || ( i % 7 == 0)) ? 0 : 1))
用几个数测了一下，屡试不爽！为了更加精确的测试，还是到网上找一个素数表吧！这样有参照的测试势必比较准确无误。试着用这个宏找出500以内的所有素数，发现与素数表中的个数不符，仔细查查，一眼就看到了121这个数，按照我的算法，它就是个’素数’了，但实际上它还能被11所整除，别忘了素数的定义："不能被1和自己之外的任何数整除"，看来我的算法是’漏洞百出’，不过在100之内它是有效的，起码算是个’Uncompleted Algorithm’^_^。重新修整一下，改进版如下：
int is_primer(int x) {
int i;
for (i = 2; i <= sqrt(x); ++i) {
if (x % i == 0) {
return 0;
}
}
return 1;
}
这种算法也是网上常见的算法，如果和外层的遍历一起来看，这是个接近O(n^2)的算法，显然性能不高！不过目前还少有好算法公布在网上，就暂用这个吧，我也想不出来什么好方法！也许需要好的数学功底才能提高该算法性能！
如何判断回文？这就是个’见仁见智’的问题了。这里提供两种方案，感觉性能上差不多，各有千秋：
[方案一]
/* 获取一个数i的位数n */
#define GET_DIGITS(n, i) do { \
n = 1; \
while (i >= pow(10, n)) { \
n++; \
} \
} while(0)
/*
* 从外到内，比较每一个对称位上的数值是否相等
* 如果全相等则是回文，否则不是。
*
* ! 这种方法还是很容易想出来的
*/
int is_palindrome(int x) {
int i = 0;
int j = 0;
int n = 0;
int high = 0;
int low = 0;
GET_DIGITS(n, x);
j = (n % 2) ? ((n-1) / 2) : (n / 2);
for (i = 1; i <= j; ++i) {
low = x % (int)(pow(10, i));
high = x/(pow(10, n-i));
if (low != high) {
return 0;
}
}
return 1;
}
[方案二]
/*
* ‘回文数’再造
* 从低位到高位，按’低位 * 10 + 高位’累加的方式得到一个数
* 如果该最终数值与原数一致，则为回文数，否则不是
*
* 这个方法对后面的方法还是很有启发的！
*/
int is_palindrome(int x) {
int rv = 0;
int i = x;
while (i != 0) {
rv = rv * 10 + i % 10;
i = i / 10;
}
return rv == x;
}
现在两个难题都解决了，我们只需要遍历加判断即可。那么是先判断素数还是先判断回文呢？看起来判断素数较浪费时间，那我们先判断回文吧！第一次提交代码，不出所料，运行时间33s(我想不止33s，也许33s只是服务器的一个时间上限，大于该时间的统一显示为33s)。看来我们的重新考量一下我们的方案了！这种遍历+判断的方法无论如何是不能够蒙混过关的了^_^。
那么怎么来做呢？方案一是拿来一个数，我们来判断是否是回文，这样绝大部分的数都不是回文数，那么这些判断也都是无效的，但却占用了大量的时间，我们能不能尽量让我们每步操作都是生成结果之路上有效的一步呢？我们来尝试自己生成一定范围内的回文数。回文数组成是有一定的规律可循的。现在我们可以将问题集中在’如何生成位数为n的所有回文数’上！我们举几个例子就能看得出来：
[例子]
6446 — 我们可以看成两个部分 — 高二位的64和低二位的46互为反序数，我们也可以理解为高二位的值随着低二位的变化而变化；
64546 — 我们可以看成三个部分 — 高二位的64和低二位的46互为反序数，再加上中间的一个独立变化的值，我们也可以理解为高二位的值随着低二位的变化而变化；中间值独立变化；
可以看出我们的算法可以将处理分为两类：奇数和偶数。
1、如何生成位数为偶数位的所有回文数？
算法名称：gen_even_palindrome
输入项：n (回文数的位数)
算法步骤：
gen_even_palindrome(n) {
j = n/2; /* j为独立变化的低位部分的位数 */
k = (10^j – 1); /* k为独立变化的低位部分的上限值 */
for (i = 1; i <= k; ++i) {
/*
* 这里的i就是低位部分独立变化的值
*/
if (i % 10) {
/* 如果 i = 10、1000等这些10^n的数，它们是没有回文的 */
continue;
}
rv = _gen_even_palindrome(i, n); /* rv就是一个n位回文数 */
}
}
_gen_even_palindrome(x, n) {
int i = x;
int j = 1;
int rv = 0;
/*
* 利用低位部分的信息，造出高位部分的数值
*/
while (i != 0) {
rv += ((i % 10) * pow(10, n-j));
i = i / 10;
j++;
}
/* 最后的回文数还要加上低位部分的数 */
rv += x;
return rv;
}
2、如何生成位数为奇数位的所有回文数？
算法名称：gen_odd_palindrome
输入项：n (回文数的位数) n > 1 对n = 1作特殊处理便是
算法步骤：
gen_odd_palindrome(n) {
j = (n + 1)/2; /* j为独立变化的低位部分的位数 *
/
k = (10^(j-1) – 1); /* k为独立变化的低位部分的上限值 */
for (h = 0; h <= 9; ++h) { /* 中间位独立变化 */
for (i = 1; i <= k; ++i) {
/*
* 这里的i就是低位部分独立变化的值
*/
if (i % 10) {
/* 如果 i = 10、1000等这些10^n的数，它们是没有回文的 */
continue;
}
rv = _gen_odd_palindrome(i, h, n); /* rv就是一个n位回文数 */
}
}
}
_gen_odd_palindrome(x, mid, n) {
int i = x;
int j = 1;
int rv = 0;
/*
* 利用低位部分的信息，造出高位部分的数值
*/
while (i != 0) {
rv += ((i % 10) * pow(10, n-j));
i = i / 10;
j++;
}
/* 最后的回文数还要加上中间数和低位部分的数 */
rv += mid * pow(10, (n-1)/2);
rv += x;
return rv;
}
至此，我们算是解决了如何生成回文数的问题了，不过目前还有一点不能满足，那就是按照数值顺序来输出回文素数，不知道大家发现没有，上面的回文数生成算法不能保证按照数值顺序生成会文数，所以我们还要再动动脑筋！
这里不妨尝试一下作弊！^_^ 由于回文数生成算法不能保证按照数值顺序输出回文数，那么我们势必需要记下来已经生成的回文数，那么到底有多少回文素数需要记下来呢？我们可以利用前面提到过的’遍历’方案在本地计算一下，结果是不到10000个，那么OK！我们就分配一个大数组，并用一个static global variable记下当前数组使用情况，待所有的回文素数都写入数组，我们对该数组进行一次quick sort，这又需要有个quick sort算法(O(nlogn)级别的，简单快速是我选它的原因)，不过这个比较容易，这里也不详述了。
把这个’回文生成’解决方案提交后，得出14.27s的结果，状态: Accepted。对了千万别忘了，这里还加了些优化，比如不存在位数为6的素数回文，所以当判断n = 6就直接返回，省着走冤枉路！14.27s属于刚及格范畴！该题肯定还有更快的解法，由于太烦，这里就浅尝辄止了！^_^
评论