PAT乙级1084 || 外观数列（详解，C/C++示例，测试点分析）

Posted on In

外观数列

题目描述

外观数列是指具有以下特点的整数序列：

1
d, d1, d111, d113, d11231, d112213111, ...

它从不等于 1 的数字 d 开始，序列的第 n+1 项是对第 n 项的描述。比如第 2 项表示第 1 项有 1 个 d，所以就是 d1；第 2 项是 1 个 d（对应 d1）和 1 个 1（对应 11），所以第 3 项就是 d111。又比如第 4 项是 d113，其描述就是 1 个 d，2 个 1，1 个 3，所以下一项就是 d11231。当然这个定义对 d = 1 也成立。本题要求你推算任意给定数字 d 的外观数列的第 N 项。

输入格式

输入第一行给出 [0,9] 范围内的一个整数 d、以及一个正整数 N（≤ 40），用空格分隔。

输出格式

在一行中给出数字 d 的外观数列的第 N 项。

输入样例

1
1 8

输出样例

1
1123123111

问题解决

解题思想

明白了外观数列的意思问题也就很容易解决了。此处我用了char型vector容器来存储每一项的内容，计算第n+1项的内容时，先将第n项暂存并清空容器，然后边处理边存入。在这里vector有个特别好的特性就是两个同类型的vector容器可以直接赋值。

坑点提醒

None

代码示例（C/C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int d, n;
    cin >> d >> n;
    vector <char> vi;
    vi.push_back(d + '0');
    for (int i = 1; i < n; i++) {
        vector <char> tmp = vi;
        vi.clear(); //清空vi中的内容
        for (vector <char> :: iterator it = tmp.begin(); it != tmp.end(); it++) {
            vi.push_back(*it);
            char c = *it;
            int num = 0;    //统计个数
            while (*it == c && it != tmp.end()) {
                num++;
                it++;
            }
            it--;
            vi.push_back(num + '0');
        }
    }
    for (vector <char> :: iterator it = vi.begin(); it != vi.end(); it++) {
        cout << *it;
    }
    return 0;
}

题目来源：PAT乙级1084
作者：CHEN, Yue
单位：浙江大学

稀罕作者