1. 梁山好汉行酒令
梁山移动有108位好汉（从1开始，到108），某日聚餐，大家按照顺序围坐一圈。开始行酒令。酒令是从1开始逐个报数，遇到7的倍数（例如14、28等），或者遇到所报的数字中某一位中含有7的情况（例如27，71, 700，979等），那么报数的好汉就要喝一杯酒。当第108位好汉报过数之后，接着由第1位好汉报。 本次宴会从1报数到999。请问喝酒杯数最多的好汉是第几位好汉，喝了几杯酒。请问喝酒杯数最少的好汉是第几位好汉，喝了几杯酒。（最多，最少均可能是1位，也可能是几位） 答： 喝的最多的是第____条好汉，喝了 杯酒； 喝的最少的是第____条好汉，喝了 杯酒；
解析
# 用字典为好汉记数，初始值为0 喝一杯就加1。
d = dict(zip(range(108), [0]* 108)) # 生成好汉序号字典
for i in range(1,1000): # 循环报数
if i % 7 == 0 or '7' in str(i): # 喝酒条件
d[i%108] += 1
# print(d)
for k,v in d.items():
if v == max(d.values()) or v == min(d.values()): # 挑出喝最多和最少的好汉
print(f'第{k}条好汉，喝了{v}杯酒')
"""
第44条好汉，喝了1杯酒
第63条好汉，喝了7杯酒
第80条好汉，喝了1杯酒
第94条好汉，喝了1杯酒
"""
这个题目思路好理解，难的地方是好汉的序号要怎么和报数对应起来。好汉序号是从1开始的，报数也是从1开始的，我是卡了很长时间，最后才弄明白，序号为0的那个好汉 (i%108=0) 对应的就是第108好汉。
2. 小兔子上台阶
已知小兔子上楼梯时每次只能跨 1 或 2 个阶梯，并在任意时刻可以选择一步跨三阶，但至多只能使用一次，假定小兔子从地面(第0阶)开始上台阶，要上到第 n 个阶梯共有多少种走法并输出走法? 答： 10个台阶，____种跳法； 15个台阶，__种跳法； 20个台阶，__种跳法； 25个台阶，__种跳法； 33个台阶，____种跳法；
解析
这个题目考试时没做出来。比较难，是斐波那契数列的变种。
由于跳三阶只有0或1次机会，要分两种情况来考虑，最终的结果为两种方法相加。
当不使用跳3阶时，要跳到第10阶，有两种方法，从第9阶跳1，或从第8阶跳2。通项公式为 f(n) = f(n-1) + f(n-2)，是典型的fibnaci数列。
当必须使用1次跳3阶时，因为走法是区分先后顺序的，要跳到第10阶，可以从第7阶跳3到10阶，也可以从任意时刻跳3。遇到这种想不清楚的问题，用纸列一下，看看有没有规律，这里假定n=10阶，看看在不同的时刻跳3，有什么规律。把用普通方法跳到台阶n记作fib(n)
- 0阶，直接跳3，跳完后还有7阶，方法为fib(7)
- 1阶，先跳到1阶，只有1种跳法，再跳3，跳完还有6阶，方法为 fib(6)
- 2阶，先跳到2阶，有fib(2)种跳法，再跳3，跳完后还有5阶，方法为
fib(2)*fib(5) - 3阶，先跳到3阶，有fib(3)种跳法，再跳3，跳完后还有4阶，方法为
fib(3)*fib(4) - 4阶，先跳到4阶，有fib(4)种跳法，再跳3，跳完后还有3阶，方法为
fib(4)*fib(3) - 5阶，先跳到5阶，有fib(5)种跳法，再跳3，跳完后还有2阶，方法为
fib(5)*fib(2) - 6阶，先跳到6阶，有fib(6)种跳法，再跳3，跳完后还有1阶，方法为
fib(6)*fib(1) - 7阶，先跳到7阶，有fib(7)种跳法，再跳3，跳完后还有0阶，方法为
fib(7)*fib(0)
从上面的分析可以看出， 跳3的位置非常重要。总结的规律为n级台阶，在其中i处使用跳3，方法有 f(i)*f(n-3-i)种。只需要遍历(n-3) 将次数相加即可。
def fib(n: int) -> int :
# 当前项为前2项和的fib函数，迭代算法
ans = [1] * (n+1) # 存储每一项计算结果，方便复用
for i in range(1,n+1):
ans[i] = sum(ans[max(0,i-2):i]) # ans[i] = ans[i-2] + ans[i-1]
return ans[-1]
def jump_3(n: int) -> int:
# 必须使用1次跳3级时
if n < 3:
return 0
ans = [0] * (n-2) # 边界为 n-3 + 1
for i in range(n-2):
ans[i] = fib(i)*fib(n-i-3)
return sum(ans)
def test():
# test_nums = range(1, 11)
test_nums = [10,15,20,25,33]
print(f"层数 -- 不跳3次数 -- 必须跳3次数 -- 合并后结果")
for num in test_nums:
print(f'{num}--{fib(num)}--{jump_3(num)}--{fib(num)+jump_3(num)}')
if __name__ == "__main__":
test()
'''
层数 -- 不跳3次数 -- 必须跳3次数 -- 最终结果
10--89--130--219
15--987--2285--3272
20--10946--34690--45636
25--121393--488400--609793
33--5702887--30737759--36440646
'''
这道题目的标准答案是用动态规划解，非常简洁优雅。
到n层的所有走法有两部分构成，一是到n-1层和n-2层的所有走法，因为跳1，2是没有限制的。
二是加上没有跳过3时，到n-3层的走法。 res[i] = res[i-1] + res[i-2] + only2[i-3]
def jump(n):
res = [0, 1, 2, 4] # 到n层的所有合法的走法
only2 = [0, 1, 2, 3] # # 到n层每次只走一、二阶的走法
for i in range(4, n+1):
res.append(res[i-1] + res[i-2] + only2[i-3])
only2.append(only2[i-1] + only2[i-2])
return res
if __name__ == '__main__':
n = 33
res = jump(n)
for i in range(1,n+1):
print('台阶数量：{}， 兔子跳法：{}。'.format(i, res[i]))
3. 蚂蚁搬家
蚂蚁准备搬家，蚂蚁的老家在原点（0,0），蚂蚁从原点（0,0）开始在平面中移动寻找新家。 蚂蚁一次移动可以通过给定的距离向上，向下，向左和向右移动。 蚂蚁每次移动的距离是大于0小于10的整数，移动的方向只有上、下、左、右四个方向。蚂蚁可能经过若干次移动后找到新家，找到新家后即停止移动。 例如蚂蚁运动的痕迹如下所示： UP 5 DOWN 3 LEFT 3 RIGHT 2 方向之后的数字是移动的距离。 请编写一个程序来计算蚂蚁一系列移动之后，新家（完成最后一次移动后的位置）与老家（原点）的距离。如果距离是浮点数，则输出最接近的整数。 例：如果给出以下列表作为程序的输入：[‘UP 5’,’DOWN 3’,’LEFT 3’,’RIGHT 2’]，程序的输出应该是：2 答： 输入：[‘UP 5’,’DOWN 3’,’LEFT 3’,’RIGHT 2’,’UP 7’,’RIGHT 8’,’UP 9’,’RIGHT 8’] 输出：_____
解析
这个题目相对简单，根据输入，调整蚂蚁的坐标(x,y)，初始的坐标为(0,0)，最终的距离$l=\sqrt{x^2 + y^2}$
def ant(s):
x,y = 0,0 # x为横坐标，y为纵坐标
for i in s:
action, step = i.split()
if action == 'UP':
y += int(step)
elif action == 'DOWN':
y -= int(step)
elif action == 'LEFT':
x -= int(step)
elif action == 'RIGHT':
x += int(step)
return round((x**2 + y**2)**0.5) # 注意题目要求四舍五入
if __name__ == '__main__':
ss = [
['UP 5','DOWN 3','LEFT 3','RIGHT 2','UP 7','RIGHT 8','UP 9','RIGHT 8'],
['RIGHT 5','DOWN 3','UP 7','RIGHT 1','UP 5','RIGHT 4','LEFT 3','RIGHT 2','UP 3','RIGHT 6'],
['DOWN 6','UP 7','RIGHT 1','LEFT 7','UP 5','RIGHT 9','RIGHT 4','LEFT 2','RIGHT 2','UP 8','RIGHT 6'],
['RIGHT 1','UP 7','UP 4','DOWN 3','LEFT 3','RIGHT 6','UP 7','RIGHT 2','UP 9','RIGHT 8','UP 1','RIGHT 3'],
['DOWN 5','LEFT 3','RIGHT 9','RIGHT 1','UP 7','UP 4','RIGHT 2','UP 9','RIGHT 1','UP 1','LEFT 3','UP 5',],
['UP 4','DOWN 3','LEFT 3','RIGHT 1','UP 7','RIGHT 6','UP 7','UP 9','LEFT 8','UP 1','RIGHT 2','DOWN 9','RIGHT 8','UP 2','RIGHT 3'],
['RIGHT 6','UP 7','RIGHT 2','RIGHT 1','UP 7','UP 5','RIGHT 8','UP 1','UP 4','DOWN 4','LEFT 3','RIGHT 8'],
['RIGHT 2','UP 5','DOWN 3','LEFT 8','RIGHT 6','DOWN 5','RIGHT 1','UP 2','UP 4','DOWN 3','LEFT 3','RIGHT 9','UP 7','UP 1','RIGHT 3'],
['UP 5','RIGHT 8','UP 1','RIGHT 4','UP 7','RIGHT 2','RIGHT 5','UP 7','UP 5','RIGHT 8','UP 1','UP 2','DOWN 4','LEFT 3','RIGHT 8'],
['DOWN 3','LEFT 1','RIGHT 2','RIGHT 5','UP 7','RIGHT 2','RIGHT 9','UP 7','UP 5','RIGHT 2','UP 1','UP 4','DOWN 2','LEFT 3','RIGHT 8'],
]
for k,v in enumerate(ss):
print(f'第{k+1}个，首动作为{v[0]},距离为{ant(v)}')
4. 机器人集合
多个机器人分布在M*N(10≤M,N≤1000)的方格中，每个机器人分布在不同的方格里。规定每个机器人只
能向上下左右的相邻方格移动，每移动一个方格需要消耗1个单位能量。现在要求所有机器人集合，集合点只能是某个机器人初始所在方格。现在请找一个集合点，使得所有机器人到达该点消耗的总能量最低。输入说明：
第一行是一个整数K(0<K≤100)，表示机器人的总数。
之后集合中K组坐标，是每个机器人所在方格的位置，用[x,y]表示。
输出说明：
输出最低的总能量消耗。
输入样例：
4
[[4,5],[3,3],[2,2],[4,4]]
输出样例：7
答：
输入：
16
[[4,3],[3,6],[2,2],[7,4],[2,8],[5,1],[5,2],[1,1],[3,9],[4,8],[8,5],[7,5],[2,6],[7,3],[4,5],[5,5]]
输出：___
解析
集合点只能是某个机器人的位置，只需要遍历机器人，计算其他所有机器人到当前机器人的距离和，取最小值。
每一移动一格，消耗1单位能量，那个两个点之间需要的能量为 abs(x1-x2) + abs(y1-y2)
def min_power(points: list):
ans = float('INF') # 取一个无穷大，方便后续比较
for i in points:
d = 0
for j in points:
d += abs(i[0]-j[0])+abs(i[1]-j[1]) # 依次计算两两之间的距离
ans = min(d,ans) # 取能量最小的点
# print(f'集合位置{i}，所需能量{d}')
return ans
points = [[4,3],[3,6],[2,2],[7,4],[2,8],[5,1],[5,2],[1,1],[3,9],[4,8],[8,5],[7,5],[2,6],[7,3],[4,5],[5,5]]
print(min_power(points))
# 58
5. 计算山脊长度
游戏中的地图都是用二维数组表达的，每个位置一个整数表示高度，现在需要找出地图中的山脊设置防御工事。已知表示地图中各点的高度，用二维数组存放，请找出其中最长的山脊线。二维地图中山脊线的定义是行（或者列）上的连续点，且其上每点的上和下（或者左和右）两个方向的高度值都小于该点的高度值（边界线不满足山脊的定义）。
输入说明：第一行是整数N(0<N<1001)，表示二维数组的行数和列数。接下来是一个N行、N列的二维整数矩阵，每个数字表示地图上该点处的地面高度H(0<H<100)。
输出说明：输出最长山脊线的长度L和最长山脊线的最左（或最上）点的坐标X，Y。(1<=X，Y<=N)，具中X表示行，Y表示列。如果不存在这样的山脊线，输出0 -1 -1，测试数据中的山脊线只需考虑同一行或同一列的情形，不需要考虑斜线，测试数据中如果存在多个同样长度的最长山脊线，输出任意一个山脊线均可。
输入示例： 6 0 3 0 0 1 1 0 6 0 1 1 1 9 9 9 7 5 3 6 5 3 5 3 3 5 6 6 5 7 4 3 4 4 5 5 5 输出示例 L：5，X：3，Y:1
答： 输入：参见电子文件《question 5.txt》 输出： L: __，X: __，Y: __
解析
题目比较长，需要仔细阅读，尤其是山脊的定义要明确。我们需要输出山脊线的最大长度和对应的起点。 我的思路的遍历二维数组的每一个位置，在这个位置上 分别向下走和向右走，不满足条件就停止，记录长度，然后取两种走法的最大值，记为这个坐标的最大山脊长度。有了这个结果，只需再遍历一次，就能找到最大值和对应的坐标。
def shanji(data, M):
# 输入二维数组和边长，输出一个数组，记录每个位置山脊的长度
grid = [[0] * M for i in range(M)] # 存储结果
for i in range(M):
for j in range(M):
# 开始计算向右走
row = 0 # 保存行能走的长度
x,y = i,j # 临时坐标
while y < M:
if x == 0 or x == M-1: # 第一行和最后一行是边界，不能当山脊
break
if int(data[i][y]) > max(int(data[i+1][y]),int(data[i-1][y])): # 当前点比上下相邻点都大时长度加1
row += 1
y += 1 # 行号不变，列号自增
else:
break
# 开始计算向下走
col = 0 # 保存列能走的长度
x,y = i,j
while x < M:
if y == 0 or y == M-1: # 最左列和最右列是边界，不算山脊
break
if int(data[x][j]) > max(int(data[x][j+1]), int(data[x][j-1])): # 当前点比左右相邻点都大时长度加1
col += 1
x += 1 # 列号不变，行号自增
else:
break
# 取两个的最大值
grid[i][j] = max(row,col)
return grid
if __name__ == '__main__':
# 测试用例
test = [[0,3,0,0,1,1],
[0,6,0,1,1,1],
[9,9,9,7,5,3],
[6,5,3,5,3,3],
[5,6,6,5,7,4],
[3,4,4,5,5,5],
]
# print(shanji(test,len(test)))
# 读取数据
with open('question 5.txt','r') as f:
tmp = f.readlines()
M = int(tmp[0]) # 二维数组边长
data = []
for i in tmp[1:]:
data.append(i.split())
grid = shanji(data, M) # 生成结果矩阵，遍历找最大值
ans = 0
point = [0,0]
for i in range(M):
for j in range(M):
if grid[i][j] > ans:
ans = grid[i][j]
point[0],point[1] = i+1, j+1 # 坐标要从1开始数，所以结果加1
print(f'最长的山脊长度L为{ans}, 坐标为{point}')
# 最长的山脊长度L为10, 坐标为[26, 34]
6. 计算质因子
给一个正整数n，写出n的所有质因子乘积。
例如： n=90，输出 90=2*3*3*5
解析
这个题目是笔试题最后一个，需要手写代码。
要注意的地方是质因子可以重复，比如32 = 2*2*2*2*2
def factor(n):
# 输出质因子列表
ans = []
for i in range(2,n): # 从2到n-1，依次去整除n, 根据对称性，到(n+1) // 2 就可以了。
while n > 0 and n % i == 0: # 因为质因子可以重复，所以要用while循环来一直除
n = n // i
ans.append(str(i)) # 将数字转为字符串，方便后续打印输出
return ans
if __name__ == '__main__':
n = 90
ans = factor(n)
# 如果 n 为质数，ans 为空，需要调整下输出
if ans:
print(f"{n}={'*'.join(ans)}")
else:
print(f'{n}={n}')