PAT Advanced 1024. Palindromic N

我的PAT系列文章更新重心已移至Github，欢迎来看PAT题解的小伙伴请到Github Pages浏览最新内容(本篇文章链接)。此处文章目前已更新至与Github Pages同步。欢迎star我的repo。

题目

A number that will be the same when it is written forwards or backwards is
known as a Palindromic Number. For example, 1234321 is a palindromic
number. All single digit numbers are palindromic numbers.

Non-palindromic numbers can be paired with palindromic ones via a series of
operations. First, the non-palindromic number is reversed and the result is
added to the original number. If the result is not a palindromic number, this
is repeated until it gives a palindromic number. For example, if we start from
67, we can obtain a palindromic number in 2 steps: 67 + 76 = 143, and 143 +
341 = 484.

Given any positive integer , you are supposed to find its paired
palindromic number and the number of steps taken to find it.

Input Specification:

Each input file contains one test case. Each case consists of two positive
numbers and , where ( ) is the initial numer and
( ) is the maximum number of steps. The numbers are separated by a
space.

Output Specification:

For each test case, output two numbers, one in each line. The first number is
the paired palindromic number of , and the second number is the number of
steps taken to find the palindromic number. If the palindromic number is not
found after steps, just output the number obtained at the th step and
instead.

Sample Input 1:

67 3

Sample Output 1:

484
2

Sample Input 2:

69 3

Sample Output 2:

1353
3

思路

结合考察大数计算和回文数，和1023题很相似，涉及到的操作有：

• 翻转
• 两数相加
• 判断回文数

相加的函数和1023中翻倍的写法很像，只不过是把当前位乘二换为相加，
因为这道题是和自己的翻转数相加，所以我代码中没有考虑两数长度不同的情况，
在更广泛的应用中，切记要考虑两不同长度的大数相加的处理。

P.S. 我的处理和1023题中也一样，是倒序存储数字的，所以开头结尾要翻转过来才可以。

字符串长度：这道题，字符串长度取得很宽松，实际上极限可能就是60位左右，不要取得过小。

代码

最新代码@github，欢迎交流

#include <stdio.h>
#include <string.h>

int isPalindromic(char n[])
{
    int len = strlen(n);
    for(int i = 0; i < len / 2; i++)
        if(n[i] != n[len - i - 1])
            return 0;
    return 1;
}

char* reverse(char n[])
{
    char temp;
    int len = strlen(n);
    for(int i = 0; i < len / 2; i++)
    {
        temp = n[i];
        n[i] = n[len - i - 1];
        n[len - i - 1] = temp;
    }
    return n;
}

/* only works when a and b are of the same length */
void addAtoB(char a[], char b[])
{
    int l, s = 0, len = strlen(a);

    for(int i = 0; i < len; i++)
    {
        s += (a[i] - '0') + (b[i] - '0');
        l = s / 10;
        s %= 10;
        b[i] = s + '0';

        s = l;
    }

    if(s)
        b[len] = s + '0';
}

int main()
{
    int K, steps;
    char s1[100] = {0}, s2[100] = {0}, *n = s1, *m = s2;

    scanf("%s %d", n, &K);
    reverse(n);

    for(steps = 0; steps < K && !isPalindromic(n); steps++)
    {
        /* change 'm' into reverse of 'n' */
        strncpy(m, n, 100);
        reverse(m);
        /* add n and reversed n, and keep the result in n */
        addAtoB(m, n);
    }

    printf("%s\n%d", reverse(n), steps);

    return 0;
}