【解題】Reverse and Add

ACM Volume C 10018 - Reverse and Add


The Problem

The "reverse and add" method is simple: choose a number, reverse its digits and add it to the original. If the sum is not a palindrome (which means, it is not the same number from left to right and right to left), repeat this procedure.

For example:
195 Initial number
591
-----
786
687
-----
1473
3741
-----
5214
4125
-----
9339 Resulting palindrome

In this particular case the palindrome 9339 appeared after the 4th addition. This method leads to palindromes in a few step for almost all of the integers. But there are interesting exceptions. 196 is the first number for which no palindrome has been found. It is not proven though, that there is no such a palindrome.

Task :
You must write a program that give the resulting palindrome and the number of iterations (additions) to compute the palindrome.

You might assume that all tests data on this problem:
- will have an answer ,
- will be computable with less than 1000 iterations (additions),
- will yield a palindrome that is not greater than 4,294,967,295.


The Input

The first line will have a number N (0 < N <= 100) with the number of test cases, the next N lines will have a number P to compute its palindrome.


The Output

For each of the N tests you will have to write a line with the following data : minimum number of iterations (additions) to get to the palindrome and the resulting palindrome itself separated by one space.


Sample Input

3
195
265
750


Sample Output

4 9339
5 45254
3 6666


解題思考

　　這題本身難度不高，主要是要做是否為迴文的判斷。

　　根據題意，我們需要在輸入一筆數字之後，使之加上其倒轉之後的數字之後，再判斷是否為一個迴文。若是結果為非，則利用迴圈重複執行上述動作與判斷，直到結果為真為止。

　　而判斷是否為迴文，只需要將數字跟其反轉後的數字相比對。假如相等，就代表它是個迴文了。


參考解答(C++)

#include <iostream>

using namespace std;

typedef unsigned long ULONG;
ULONG reverse(ULONG);

int main(void)
{
    int n;
    cin >> n;

    // 進入資料輸入迴圈
    for (int i = 0; i < n; i++)
    {
        ULONG p;
        cin >> p;

        // 將 p 加上倒轉過來的數字
        p += reverse(p);

        int time = 0;
        while (1)
        {
            ULONG r = reverse(p);
            time++;

            // 判斷是否迴文
            if (p == r)
            {
                cout << time << " " << p << endl;
                break;
            }
            else { p += r; }
        }
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}

ULONG reverse(ULONG p)
{
    // 反轉數字
    ULONG r = 0;
    while (p)
    {
        r = r * 10 + p % 10;
        p /= 10;
    }

    return r;
}