PAT甲级1015解法

原题链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805495863296000

思路

这题要求判断一个数在翻转前后是否都是质数。有一个难以理解的地方是在给定进制下的翻转,这是指转成该进制表示的数之后翻转,再将翻转后的数转换回十进制判断。比如11在二进制下的翻转,首先转换为二进制表示形式1011,之后翻转为1101,再转换回十进制为13判断。另外,将十进制转换为其他进制的方法是用原数不断去除以进制数,并将每次得到的余数倒序记录下来,而由于我们还需要再翻转一次,所以在计算时直接依次将余数存在vector中最终得到的就是在给定进制下翻转后的数。

代码如下

代码

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int num, radix, reverse;
    vector<int> result; //1代表Yes,0代表No
    cin >> num;
    while (num >= 0)
    {
        reverse = 0;    //用于存储翻转后的数
        if (num < 2)    //1和0
        {
            result.push_back(0);
            cin >> num;
            continue;   //直接进入下一次循环
        }
        int flag = 1;
        cin >> radix;
        for (int i = 2; i < num; i++)   //判断原数是否为质数
        {
            if (num%i == 0)
            {
                flag = 0;
                break;
            }
        }
        vector<int> radixNum;
        while (num / radix > 0)
        {
            radixNum.push_back(num%radix);
            num /= radix;
        }
        radixNum.push_back(num);
        int exp = 1;
        for (int i = radixNum.size() - 1; i >= 0; i--)
        {
            reverse += radixNum[i] * exp;
            exp *= radix;
        }
        if (reverse < 2)    //1和0
        {
            result.push_back(0);
            cin >> num;
            continue;   //直接进入下一次循环
        }
        for (int i = 2; i < reverse; i++)   //判断翻转数是否为质数
        {
            if (reverse % i == 0)
            {
                flag = 0;
                break;
            }
        }
        result.push_back(flag);
        cin >> num;
    }
    for (int i = 0; i < result.size(); i++)
    {
        if (result[i] == 1)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}
上一篇:PAT乙级1015-----德才论 (25分)


下一篇:信息学奥赛一本通 1015 计算并联电阻的阻值