1117 数字之王 – PAT乙级真题

给定两个正整数 N1<N2。把从 N1 到 N2 的每个数的各位数的立方相乘，再将结果的各位数求和，得到一批新的数字，再对这批新的数字重复上述操作，直到所有数字都是 1 位数为止。这时哪个数字最多，哪个就是“数字之王”。

例如 N1=1 和 N2=10 时，第一轮操作后得到 { 1, 8, 9, 10, 8, 9, 10, 8, 18, 0 }；第二轮操作后得到 { 1, 8, 18, 0, 8, 18, 0, 8, 8, 0 }；第三轮操作后得到 { 1, 8, 8, 0, 8, 8, 0, 8, 8, 0 }。所以数字之王就是 8。

本题就请你对任意给定的 N1<N2 求出对应的数字之王。

输入格式：

输入在第一行中给出两个正整数 0<N1<N2≤10^3，其间以空格分隔。

输出格式：

首先在一行中输出数字之王的出现次数，随后第二行输出数字之王。例如对输入 1 10 就应该在两行中先后输出 6 和 8。如果有并列的数字之王，则按递增序输出。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

10 14

输出样例：

2
0 8

分析：使用f变量控制是否继续重复执行题目中的操作，1表示继续执行，0表示停止。B中存储数字0-9出现的次数，maxn存储数字之王出现的次数。首先将N1到N2的值存储在数组A中，如果N2超过9，表示有数字不是个位数。循环过程中按照题意模拟。然后把所有的个位数输出现了几次，记录在数组B中。把出现次数最多的所有的数存储在数组ans中，最后按顺序输出它们。

#include <iostream>
#include <vector>
using namespace std;
int N1, N2, f, A[1005], B[10], maxn;
vector<int> ans;
signed main(){
    cin >> N1 >> N2;
    for (int i = N1; i <= N2; i++) A[i] = i;
    if (N2 > 9) f = 1;
    while (f) {
        f = 0;
        for (int i = N1; i <= N2; i++) {
            if (!A[i]) continue;
            int t1 = 1, t2 = A[i];
            while(t2) {
                t1 *= (t2 % 10) * (t2 % 10) * (t2 % 10);
                t2 /= 10;
            }
            while(t1) {
                t2 += t1 % 10;
                t1 /= 10;
            }
            if (t2 > 9) f = 1;
            A[i] = t2;
        }
    }
    for (int i = N1; i <= N2; i++) {
         B[A[i]]++;
         maxn = max(maxn, B[A[i]]);
    }
    for (int i = 0 ; i < 10; i++) 
        if (B[i] == maxn) ans.push_back(i);
    cout << maxn << '\n';
    for (int i = 0; i < ans.size(); i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int N1, N2, f, A[1005], B[10], maxn;

vector<int> ans;

signed main(){

cin >> N1 >> N2;

for (int i = N1; i <= N2; i++) A[i] = i;

if (N2 > 9) f = 1;

while (f) {

f = 0;

for (int i = N1; i <= N2; i++) {

if (!A[i]) continue;

int t1 = 1, t2 = A[i];

while(t2) {

t1 *= (t2 % 10) * (t2 % 10) * (t2 % 10);

t2 /= 10;

}

while(t1) {

t2 += t1 % 10;

t1 /= 10;

}

if (t2 > 9) f = 1;

A[i] = t2;

}

for (int i = N1; i <= N2; i++) {

B[A[i]]++;

maxn = max(maxn, B[A[i]]);

}

for (int i = 0 ; i < 10; i++)

if (B[i] == maxn) ans.push_back(i);

cout << maxn << '\n';

for (int i = 0; i < ans.size(); i++) {

if (i) cout << ' ';

cout << ans[i];

}

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版