问题 A: 回文数

时间限制: 1 Sec 内存限制: 32 MB
提交: 1700 解决: 510
[提交][状态][讨论版]</center>

题目描述

我们把从左往右和从右往左念起来相同的数字叫做回文数。例如，75457就是一个回文数。
当然某个数用某个进制表示不是回文数，但是用别的进制表示可能就是回文数。
例如，17是用十进制表示的数，显然它不是一个回文数，但是将17用二进制表示出来是10001，显然在二进制下它是一个回文数。
现在给你一个用十进制表示的数，请你判断它在2~16进制下是否是回文数。

输入

输入包含多组测试数据。每组输入一个用十进制表示的正整数n（0<n<50000），当n=0时，输入结束。

输出

对于每组输入，如果n在2~16进制中的某些进制表示下是回文数，则输出“Number i is palindrom in basis ”，在后面接着输出那些进制。其中i用n的值代替，后面输出的进制中，每两个数字之间空一个。
如果n在2~16进制的表示下都不为回文数，则输出“Number i is not a palindrom”，其中i用n的值代替。

样例输入

17
19
0

样例输出

Number 17 is palindrom in basis 2 4 16
Number 19 is not a palindrom

//整数部分，对X短除取余倒序
//十进制以上要用到英文字母！！！
#include<iostream>
#include<deque>
using namespace std;

bool judge(deque<char> deq);        //是否为回文
deque<char> translate(int number,int basis);        //将数转换成不同进制下的字符串
bool all(bool *able);       //在所有进制中是否为回文数

int main()
{
    int num;
    deque<char> deq;
    while(1)
    {   
        cin>>num;
        if(num==0)      //等于0时退出
            break;
        bool able[17] = { 0 };      //在各个进制下是否为回文数,第一个时不用的

        for(int i=2;i<=16;i++)      //在2到16进制下面判断
        {
            deq=translate(num,i);       //将数字转化成不同进制下面的字符串
            able[i]=judge(deq);     //判断各进制下是否为回文
        }

        bool allbasis=all(able);    //在所有进制中是否为回文数

        if(!allbasis)         //如果n在2~16进制的表示下都不为回文数
            cout<<"Number "<<num<<" is not a palindrom"<<endl;

        if(allbasis)        //如果n在2~16进制中的某些进制表示下是回文数
        {
            cout<<"Number "<<num<<" is palindrom in basis";
            for(int i=2;i<=16;i++)
            {
                if(able[i])
                    cout<<" "<<i;
            }   
            cout<<endl;
        }
    }
    return 0;
}

bool all(bool *able)        //在所有进制中是否为回文数
{
    bool alljudge=false;
    for(int i=2;i<=16;i++)
        if(able[i])
            alljudge=true;      
    return alljudge;
}

deque<char> translate(int number,int basis)     //将数转换成不同进制下的字符串
{
    deque<char> deq;
    int current;
    for(;number>=1;number/=basis)
    {
        current=number%basis;
        if(basis>10)        //大于十进制时有字母了
        {
            if(current>=10)
                deq.push_front(current +'A'-10);
            if(current<10)
                deq.push_front(current +'0');
        }
        if(basis<=10)
            deq.push_front(current+'0');
    }
    return deq;
}

bool judge(deque<char> deq)     //是否为回文
{
    char q,p;
    if(deq.size()==1)
        return true;
    while(deq.size()>1)
    {
        p = deq.front();
        q = deq.back();
        deq.pop_back();
        deq.pop_front();
        if(q!=p)
            return false;
    }
    return true;
}