求回文数

skymens

打印所有不超过n（取n<256）的其平方具有对称性质的数（也称回文数）。


问题分析


对于要判定的数n计算出其平方后（存于a），按照“回文数”的定义要将最高位与最低位、次高位与次低位……进行比较，若彼此相等则为回文数。此算法需要知道平方数的位数，再一一将每一位分解、比较，此方法对于位数已知且位数不是太多的数来说比较适用。


此问题可借助数组来解决。将平方后的（a的）每一位进行分解，按从低位到高位的顺序依次暂存到数组中，再将数组中的元素按照下标从大到小的顺序重新将其组合成一个数众（如n=15，则a=225且k=522），若k等于n×n则可判定n为回文数。


算法设计


从低位到高位将某一整数拆分。对于一个整数（设变量名为a）无论其位数多少，若欲将最低位拆分，只需对10进行求模运算a%10，拆分次低位首先要想办法将原来的次低位作为最低位来处理，用原数对10求商可得到由除最低位之外的数形成的新数，且新数的最低位是原数的次低位，根据拆分最低位的方法将次低位求出a/10、a%10，对于其他位上的数算法相同。


利用这个方法要解决的一个问题就是，什么情况下才算把所有数都拆分完？当拆分到只剩原数最高位时（即新数为个位数时），再对10求商的话，得到的结果肯定为0，可以通过这个条件判断是否拆分完毕。根据题意，应将每次拆分出来的数据存储到数组中，原数的最低位存到下标为0的位置，次低位存到下标为1的位置……依次类推。

[C] 纯文本查看 复制代码

for (i=0; a!=0; i++)
{
    m[i] = a % 10;
    a /= 10;
}

将数组中元素重新组合成一新数。拆分时变量a的最高位仍然存储在数组中下标最大的位置，根据“回文数”定义，新数中数据的顺序与a中数据的顺序相反，所以我们按照下标从大到小的顺序分别取出数组中的元素组成新数k，由几个数字组成一个新数时只需用每一个数字乘以所在位置对应的权值然后相加即可，在编程过程中应该有一个变量t来存储每一位对应的权值，个位权值为1，十位权值为10，百位权值为100……，所以可以利用循环，每循环一次t的值就扩大10倍。对应程序段如下：

[C] 纯文本查看 复制代码

for( ; i>0; i--)
{
    k += m[i-l] * t;
    t *= 10;
}

源代码：

[C] 纯文本查看 复制代码

#include<stdio.h>
int main()
{
    int m[16], n, i, t, count=0;
    long unsigned a, k;
    printf("No.    number     it's square(palindrome)\n");
    for( n=1; n<256; n++ )  /*穷举n的取值范围*/
    {
        k=0; t=1; a=n*n;  /*计算n的平方*/
        for( i=0; a!=0; i++ )  /*从低到高分解数a的每一位存于数组m[1]~m[16]*/
        {
            m[i] = a % 10;
            a /= 10;
        }
        for(; i>0; i--)
        {
            k += m[i-1] * t;  /*t记录某一位置对应的权值 */
            t *= 10;
        }
        if(k == n*n)
            printf("%2d%10d%10d\n", ++count, n, n*n);
    }
    return 0;
}

运行结果

No.    number     it's square(palindrome) 1            1               1 2            2               4 3            3               9 4           11             121 5           22             484 6           26             676 7          101           10201 8          111           12321 9          121           14641 10          202           40804 11          212           44944