【PAT】1136 A Delayed Palindrome
发布日期:2022-02-10 08:11:17 浏览次数:14 分类:技术文章

本文共 3774 字,大约阅读时间需要 12 分钟。

1136 A Delayed Palindrome (20 分)

Consider a positive integer N written in standard notation with k+1 digits a​i​​ as a​k​​⋯a​1​​a​0​​ with 0≤a​i​​<10 for all i and a​k​​>0. Then N is palindromic if and only if a​i​​=a​k−i​​ for all i. Zero is written 0 and is also palindromic by definition.

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. Such number is called a delayed palindrome. (Quoted from https://en.wikipedia.org/wiki/Palindromic_number )

Given any positive integer, you are supposed to find its paired palindromic number.

Input Specification:

Each input file contains one test case which gives a positive integer no more than 1000 digits.

Output Specification:

For each test case, print line by line the process of finding the palindromic number. The format of each line is the following:

A + B = C

where A is the original number, B is the reversed A, and C is their sum. A starts being the input number, and this process ends until C becomes a palindromic number – in this case we print in the last line C is a palindromic number.; or if a palindromic number cannot be found in 10 iterations, print Not found in 10 iterations. instead.

Sample Input 1:

97152

Sample Output 1:

97152 + 25179 = 122331

122331 + 133221 = 255552
255552 is a palindromic number.

Sample Input 2:

196

Sample Output 2:

196 + 691 = 887

887 + 788 = 1675
1675 + 5761 = 7436
7436 + 6347 = 13783
13783 + 38731 = 52514
52514 + 41525 = 94039
94039 + 93049 = 187088
187088 + 880781 = 1067869
1067869 + 9687601 = 10755470
10755470 + 07455701 = 18211171
Not found in 10 iterations.

错误解题思路

解题代码:

#include 
#include
#include
#include
using namespace std;int main(){
long int N = 0,nonN = 0,count = 0; string str = "",nonstr = ""; cin>>N; str = to_string(N); nonstr = str; reverse(str.begin(),str.end()); while(nonstr != str && count < 10) {
cout<
<<" + "<
<<" = "; stringstream ss; ss<
>nonN; N += nonN; cout<
<

测试结果:

测试结果

这种解题方法过不了最后一个测试点,因为题目中已经说明整数N不超过1000位,也就是说当N有1000位的时候,直接进行整型相加会超出整型的范围。我也是在这里卡了很久,没有注意到这一点。于是将其修改为
字符串一位一位地相加,最后得出的还是字符串,不会超出范围,还要注意,
输入也应该存在字符串中,否则当超出整型范围时,int变量无法正确接收。 具体代码如下:
#include 
#include
using namespace std;string add(string a,string b){
int i = a.length()-1,k = 0; string sum = "",s = ""; for(;i>=0;i--) {
k += a[i]-'0'+b[i]-'0'; s = to_string(k); if(s.length()==2) {
k = 1; sum += s[1]; } else {
k = 0; sum += s; } } if(k == 1) {
sum += "1"; } reverse(sum.begin(),sum.end()); return sum;} int main(){
int count = 0; string str = "",nonstr = ""; cin>>str; nonstr = str; reverse(str.begin(),str.end()); while(nonstr != str && count < 10) {
cout<
<<" + "<
<<" = "; str = add(nonstr,str); cout<
<

涉及知识点

  1. reverse 反转函数

标准C中是没有recerse()函数的,这是C++的一个新增函数,使用需要包含头文件

#include 

​ reverse函数用于反转在[first,last)范围内的顺序(包括first指向的元素,不包括last指向的元素),reverse函数没有返回值

template 
void reverse (BidirectionalIterator first,BidirectionalIterator last);

​ 例如,交换vector容器中元素的顺序

vector
v = {5,4,3,2,1};reverse(v.begin(),v.end());//v的值为1,2,3,4,5

​ 还有string类的字符串

string str="www.mathor.top";reverse(str.begin(),str.end());//str结果为pot.rohtam.wwww

​ 最后给出函数原型,该函数等价于通过调用iter_swap来交换元素位置

template 
void reverse (BidirectionalIterator first, BidirectionalIterator last){ while ((first!=last)&&(first!=--last)) { std::iter_swap (first,last); ++first; }}

转载地址:https://blog.csdn.net/qq_45717064/article/details/114284251 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:PAT甲级题目及分类总结
下一篇:【PAT】甲级题目分类

发表评论

最新留言

不错!
[***.144.177.141]2024年02月29日 08时28分17秒