回文数专题 ++++++++++ :strong:`回文`\ （palindrome）是指这样一种文字，它从左到右读和从右到左读是一样的，例如英语单词\ :emphasis:`level`\ 。我们的汉语里有许多优美的回文句，比如“雾锁山头山锁雾，天连水尾水连天”、“处处飞花飞处处，潺潺碧水碧潺潺”。甚至还有神奇的回文诗词，比如： :strong:`菩萨蛮·回文夏闺怨` [宋] 苏轼 :emphasis:`柳庭风静人眠昼。昼眠人静风庭柳。` :emphasis:`香汗薄衫凉。凉衫薄汗香。` :emphasis:`手红冰碗藕。藕碗冰红手。` :emphasis:`郎笑藕丝长。长丝藕笑郎。` :strong:`梅` [清] 张奕光 :emphasis:`香暗绕窗纱，半帘疏影遮。` :emphasis:`霜枝一挺干，玉树几开花。` :emphasis:`傍水笼烟薄，隙墙穿月斜。` :emphasis:`芳梅喜淡雅，永日伴清茶。` :emphasis:`茶清伴日永，雅淡喜梅芳。` :emphasis:`斜月穿墙隙，薄烟笼水傍。` :emphasis:`花开几树玉，干挺一枝霜。` :emphasis:`遮影疏帘半，纱窗绕暗香。` 虽然英语的词法和语法决定了英文只有回文词，构不成回文句，但是如果把句子中单词和单词之间的空格去掉，英语也可以有正着看和反着看一样的回文句。例如拿破仑被流放到厄尔巴岛时说的一句话，“在我看到Elba岛之前我曾所向无敌”，它的英文就是英语中最著名的一句回文句：:emphasis:`Able was I ere I saw Elba`\ 。 类似的，正读反渎都一样的整数就被称为\ :strong:`回文数`\ 。例如1，11，121，2002，20199102是回文数。而12，132，2020这些就不是回文数。 一般来说回文数是指自然数，即0和正整数。负数由于前面有一个负号，所以绝不能是回文数。但是有些算法题里特别说明，对于负数，如果其绝对值是回文数那么就算它也是回文数。像这样的特殊说明可能并没有用文字说出来，而是在样例中给了一个例子来说明，审题一定要仔细！还有一些题目会特别认定若去除小数点后剩余的数字成为回文数则也认为这个小数是回文数，例如 12.21。这些特殊情况只是拓宽了回文数的认定范围，回文数本身的规则并没有什么不同，用于处理自然数回文数的算法稍加修改就可以适应这些负数或小数回文数，所以这里我们不打算对它们做专门介绍，我们的讨论范围仍然是自然数。 回文数有两个特点非常有用。 1. 不证自明，所有的一位数必然是回文数：0, 1, 2, 3, 4, 5, 6, 7, 8, 9。 2. 偶数位的回文数，除了11以外全部是合数，它们都有因数11。 第二个性质的证明并不难，把一个回文数按十进制数的占位表示法在各位上展开即可证明，用数学归纳法来证明比较简单。 首先考虑两位回文数，一共只有9个：11，22，33，44，55，66，77，88，99。显然除了11是质数以外，其他都是合数而且有因数11。 再看四位回文数的情况，任何一个四位回文数都可以表示为： .. math:: \overline{abba}=1000a+100b+10b+a=1001a+110b=11(91a+10b) 所以四位回文数一定能被11整除。 对于更多位数的偶数位回文数，设任意 :math:`2k` 位回文数 :math:`A_{2k}=\overline{a_k\cdots a_1a_1\cdots a_k}` 都是可以被11整除的，那么 :math:`2k+2` 位的回文数都可以表示为 :math:`A_{2k+2}=\overline{a_{k+1}A_{2k}a_{k+1}}=(10^{2k+1}+1)\cdot a_{k+1}+A_{2k}\cdot 10`\ 。由于 :math:`A_{2k}` 能被11整除，我们只需证明 :math:`10^{2k+1}+1` 能被11整除就可以了。对这个数字的表达式做以下变形处理： .. math:: 10^{2k+1}+1=10^{2k+1}-10+11=10\times(10^{2k}-1)+11=10\times\overline{\underbrace{9\cdots9}_{2k个9}}+11 所以它能被11整除。所以 :math:`2k+2` 位回文数也可以被11整除。 这就用数学归纳法证明了所有偶数位的回文数除了11以外全都是合数。 整数取位 ^^^^^^^^ 取一个十进制整数中指定位上的数是最基本的整数算法，不光是回文数算法的基础，也是所有数值算法的基础。 整数取位的原理非常简单。一个十进制整数从右到左各位一般依次称作“个位、十位、百位......”，或者用序号叫做“第1位、第2位、第3位......”。每一个位的序号和这个位上的\ :strong:`基`\ 是对应的，第 :math:`k` 位的基就是 :math:`10^{k-1}`\ 。例如个位是第1位，个位的基就是10\ :superscript:`0`\ =1，千位是第4位，它的基是10\ :superscript:`3`\ =1000。 对于 :math:`n` 位的十进制整数，要取它的个位数很简单，除10取余就是。如果要取其第 :math:`k` 位上的数，只要将它从第 :math:`k` 位和第 :math:`k-1`\ 的中间断开，舍去右边部分，取左边那个整数的个位数就可以了。例如取整数1234的个位数，只要除10取余就可以得到个位数4，如果要取百位数，百位是第3位，所以先除以10\ :superscript:`2`\ =100，得到的商就是从百位和十位中间断开后的左边部分那个整数12，对其除10取余得个位数2，它就是1234的百位数。 所以取整数第 :math:`k` 位数的算法是：将原数除以 :math:`10^{k-1}` 取商，然后对商除10取余，就得到了原数的第 :math:`k` 位数。对于负数，C++取余运算的规则将使得取到的数也是负数（或0），例如取-876的十位数将得到-7。有时候这个特点非常有用。 使用上述数学方法，很容易编写出整数取位的C++函数。 .. literalinclude:: ../../codes/213_palindrom.cpp :language: c++ :lines: 3-7 整数反转 ^^^^^^^^^^^^ 所谓整数反转就是把一个整数的各个位反方向排列后形成一个新的整数。例如123变成321，1023变成3201。需要注意的是，如果原数的个位或最后几位为0的，在反转之后这些0就没有了，所以反转一个整数得到的结果和原数有可能位数不同。例如1230反转后变成321，100反转后变成1。另外，负数反转仍然得负数，只是它的绝对值进行了反转。例如-123反转后变成-321，-1200反转后变成-21。 用数学语言来描述这个过程，反转任意一个非负整数 :math:`\overline{a_na_{n-1}\cdots a_2a_1}` 就是把它变成 :math:`\overline{a_1a_2\cdots a_{n-1}a_n}`\ ，这个数的值用十进制占位计数法的规则计算，就等于 :math:`10^{n-1}\cdot a_1+10^{n-2}\cdot a_2+\cdots+10^1\cdot a_{n-1}+10^0\cdot a_n`\ 。从这个关系式出发我们可以归纳出反转任意非负整数的算法：把结果先预设为原数的第1位（个位），然后从第2位开始逐位向前取数，每取出一个位上的数，就把当前的结果乘以10再加上取得的数，这样循环下去直到原数的最高位为止，结果就是原数的反转数。 以反转123为例，首先我们让结果等于个位数3。第一轮循环取原数的第2位上的数2，修正结果值为30+2=32；第二轮循环取原数第3位上的数1，修正结果为320+1=321；原数最高位取完，算法结束，得到最终的结果321。 对于负整数，由于前面介绍的C++（以及其他绝大多数计算机语言）负数取余规则，上述算法仍然适用。以反转-1234为例，首先我们通过除10取余获得初始的结果值-4。第一轮循环取第2位，按照C++运算规则将取到-3，修正结果值为-40+(-3)=-43；第三轮循环取第3位得到-2，修正结果为-430+(-2)=-432；第四轮取第4位得到-1，修正结果为-4320+(-1)=-4321。循环结束，得到最终结果-4321，正确！ 上代码。 .. literalinclude:: ../../codes/213_palindrom.cpp :language: c++ :lines: 9-14 .. note:: 这段代码的循环条件值得关注，它使用了一个自除10表达式 ``n /= 10``\ ，这个表达式的值是 ``n`` 除以10之后得到的商。这样做使得程序不需要在循环体内去完成 ``n`` 的自除，所以循环体内只需要一条修正结果的语句就够了。之所以可以这么做是因为我们把结果的初始值设为了原数的个位数，而不是很多整数反转算法里采用的初始值0。请想一想如果我们把结果的初始值设为0，这个算法和代码要怎么改变？ .. warning:: 有没有发现我们的返回值用了 ``long long`` 类型而不是和原数一样的 ``int`` 类型？这是初学者特别容易疏忽的一点。如果返回值也用 ``int`` 类型，那么可能导致结果超过取值范围的情况，术语叫溢出。因为 ``int`` 的最大可取值仅是21亿多，而不是9,999,999,999，所以如果原数恰为十位数而且末尾几位的数值比较大就可能导致反转结果溢出。例如1,234,567,123，反转后得到的数3,217,654,321就溢出了。 回文数判断 ^^^^^^^^^^ 于是，判断一个整数是不是回文数已经成了一个无比简单的任务。先反转，检查反转前后是不是相等。如果相等就是回文数（包括特殊情形下对负数的扩展），否则就不是。 .. literalinclude:: ../../codes/213_palindrom.cpp :language: c++ :lines: 9-19 下一节我们将综合应用已经学过的这些关于质数和回文数的知识来完成一个普及组难度的竞赛题：寻找一定范围内的回文质数。