PAT Basic 1079. 延迟的回文数

1. 题目描述：

给定一个 \(k+1\) 位的正整数 \(N\)，写成 \(a_k⋯a_1a_0\) 的形式，其中对所有 \(i\) 有 \(0≤a_i<10\) 且 \(a_k>0\)。\(N\) 被称为一个回文数，当且仅当对所有 \(i\) 有 \(a_i=a_{k−i}\)。零也被定义为一个回文数。

非回文数也可以通过一系列操作变出回文数。首先将该数字逆转，再将逆转数与该数相加，如果和还不是一个回文数，就重复这个逆转再相加的操作，直到一个回文数出现。如果一个非回文数可以变出回文数，就称这个数为延迟的回文数。（定义翻译自 https://en.wikipedia.org/wiki/Palindromic_number ）

给定任意一个正整数，本题要求你找到其变出的那个回文数。

2. 输入格式：

输入在一行中给出一个不超过1000位的正整数。

3. 输出格式：

对给定的整数，一行一行输出其变出回文数的过程。每行格式如下

A + B = C

其中 A 是原始的数字，B 是 A 的逆转数，C 是它们的和。A 从输入的整数开始。重复操作直到 C 在 10 步以内变成回文数，这时在一行中输出 C is a palindromic number.；或者如果 10 步都没能得到回文数，最后就在一行中输出 Not found in 10 iterations.。

4. 输入样例：

97152

196

5. 输出样例：

97152 + 25179 = 122331
122331 + 133221 = 255552
255552 is a palindromic number.

196 + 691 = 887
887 + 788 = 1675
1675 + 5761 = 7436
7436 + 6347 = 13783
13783 + 38731 = 52514
52514 + 41525 = 94039
94039 + 93049 = 187088
187088 + 880781 = 1067869
1067869 + 9687601 = 10755470
10755470 + 07455701 = 18211171
Not found in 10 iterations.

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

编写两个子函数分别用于判断回文数和进行逆转相加的操作，逆转相加做好进位即可。这里因为给出的正整数有可能达到1000位，int类型存不下，所以必须存储为字符串。

第一次提交时testpoint6报Runtime Error，网站提示可能是数组越界访问造成的，检查了代码感觉逻辑无问题，将用于存储数字的字符数组大小改为1006时AC。开始的想法是两个数字最多为1000位，相加后存在进位的话最多为1001位，就将字符数组大小设为了1002，但是没有考虑到不满足回文数的话，数字会反复相加，就有可能超过1001位，这里逐渐增大到1006时AC。。。

My Code:

#include <stdio.h>
#include <string.h> // strlen header, strcpy header

#define MAX_LEN 1006 // 1006 is minimal value

int isPalindromic(const char *number);
void palindromicSum(char *number);

int main(void)
{
    char number[MAX_LEN] = "";
    int i=0; // iterator
    //char res[1002] = "";
    
    scanf("%s", number);
    
    if(isPalindromic(number)) // already panlindromic
    {
        printf("%s is a palindromic number.\n", number);
        return 0;
    }
    
    for(i=0; i<10; ++i)
    {
        palindromicSum(number);
        if(isPalindromic(number)) // become panlindromic
        {
            printf("%s is a palindromic number.\n", number);
            break;
        }
    }
    if(i==10)
    {
        printf("Not found in 10 iterations.\n");
    }
    
    //printf("%s\n", number);
    
    return 0;
}

int isPalindromic(const char *number) // 1 means true, 0 means false
{
    int i=0, j=0; // iterator
    
    for(i=0, j=strlen(number)-1; i<j; ++i, --j)
    {
        if(number[i] != number[j])
        {
            return 0;
        }
    }
    return 1;
}

void palindromicSum(char *number)
{
    char temp1[MAX_LEN] = "";
    int i=0; // iterator
    int carry = 0;
    int num1=0, num2=0;
    char temp2[MAX_LEN] = "";
    
    strcpy(temp1, number);
    for(i=0; i<strlen(temp1); ++i)
    {
        temp2[strlen(temp1)-1-i] = temp1[i];
    }
    
    for(i=0; i<strlen(temp1); ++i)
    {
        num1 = temp1[i] - '0';
        num2 = temp2[i] - '0';

        number[strlen(temp1)-1-i] = (num1+num2+carry)%10 + '0';
        carry = (num1+num2+carry)/10;
    }
    number[strlen(temp1)] = '\0';
    
    if(carry) // have carry bit
    {
        for(i=strlen(temp1); i>0; --i)
        {
            number[i] = number[i-1];
        }
        number[0] = '1';
        number[strlen(temp1)+1] = '\0';
    }
    
    printf("%s + %s = %s\n", temp1, temp2, number);
}