title: PAT1136
date: 2021-01-22 20:03:07
tags: PAT

1136

题目：

计算特殊的Palindrome数，性质是a_i = a_k-i，如果本身不是，则计算他和自己转置的和是不是，最多连续计算10次和

范围:

数的长度为1000个数字以内

分析:

数的长度1000内，所以是个大数，需要用到大数加法

解法:

大数加法算法

1. 两个数转置（此题以转置，长度一样，不用考虑）
2. 从后往前加，每次计算每一位的和，加上上一位的进位，加入字符串
3. 字符串转置

代码问题

代码中的大数加法没有处理长度短的的数前面有过多的0使长度大于长的数的可能

代码:

#include<iostream>
#include<string>
#include<algorithm>

using namespace std; 

bool judge_num(string num){
    int len = num.length(); 
    for(int i = 0; i < len/2; i++){
        if(num[i] != num[len - i - 1]) return false; 
    }
    return true; 
}

string add(string a,string b)
{
    string ret="";
    int lena=a.size();
    int lenb=b.size();
    int i=0,j=0;
    int c=0;
    while(i<lena&&j<lenb)
    {
        int now=a[i]-'0'+b[i]-'0'+c;
        c=now/10;
        now=now%10;
        char charnow=now+'0';
        ret+=charnow;
        i++;
        j++;
    }
    while(i<lena)
    {
        int now=a[i]-'0'+c;
        c=now/10;
        now=now%10;
        char charnow=now+'0';
        ret+=charnow;
        i++;
    }
    while(j<lena)
    {
        int now=b[j]-'0'+c;
        c=now/10;
        now=now%10;
        char charnow=now+'0';
        ret+=charnow;
        j++;
    }
    if(c>0)
    {
        ret+="1";
    }
    reverse(ret.begin(),ret.end());
    return ret;
}

int main(){
    freopen("./1136_in", "r", stdin); 
    string num; 
    cin>>num;
    for(int i = 0; i <= 10; i++){
        if(judge_num(num)) {
            cout<<num<<" is a palindromic number."<<endl; 
            break; 
        }
        else if(i <= 9){
            string tmp_num = num; 
            reverse(num.begin(), num.end());
            cout<<tmp_num<<" + "<<num<<" = "; 
            num = add(tmp_num, num); 
            cout<<num<<endl; 
        }
        else {
            cout<<"Not found in 10 iterations."<<endl; 
        }
    }
}