本文共 3774 字,大约阅读时间需要 12 分钟。
1136 A Delayed Palindrome (20 分)
Consider a positive integer N written in standard notation with k+1 digits ai as ak⋯a1a0 with 0≤ai<10 for all i and ak>0. Then N is palindromic if and only if ai=ak−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< <
涉及知识点
- reverse 反转函数
标准C中是没有recerse()函数的,这是C++的一个新增函数,使用需要包含头文件
#include reverse函数用于反转在[first,last)范围内的顺序(包括first指向的元素,不包括last指向的元素),reverse函数没有返回值
templatevoid 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来交换元素位置
templatevoid 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!