关于算法-数据结构:PAT甲级1024-Palindromic-Number

38次阅读

共计 1359 个字符,预计需要花费 4 分钟才能阅读完成。

题目粗心:

定义种操作: 让一个条数加上这个整数首尾颠倒后的数字。例如对整数 1257 执行操作就是 1257 + 7521 = 8778.* 当初给出一个正整数和操作次数限度,问在限定的操作次数内能是否能失去回文数。如果能失去,则输入那个回文数,并输入操作的次数; 否则,输入最初一次操作失去的数字以及操作次数。

算法思路:

此题的数据范畴有可能会超过 long long 类型 (自己没有测试),并且这里波及到了逆置操作,应用字符串才解决该数字较为不便,这个问题的要害两个问题就是如何判断一个数字是回文数,第二个就是如何实现 2 个字符串或者大整数的加法操作。第一个问题只须要判断字符串中对称地位的字符是否相等即可(对称地位的和为字符串长度),第二个问题在这里也比拟好解决,因为第二个整数是第一个整数逆置失去的,所以这两个整数的长度是雷同的,那么就只须要应用指针 i 从后往前扫描每一位,而后计算对应的局部和partialSum = (s1[i]-'0')+(s2[i]-'0')+carry; 这里应用 carry 保留上一位的进位,初始为 0,而后计算进位 carry = partialSum/10; 并且应用字符串 r 保留相加后的本位数字partialSum%10,最初得留神如果最高位有进位得增加进位到 r 中。

算法流程:

应用 step 记录执行加法的次数,初始为 0,而后只有 step<K 那么就进入循环,如果以后数字 N 为回文数字,就退出循环进行输入操作,否则就应用 s 保留 N 的逆置数,将 N 和 s 相加的后果保留到 N 中,并 step 自增。最初在循环退出的时候输入后果和执行次数。

提交后果:

AC 代码:

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

bool isPalindromic(string s){for (int i = 0; i < s.size() / 2; ++i) {if(s[i]!=s[s.size()-i-1]){return false;}
    }
    return true;
}

string add(string s1,string s2){
    int carry = 0;
    int partialSum = 0;
    string r;
    for (int i = s1.size()-1; i >= 0; --i) {// s1 和 s2 理论是一样长的
        partialSum = (s1[i]-'0')+(s2[i]-'0')+carry;
        carry = partialSum/10;
        r += to_string(partialSum%10);
    }
    // 因为 s1 和 s2 是一样长的,就无需判断 s1 或者 s2 还有局部须要相加了。if(carry!=0){r += to_string(carry);
    }
    reverse(r.begin(),r.end());
    return r;
}

int main(){
    string N;
    cin>>N;
    int K;
    scanf("%d",&K);
    int step = 0;
    string s;
    while (step<K){if(isPalindromic(N)) break;
        s = N;
        reverse(s.begin(),s.end());
        N = add(N,s);
        ++step;
    }
    printf("%s\n%d",N.c_str(),step);
    return 0;
}

正文完
 0