数列求值
原题
给定数列 
，从第 项开始，每项都是前 项的和。
求第 项的最后 位数字。
枚举、取余
本题使用常规的枚举即可，就是计算数列的第i项(i=4, 5, 6, 7, ..., n)的数值，这里的n=20190324，但是需要考虑数列元素的数值越来越大，且本题要求最后一项（第n项）的最后4位数字，枚举时只要保持最后4位数的变化直至计算出最后一项。
做法是：当数列计算得到的当前项的数值较大时，进行取余取最后的指定位数（这里根据判断是否大于 t=100000，这里的t的取值有点讲究的，即要保持最后4位数的变化，考虑到从低到高的第4位数的满10进1的变化，t最合适的取值为10的（4+1)次方）。
源码
n = 20190324
a,b,c = 1,1,1
t = int(1e5)
for i in range(4,n+1):
a,b,c = b,c,a+b+c
if a > t:
a,b,c = a%t,b%t,c%t
print(c%10000)
注：运行时间2.7s左右
七段码
原题
小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示，数码管中一共有 段可以发光的二 极管，分别标记为 。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符 的表达时，要求所有发光的二极管是连成一片的。
例如： 发光，其他二极管不发光可以用来表达一种字符。
例如 发光，其他二极管不发光可以用来表达一种字符。这种方案与上 一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如： 发光， 不发光可以用来表达一种字符。
例如： 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
连通图与其子图
用数字1，2，3，4，5，6，7分别表示字母a~g，七段码可以转化为一个无向图（如下图，是一个7个结点的连通图），这样问题可以转化为求该连通图的子连通图的个数。
首先是对图的信息（结点和边的）进行录入，使用“二维数组”的形式，即邻接矩阵存储。Python中，列表p_l = [(),(2,6),(1,3,7),(2,4,7),(3,5),(4,6,7),(1,5,7),(2,3,5,7)] (见“源码”部分)存储上图中的连通图，p[i]是一个元组，存放与结点i有边连接的结点。
需要定义一个方法，输入是已访问结点的列表node_l、连通图子图的结点的个数num，具体实现见“源码”部分。这里的结点总数n=7，可以使用上述方法求结点个数为num(num=1, 2, ..., n)的不同子图。
源码
p_l = [(),(2,6),(1,3,7),(2,4,7),(3,5),(4,6,7),(1,5,7),(2,3,5,7)]
res_s = set()
def find_subGraph(node_l: list, num: int):
'''node_l存放当前子图的结点的列表，num为当前要找的子图的结点个数'''
# 当前子图结点个数达到要求
if len(node_l) == num:
res_s.add(tuple(sorted(node_l))) # 把子图结点排序并放入集合中，删选相同的子图
return
i = node_l[-1]
for node in p_l[i]:
# 若结点node未访问，则访问该结点（放入当前已访问结点的列表node_l）
if node not in node_l:
find_subGraph(node_l + [node], num)
for node in range(1,8): # 子图的第一个结点
for num in range(2,7): # 子图的结点个数（2~6）
find_subGraph([node],num)
# 只有一个结点的子图有7个，还有图本身也可以作为图的一个最大子图
print( 7+1+len(res_s) )
上一篇：蓝桥杯备战日志(Python)13-跳跃-(遍历、动态规划)
