ZeroJudge C015: Reverse and Add

同題：UVa 10018 – Reverse and Add

把一個數字反轉並相加的方法很簡單：就是把數字反轉並加上原來的數字。假如這個和不是一個迴文 (指這個數字從左到右和從右到左都相同），就一直重複這個程序。舉例說明：

195 開始的數字
591
—–
786
687
—–
1473
3741
—–
5214
4125
—–
9339 迴文出現了

在這個例子中，經過了 4 次相加後得到了迴文 9339。幾乎對所有的整數這個方法都會得到迴文，但是也有有趣的例外。196 是第 1 個用這個方法找不到迴文的數字，然而並沒有證明該迴文不存在。

現在給你一個開始的數字，你的任務就是求出經過多少次相加後，會產生哪一個迴文。對所有的測試資料，你可以假設：

  1. 都會有1個答案
  2. 在1000個相加內都會得到答案
  3. 產生的迴文不會大於4294967295

範例測資

範例輸入範例輸出
第 1 列有一個整數 N (0 < N <= 100），代表以下有幾組測試資料。每筆測試資料一列，各有 1 個整數 P，就是開始的數字。對每一測試資料，請輸出 2 個數字：得到迴文所需的最少次數的相加，以及該迴文。
5
195
265
750
2
99		4 9339
5 45254
3 6666
1 4
6 79497

解題思路

每個數字至少需要進行計算一次，所以就算一開始就是迴文了也需要計算下一次出現迴文的時間。可以將收到的資料轉換成字串或是一開始收資料的時候就收成字串型態。使用 While迴圈，如果目前的數字不是迴文就一直做計算，並且每次進 While迴圈 計算的次數就 +1。

範例程式碼－ZeroJudge C015: Reverse and Add

#include <iostream>
#include <algorithm>
using namespace std;

int toint (string str)
{
    if (str.length() == 1) return int(str[0] - '0');
    return stoi(str);
}

int calc (int N)
{
    int a = N;
    string str = to_string(N);
    reverse(str.begin(), str.end());
    int b = toint(str);
    return a + b;
}

bool OK (int N)
{
    string str = to_string(N);
    string str1 = str;
    reverse(str1.begin(), str1.end());
    if (str == str1) return true;
    return false;
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        int tmp;
        cin >> tmp;
        int count = 1;
        tmp = calc(tmp);
        while (!OK(tmp))
        {
            count++;
            tmp = calc(tmp);
        }
        cout << count << " " << tmp << "\n";
    }
}

//ZeroJudge C015
//Dr. SeanXD
標籤

相關文章

發佈留言