【蓝桥杯冲击国赛计划第7天】模拟和打表 {题目：算式问题、求值、既约分数、天干地支}

1. 模拟和打表

1.1 定义

模拟法是比赛中最常用的方法，使用各种算法大都离不开模拟，而对于一些只是需要结果的题目来说打表法是一个非常好的解决方案，而且对于数论等其他需要找规律的题目来说，打表法是一个非常有用的方法。

模拟法和打表法，经常会同时出现，因为打表就要按照题目的意思去模拟。今天我们就从蓝桥杯的真题出发，给大家讲解一下，打表法和模拟法的应用

2. 实例「算式问题」

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

看这个算式：

☆☆☆ + ☆☆☆ = ☆☆☆

如果每个五角星代表 1 ~ 9 的不同的数字。

这个算式有多少种可能的正确填写方法？

173 + 286 = 459
295 + 173 = 468
173 + 295 = 468
183 + 492 = 675
1
2
3
4

以上都是正确的填写法！

注意：111+222=333 是错误的填写法！ 因为每个数字必须是不同的！ 也就是说：1 ~ 9 中的所有数字，每个必须出现且仅出现一次！

注意：不包括数字 0！

注意： 满足加法交换率的式子算两种不同的答案。 所以答案肯定是个偶数！

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

2.1 简单分析

可以做三重循环（后续进行降到两重循环）遍历三个未知数，然后可以通过取个位、十位、百位到列表或者字典中，进行判定重复。

由于后续使用了字典，这里说下列表的判重，我们可以做个一维列表，把三个未知数的每一位不断添加到列表，添加前判断一下是否存在，不存在就添加，存在就说明重复。如果能添加到最后，也就是列表长度为 9 时，说明条件满足。

2.2 检查函数

我们需要判断三个数是否是 1-9 的数字，是否产生重复的问题。一看到重复，我们本能可以想到字典。为了让取值更简单一点，我们需要先把数字转化为字符串，通过循环来判定字符串是否合法。

合法需要两个条件：

1. 是否出现 0，如果字符串内有 0 的存在即为不合法
2. 是否有重复，当有重复的数字使用时也为不合法

关于字典，下面类似的操作我在【蓝桥杯冲击国赛计划第6天】字典 已经讲的很清楚，不懂的小伙伴可以自行查看。

def check(num1,num2,num3):
    d = {}
    # 数字字符化 --> 便于取值
    num1 = str(num1)
    num2 = str(num2)
    num3 = str(num3)
    for i in range(3):
        if num1[i] == '0' or num2[i] == '0' or num3[i] == '0': # 排除出现有0的情况
            return False
        if d.get(num1[i]) == None: # 没在字典中，添加，这里的值可以任意，这里默认为1
            d[num1[i]] = 1
        else:
            return False # 说明第二次出现在字典中，排除数字重复
        # 下面如上
        if d.get(num2[i]) == None:
            d[num2[i]] = 1
        else:
            return False
        if d.get(num3[i]) == None:
            d[num3[i]] = 1
        else:
            return False
    return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.3 三重化二重

如果最简单的想：我们可以做三重循环去遍历，然后看三个数是否能满足等式。实际上，我们可以降至两重循环，因为我们知道两个加数后，加起来就可以得到他们的和了，这样就没必要做三重循环去判断两数之和是否等于第三个数。

由于只能使用 1- 9 的数，且只能使用一次。那么加数的范围只能是 [123,987]，虽然这个范围只缩小了一点，但希望大家能够理解，这也是一种思维，每次在一些细枝末节减少时间，最后可能带来的就是整体效率的提升。

第一个加数范围是 [123,988) ，第二个应该也是，但实际上当第一个加数范围出来后，第二个加数的范围可以更小。因为第一个加数它的约束是 1-9 只能用一次，而第二个加数在此约束的基础上，加了一个新的约束：两个加数加起来需要是三位数，再细节一点，这个加起来的三位数也要 < 988。所以第二个数的范围应该是 [123,988-第一个加数)。

if __name__ == '__main__':
    res = 0
    for i in range(123,988):
        for j in range(123,988-i): # 保证 i+j 和不大于987
            if check(i,j,i+j):
                res+=1
    print(res)
1
2
3
4
5
6
7

3. 实例「求值」

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

学习了约数后，小明对于约数很好奇，他发现，给定一个正整数 t，总是可以找到含有 t 个约数的整数。小明对于含有 t 个约数的最小数非常感兴趣，并把它定义为St 。

例如 S1=1，S2=2，S3=4，S4=6，⋅⋅⋅ 。

现在小明想知道，当 t=100 时，St 是多少？即 S100 是多少？

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

3.1 简单分析

一个自然数数如果能够由两个整数相乘，那么这两个整数就是该自然数的约数。

例如：

• 1 = 1 * 1 ，所以 S1=1

• 2 = 1 * 2 ，所以 S2=2

• 3 和 2 一样都是 2 个约数，跳过

• 4 = 1 * 4 = 2 * 2 ，所以 S3=3

• …

我们可以做两重循环，通过取余操作，不断查找约数，记录数量。

3.2 主函数

由于这题比较直接，就在主函数解决了。其实本来应该是数论的内容，硬是被我们模拟出来了。虽然时间上要用 2,3 分钟 左右，但结果至少是对的，而且填空题只要填最后的答案。

两重循环：第一重循环查找的数，第二重循环它可能的约数（约数范围实际是可以缩小的，这里为了方便理解就没有缩小范围），这个查找的数最大定义到 100000，这只是一个大概的估计，如果运行不出来，就要扩大范围查找。

如果 第一重循环的数 % 第二重循环的数 == 0，说明第二重循环的数是第一重循环的数的约数，所以个数++。

if __name__ == '__main__':
    for i in range(1,100000): # 待查找的数
        t = 0 # 约数个数
        for j in range(1,i+1): # 约数
            if i % j == 0:
                t+=1 # 约数个数++
            if t > 100:
                break
        if t == 100:
            print(i)
            break
1
2
3
4
5
6
7
8
9
10
11

4. 实例「既约分数」

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。

$\frac{3}{4},\frac{1}{8},\frac{7}{1}$都是既约分数。

请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1 和 2020）？

运行限制

• 最大运行时间：2s
• 最大运行内存: 128M

4.1 简单分析

两重循环，一重分子，一重分母，然后通过辗转相除法判断两者是否互质，是的话既约分数个数++。

4.2 辗转相除法

大概就是 a % b = c，下一次让 b，c 代替刚才 a 和 b 的位置。具体原理我就直接转载了底层开发的辗转相除法，我认为这个博主讲的质量很高，大家可以自行查看。

def gcd(a,b):
    # 边界条件
    if a % b == 0:
        return b
    # 辗转相除法
    return gcd(b,a%b)
1
2
3
4
5
6

2.3 主函数

这里不多加赘述，正常循环判断即可。

if __name__ == '__main__':
    res = 0
    for i in range(1,2021):
        for j in range(1,2021):
            if gcd(i,j) == 1:
                res+=1
    print(res)
1
2
3
4
5
6
7

5. 实例「天干地支」

题目描述

古代中国使用天干地支来记录当前的年份。

天干一共有十个，分别为：甲（jiǎ）、乙（yǐ）、丙（bǐng）、丁（dīng）、戊（wù）、己（jǐ）、庚（gēng）、辛（xīn）、壬（rén）、癸（guǐ）。

地支一共有十二个，分别为：子（zǐ）、丑（chǒu）、寅（yín）、卯（mǎo）、辰（chén）、巳（sì）、午（wǔ）、未（wèi）、申（shēn）、酉（yǒu）、戌（xū）、 亥（hài）。

将天干和地支连起来，就组成了一个天干地支的年份，例如：甲子。

2020 年是庚子年。

每过一年，天干和地支都会移动到下一个。例如 2021 年是辛丑年。

每过 60 年，天干会循环 6 轮，地支会循环 5 轮，所以天干地支纪年每 60 年轮回一次。例如 1900 年，1960 年，2020 年都是庚子年。

给定一个公元纪年的年份，请输出这一年的天干地支年份。

输入描述

输入一行包含一个正整数，表示公元年份。

其中有 ，输入的公元年份为不超过 9999 的正整数。

输出描述

输入一行包含一个正整数，表示公元年份。

输入输出样例

示例

输入

2020
1

输出

gengzi
1

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

5.1 简单分析

我们需要先找到公元 0 年的天干地支，然后用列表分别存储天干和地支表，然后我们输入的其他年份通过取余判断该年天干和地支在表中的位置。

5.2 公元 0 年的天干地支

天干循环周期为：10，地支循环周期为：12。

题目中说 2020 年是庚子年，因为 2020 % 10 = 0，说明公元 0 年的天干为：庚。又因为 2020 % 12 = 4。由于我们需要向前推 4 个才能找到公元 0 年的地支。所以我们可以得到公元 0 年的地支为：申。综上所述，公元 0 年的天干地支为：庚申年。

所以我们重新制定天干地支表：

# 字符列表
tg = ["geng", "xin", "ren", "gui", "jia", "yi", "bing", "ding", "wu", "ji"]
dz = ["shen", "you", "xu", "hai", "zi", "chou","yin", "mou", "chen", "si", "wu", "wei"]
1
2
3

5.3 主函数

输入的其他年份通过取余判断该年天干和地支在表中的位置。取模后等于 0 说明在第 0 位，等于 1 说明 在第1位。

if __name__ == '__main__':
    year = int(input())
    # 天干地支无间隔
    print(tg[year % 10], dz[year % 12], sep='')
1
2
3
4

6. 完整代码

以上实例的完整代码可在 我的仓库免费查看，如果无法使用可以及时私信我或在评论区指出，谢谢。

本文主要参考蓝桥杯省赛14天夺奖冲刺营，有兴趣的可以自己在蓝桥杯官网搜索

如有错误，敬请指正，欢迎交流🤝，谢谢♪(･ω･)ﾉ