Henry-ji 的小站

精品资源，小知识分享

0%

UVA613 题解

发表于 分类于 Valine：
本文字数： 337 阅读时长 ≈ 1 分钟

UVA 613 Numbers That Count 翻译 | Henry-ji 的小站

一、题目分析

  • 仔细阅读题目，不难发现本题是一个纯模拟题，只需要通过递归求每个数的”记录数“即可。

  • 记录数的计算：构建长度为 10 的 list，记录各数字的出现次数，最后拼成一个数即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def inventory(n):    # 计算”记录数“
        countList = [0] * 10    # 统计数字的出现频率
        for c in str(n):
            countList[int(c)] += 1
        ans = ''
        for i in range(10):
            if countList[i] != 0:
                ans += str(countList[i]) + str(i)
        return int(ans)

  • 数的分类（为了简化代码，我们以迭代的次数 $j$ 以及循环的长度 $k$ 来进行分类）

    • $j = 0$：本来就是”自记录数“
    • $j = 14$ 且 $k = 0$：已经进行了 $15$ 次迭代但依旧未找到循环，即无法分类
    • $j < 14$ 且 $k = 0$：循环长度为零，即在迭代后成为了“自记录数”
    • $j < 14$ 且 $k \ne 0$：即在 $j$ 次迭代后生成了长度为 $k + 1$ 的循环（算上循环开始的第一个数）
    1
    2
    3
    4
    5
    6
    7
    8
    if j == 0:    # 循环长度为 0，即本身就是”自记录数“
        print(n, 'is self-inventorying')
    elif j == 14 and k == 0:    # 已经进行了 15 次迭代仍未找到循环，即无法分类
        print(n, 'can not be classified after 15 iterations')
    elif k == 0:    # 循环长度为 0，即在 j 次迭代后成为”自记录数“
        print(n, 'is self-inventorying after', j, 'steps')
    else:    # 即 j 次迭代后进入长度为 k + 1 的循环
        print(n, 'enters an inventory loop of length', k + 1)

二、AC Code

理清思路后代码就很好写了，下面放上 AC 代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def inventory(n):    # 计算”记录数“
    countList = [0] * 10    # 统计数字的出现频率
    for c in str(n):
        countList[int(c)] += 1
    ans = ''
    for i in range(10):
        if countList[i] != 0:
            ans += str(countList[i]) + str(i)
    return int(ans)


def find(l, n):    # 查找函数
    for i in range(len(l)):
        if l[i] == n:
            return i
    return -1


def classify(n):    # 分类函数
    memList = []
    k = 0
    for j in range(15):
        next_n = inventory(n)
        if n == next_n:
            break
        p = find(memList, next_n)
        if p != -1:
            k = j - p
            break
        memList.append(n)
        n = next_n
    return j, k    # j 指迭代的次数，k 指循环起始位


while True:
    n = eval(input())
    if n == -1:
        break
    j, k = classify(n)
    if j == 0:    # 循环长度为 0，即本身就是”自记录数“
        print(n, 'is self-inventorying')
    elif j == 14 and k == 0:    # 已经进行了 15 次迭代仍未找到循环，即无法分类
        print(n, 'can not be classified after 15 iterations')
    elif k == 0:    # 循环长度为 0，即在 j 次迭代后成为”自记录数“
        print(n, 'is self-inventorying after', j, 'steps')
    else:    # 即 j 次迭代后进入长度为 k + 1 的循环
        print(n, 'enters an inventory loop of length', k + 1)