1024 Palindromic Number（回文数）

本是古典何须时尚 2024-04-08 09:54 14阅读 0赞

## 1024 Palindromic Number ##

### 0、题目 ###

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* (≤1010) is the initial numer and *K* (≤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

### 1、大致题意 ###

给定一个数字，和允许翻转后相加的次数`cnt`，求要多少次才能变成一个回文数字，输出那个回文数字和翻转相加了多少次，如果本身就是回文数字就输出`0`次，如果超过给定的次数`cnt`了，就输出那个不是回文的结果，并且输出给定的次数`cnt`

### 2、基本思路 ###

简单题

### 3、解题过程 ###

#### 3.1 数组存法 ####

#include<iostream>
    #include<cmath>
    using namespace std;
    
    long long n,k;
    int a[105],num_a;
    
    void seta(long long k) {
        
    	num_a=0;
    	while(k!=0) {
        
    		a[num_a]=k%10;
    		k/=10;
    		num_a++;
    	}
    }
    
    int is_Palindromic(long long k) {
        
    	seta(k);
    	for(int i=0; i<num_a/2; i++) {
        
    		if(a[i]!=a[num_a-i-1]) {
        
    			return -1;
    		} else {
        
    			return 1;
    		}
    	}
    }
    
    int main() {
        
    	scanf("%lld%lld",&n,&k);
    	long long ans=0;
    	int cnt=0;
    	while(is_Palindromic(n)!=1&&cnt<k) {
        
    		ans=0;
    		num_a=0;
    		seta(n);
    		for(int i=num_a-1; i>=0; i--) {
        
    			ans=ans+(long long)a[i]*pow(10,num_a-i-1);
    		}
    		n=n+ans;
    		cnt++;
    	}
    	cout<<n<<endl<<cnt;
    	return 0;
    }

![在这里插入图片描述][835a21fe368340c5a56741f7dd019b60.png]

##### 3.1.1 一位数 #####

当一位数的时候，会出错，例如下面的用例

输入：
    1 3
    输出：
    1
    0

问题出在 **c++的默认返回值**

int is_Palindromic(long long k) {
        
    	seta(k);
    	for(int i=0; i<num_a/2; i++) {
        
    		if(a[i]!=a[num_a-i-1]) {
        
    			return -1;
    		} else {
        
    			return 1;
    		}
    	}
        return 1;//这句一定要加
    }

编译器会脑补默认的返回值——0。当然，**成熟的编译器**会给出一条警告，但不会认为这是个错误。

#include<iostream>
    #include<cmath>
    using namespace std;
    
    long long n,k;
    int a[105],num_a;
    
    void seta(long long k) {
        
    	num_a=0;
    	while(k!=0) {
        
    		a[num_a]=k%10;
    		k/=10;
    		num_a++;
    	}
    }
    
    int is_Palindromic(long long k) {
        
    	seta(k);
    	for(int i=0; i<num_a/2; i++) {
        
    		if(a[i]!=a[num_a-i-1]) {
        
    			return -1;
    		} else {
        
    			return 1;
    		}
    	}
    	return 1;
    }
    
    int main() {
        
    	scanf("%lld%lld",&n,&k);
    	long long ans=0;
    	int cnt=0;
    	while(is_Palindromic(n)!=1&&cnt<k) {
        
    		ans=0;
    		num_a=0;
    		seta(n);
    		for(int i=num_a-1; i>=0; i--) {
        
    			ans=ans+(long long1)a[i]*pow(10,num_a-i-1);
    		}
    		n=n+ans;
    		cnt++;
    	}
    	cout<<n<<endl<<cnt;
    	return 0;
    }

![在这里插入图片描述][d8a7cf96beea49c2a963039413b14841.png]

##### 3.1.2 大数 #####

数字太大会出错

输入：
    5165454546454 4
    输出：
    1039973000379940
    4

当 `long long` 吃不消时，就只能转用其他的办法

#### 3.2 AC代码 ####

#include <iostream>
    #include <algorithm>
    using namespace std;
    string s;
    void add(string t) {
        
    	int len = s.length(), carry = 0;
    	for(int i = 0; i < len; i++) {
        
    		s[i] = s[i] + t[i] + carry - '0';
    		carry = 0;
    		if(s[i] > '9') {
        
    			s[i] = s[i] - 10;
    			carry = 1;
    		}
    	}
    	if(carry) s += '1';
    	reverse(s.begin(), s.end());
    }
    int main() {
        
    	int cnt, i;
    	cin >> s >> cnt;
    	for(i = 0; i <= cnt; i++) {
        
    		string t = s;
    		reverse(t.begin(), t.end());
    		if(s == t || i == cnt) break;
    		add(t);
    	}
    	cout << s << endl << i;
    	return 0;
    }

[835a21fe368340c5a56741f7dd019b60.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/1b942c0412dd4814b3a625daae605f41.png
[d8a7cf96beea49c2a963039413b14841.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/240483243dae460586d46ee6f1c2a8a4.png