PAT-A 真题 – 1024 Palindromic Number

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 $N$ , 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 $N$ and $K$ , where $N$ ( $\leq 1 0^{10}$ ) is the initial numer and $K$ ( $\leq 100$ ) 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 $N$ , and the second number is the number of steps taken to find the palindromic number. If the palindromic number is not found after $K$ steps, just output the number obtained at the $K$ th step and $K$ instead.

Sample Input 1:

67 3

Sample Output 1:

484
2

Sample Input 2:

69 3

Sample Output 2:

1353
3

题目大意：对于给定的数字，计算它本身与其倒过来的数字之和，判断是不是回文数，如果是，输出这个回文数和计算结果；如果不是，将其和继续计算，直到是回文数。最多计算K次，如果K次还不是回文数，给出第K次的结果。

这道题注意，给定的数的最大值是10000000000，K最大是100，在极端情况下会超过unsigned long long int，所以不能用整数来存储，只能用字符串。

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

string add(string a, string b){
  //字符串表示的数字进行加法运算 
  string ans;
  int jw = 0;  //进位 
  int i = a.length()-1, j = b.length()-1;
  for(;i>=0 && j>=0; i--, j--){
    int n = a[i] + b[j] - '0' * 2 + jw;
    jw = 0;
    if(n >= 10){
      n -= 10, jw = 1;
    }
    ans += (n + '0');
    //cout << a[i] << ' ' << b[i] << endl;
  }
  while(i >= 0){
    if(jw){
      ans += (a[i--]+1);
      jw = 0;
    }
    else ans += (a[i--]); 
  }
  while(j >= 0){
    if(jw){
      ans += (b[j--]+1);
      jw = 0;
    }
    else ans += (b[j--]); 
  }
  if(jw) ans += '1';  //处理进位 
  reverse(ans.begin(), ans.end());  //反转 
  return ans;
}

int main(){
  string num;
  int n;
  cin >> num >> n;
  int cnt = 0;
  while(n--){
    string rev = num;
    reverse(rev.begin(), rev.end());
    //cout << cnt << ' ' << num << ' ' << rev << endl;
    if(rev == num){
      cout << num << endl << cnt;
      return 0;
    }
    else num = add(num, rev);
    cnt++;
  }
  cout << num << endl << cnt;
  return 0;
}

上面的代码其实不是最优的，因为add函数考虑到了两个位数不一样的数字相加的对位、处理末尾进位的问题，其实这道题是自己和自己反过来相加，加数和被加数的位数一定是相同的，所以不必考虑对位。

因而add函数可以精简成下面的样子：

string add(string a, string b){
  int jw = 0;
  string ans;
  for(int i = b.length() - 1; i >= 0; i--){
    int n = a[i] + b[i] - 2 * '0' + jw;
    jw = 0;
    while(n >= 10)
      n-=10, jw++;
    ans += (n + '0');
  }
  if(jw) ans += (jw + '0');
  reverse(ans.begin(), ans.end());
  return ans;
}

斐斐のBlog