问题描述：
试设计一个算法测试一个串t的值是否为回文，即正读和倒读相同。
给定一个k进制数a，其倒置相加运算⊕是将a 的各位数字倒置后再与a 相加。例如，
当a=56 时，⊕a=56+65=121。有些数经过若干次倒置相加运算就成为一个回文数。例如，
56 经过1 次倒置相加运算就变成回文数121。

编程任务：
给定一个k进制数a，编程计算最少经过多少次倒置相加运算，a 变成回文数。
«数据输入：
由文件input.txt 给出输入数据。第一行有2 个正整数k 和n，k 表示给定的数是k 进制
数，2≤k≤16；n表示执行倒置运算的次数上界，如果经过n次倒置运算，还没有得到回文
数，则输出“No solution！”。第2 行是给定的k进制数a。

结果输出:
将计算出的最少倒置运算次数和最终得到的回文数输出到文件output.txt。第1 行是最
少倒置运算次数，第2 行是最终得到的回文数。
输入文件示例 输出文件示例
input.txt
10 15
167
output.txt
11
8855558


//done by smallrain,05,4,8  , 算法与数据结构,第五章,串,回文问题

#include<iostream>
#include<fstream>
#include<string>
#include"time.h"
using namespace std;

int k_system;

class cyc
{
private:
    string str;
public:
    cyc(const string &x);
    cyc(){}
    ~cyc();
    void print();
    void change_intArray(int *a,int len,int k) const;               //k表示k进制
    void change_string(int *a,int len,int k);
    cyc &operator =(const cyc &y);
    void operator =(const string &y);
    bool operator ==(const cyc &y) const;
    void print_output(ostream &out) const;
    friend bool cycle_string(const cyc &source,int count,cyc &result,int &result_count);
};///:p

inline void cyc::print_output(ostream &out) const
{
    out<<str<<endl;
}///:p

cyc::cyc(const string &x)
{
    str=x;
}///:p

cyc::~cyc()
{
    str="0";
}///:p

void cyc::print()
{
    cout<<str<<endl;
}///:p

void cyc::change_intArray(int *a,int len,int k) const
{
    if(k<=10&&k>=2)
    {
        for(int j=0;j<len;j++)                                        //已经对数组进行了逆置
        {
            a[len-1-j]=(int)(str[j]-48);
        }
    }
    if(k>=11&&k<=16)
    {
        for(int j=0;j<len;j++)
        {
            switch(str[j])
            {
            case 'A': a[len-1-j]=10; break;
            case 'B': a[len-1-j]=11; break;
            case 'C': a[len-1-j]=12; break;
            case 'D': a[len-1-j]=13; break;
            case 'E': a[len-1-j]=14; break;
            case 'F': a[len-1-j]=15; break;
            default : a[len-1-j]=(int)(str[j]-48);
            }
        }
    }
}///:p

void cyc::change_string(int *a,int len,int k)
{
    int i=1;
    while(a[len-i]==0&&i<len)
    {
        i++;
    }
    if(k<=10&&k>=2)
    {
        for(int j=0;j<=len-i;j++)
        {
           str+=(char)(a[len-i-j]+48);    
        }
    }
    if(k>=11&&k<=16)
    {
        for(int j=0;j<=len-i;j++)
        {
            switch(a[len-i-j])
            {
            case 10: str+='A'; break;
            case 11: str+='B'; break;
            case 12: str+='C'; break;
            case 13: str+='D'; break;
            case 14: str+='E'; break;
            case 15: str+='F'; break;
            default: str+=(char)(a[len-i-j]+48);
            }
        }
    }
}///:p

inline cyc &cyc::operator =(const cyc &y)
{
    this->str=y.str;
    return *this;
}///:p

inline void cyc::operator =(const string &x)
{
    this->str=x;
}///:p

inline bool cyc::operator ==(const cyc &y) const
{
    if(str==y.str)
    {
        return true;
    }
    else
    {
        return false;
    }
}///:p

//回文运算，此函数是本程序的核心
bool cycle_string(const cyc &source,int count,cyc &result,int &result_count)//data为要被检测的数，count为要求检测的次数,result为输出结果,result_count为若是回文，要多少次回文运算
{
    int len=source.str.length();

    int dynamic_len=len+100;
    int *p_zz=new int [dynamic_len];
    int *p_xx=new int [dynamic_len];
    if(NULL==p_zz||NULL==p_xx)
    {
        exit(1);
    }

    source.change_intArray(p_zz,len,k_system);

    for(int j=0;j<count+1;j++)                                             //若此循环内无解，则no solution
    {
        int switch_array=0;
        int carry=0,temp1,temp2;
        for(int i1=0;i1<len/2;i1++)
        {
            if(p_zz[i1]!=p_zz[len-1-i1])                                   //若不是回文，跳出
            {
                break;
            }
        }
        if(i1==len/2)                                                      //若i1==len/2，肯定是回文
        {        
            result.change_string(p_zz,len,k_system);
            result_count=j;
            delete [] p_zz;
            delete [] p_xx;
            return true;
        }

        int *temp=p_xx;                          //对指向数组的指针进行交换,保证参加运算的数组为p_xx所指的，存放结果的为p_zz所指的
        p_xx=p_zz;
        p_zz=temp;
        
        if(len==dynamic_len)
        {
            dynamic_len=len+100;
            delete [] p_zz;
            p_zz=new int [dynamic_len];
            if(NULL==p_zz)
            {
                exit(1);
            }
            switch_array=1;
        }

        for(int i=0;i<len;i++)
        {
            temp2=temp1=p_xx[i]+p_xx[len-1-i]+carry;
            carry=temp1/k_system;
            if(carry)
            {
                p_zz[i]=temp2%k_system;
            }
            else
            {
                p_zz[i]=temp2;
            }
        }
        if(carry)
        {
            p_zz[len]=carry;
            len+=1;
        }
        if(1==switch_array)
        {
            delete [] p_xx;
            p_xx=new int [dynamic_len];
            if(NULL==p_xx)
            {
                exit(1);
            }
        }

    }
    result="No solution!";                       //在count次循环内无解
    delete [] p_zz;
    delete [] p_xx;
    p_zz=NULL;
    p_xx=NULL;
    return false;
}///:p

clock_t start,finish;

int main()
{
    start=clock();
    ifstream in("input.txt");
    if(in.fail())
    {
        exit(1);
    }
    ofstream out("output.txt");
    int count;
    string input_data;
    in>>k_system>>count;
    in>>input_data;
    cyc data(input_data),result;
    int result_count;                             //记录几次得到回文数
    bool p=cycle_string(data,count,result,result_count);//data为要被检测的数，count为要求检测的次数,result为输出结果,result_count为若是回文，要多少次回文运算
    if(p)
    {
        out<<result_count<<endl;
        result.print_output(out);
    }
    else
    {
        result.print_output(out);
    }
    finish=clock();
    cout<<finish-start<<endl;
    return 0;
}