递归与递推练习
文章目录
题目来自 AcWing
92. 递归实现指数型枚举 | 原题链接
使用 AcWing 上的挑战模式做题，所以码风看上去比较乱。
1n = int(input())
2nums = list(range(1, n + 1))
3
4def dfs(current, nums):
5 if len(nums) == 0:
6 print(" ".join(current))
7 return
8
9 dfs(current, nums[1:])
10 dfs(current + [str(nums[0])], nums[1:])
11
12dfs(list(), nums)
94. 递归实现排列型枚举 | 原题链接
全排列，一般做法：
1n = int(input())
2nums = {k: True for k in range(1, n + 1)}
3result = list()
4
5def dfs(current):
6 if not any(nums.values()):
7 result.append(" ".join(current))
8 return
9
10 for i in nums.keys():
11 if nums[i]:
12 current.append(str(i))
13 nums[i] = False
14 dfs(current)
15 current.pop()
16 nums[i] = True
17
18dfs(list())
19result.sort()
20print(*result, sep="\n")
Python 取巧做法：
1from itertools import permutations
2
3n = int(input())
4perm = permutations(range(1, n + 1))
5perm = map(lambda x: " ".join(map(str, x)), perm)
6print(*sorted(perm), sep="\n")
717. 简单斐波那契 | 原题链接
1n = int(input())
2
3if n == 1:
4 print(0)
5 exit(0)
6
7if n == 2:
8 print(1)
9 exit(0)
10
11fib = [0, 1]
12i = 2
13while i < n:
14 fib.append(fib[i - 1] + fib[i - 2])
15 i += 1
16
17print(" ".join(map(str, fib)))
95. 费解的开关 | 原题链接
这道题有点难住我了，最开始尝试广搜结果超时，深搜也超时，所以看了题解。题解中用的是模拟+递推的思想。
第一行的五个开关按与不按一共有 $2^5$ 种情况，对于每一种情况，都假设第一行开关的状态已经确定，如果此时要改变第一行灯的状态，则去按第二行的开关；当通过按第二行的开关将第一行的灯都打开后，第二行开关的状态已经确定，如果还需要更改第二行的灯的状态则去第三行……依此类推，直到第四行灯都打开而第五行开关状态确定时，检测第五行的灯是否全亮以及步数是否超过限制即可。
1def toggle(field, x, y):
2 field[x][y] = not field[x][y]
3 for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
4 nx, ny = x + dx, y + dy
5 if 0 <= nx < 5 and 0 <= ny < 5:
6 field[nx][ny] = not field[nx][ny]
7
8
9n = int(input())
10for i in range(n):
11 field = list()
12 for _ in range(5):
13 row = list(map(lambda x: bool(int(x)), list(input().strip())))
14 field.append(row)
15 if i != n - 1:
16 input()
17
18 result = set()
19 for j in range(0, 32):
20 step = 0
21 new_field = [row[:] for row in field]
22 status = bin(j)[2:].rjust(5, "0")
23 for s in range(5):
24 if status[s] == "1":
25 toggle(new_field, 0, s)
26 step += 1
27 for x in range(1, 5):
28 for y in range(5):
29 if not new_field[x - 1][y]:
30 toggle(new_field, x, y)
31 step += 1
32 if step <= 6 and all(new_field[4]):
33 result.add(step)
34 if len(result) == 0:
35 print(-1)
36 else:
37 print(min(result))
93. 递归实现组合型枚举 | 原题链接
搜索与回溯解法：
1def dfs(current, depth, k, nums):
2 if depth == k:
3 print(" ".join(current))
4 return
5
6 for i in range(len(nums)):
7 current.append(str(nums[i]))
8 dfs(current, depth + 1, k, nums[i + 1:])
9 current.pop()
10
11 return
12
13n, k = map(int, input().strip().split(" "))
14nums = list(range(1, n + 1))
15dfs(list(), 0, k, nums)
itertools.combinations 写法：
1from itertools import combinations
2
3n, k = map(int, input().strip().split(" "))
4comb = combinations(range(1, n + 1), k)
5for c in comb:
6 print(" ".join(map(str, c)))
1209. 带分数 | 原题链接
这道题大致的思路就是枚举 $a\space b\space c$ 的值，然后验证方程 $n=a+\frac bc$ 是否成立。对于这个题可以做如下优化：根据方程知道 $a<n$，所以枚举 $a$ 时，只需在位数小于等于 $n$ 的数字中枚举，且只有 $a<n$ 时才继续枚举另外两个变量；对原方程作变换后得到 $b=c\cdot(n-a)$，这样可以通过枚举 $a\space c$ 计算出 $b$，然后判断 $b$ 是否是由剩下的数字组合而成，而不需要再去枚举 $b$ 的值。
使用 Python 解决问题时，为了方便，使用 itertools 中的 combinations 与 permutations 函数。在枚举 $a\space c$ 时，首先确定位数，随后用 permutations 函数筛选出指定位数的各种组合，最后使用 combinations 函数生成对应的全排列，将每一种排列连接成数即是要枚举的数。
1from itertools import permutations, combinations
2
3
4n = input()
5length = len(n)
6n = int(n)
7nums = list(range(1, 10))
8count = 0
9
10
11def get_c(a, rest):
12 for i in range(1, len(rest) - 1):
13 perm_c = permutations(rest, i)
14 for p in perm_c:
15 comb_c = combinations(p, i)
16 for comb in comb_c:
17 c = int("".join(map(str, comb)))
18 b = n * c - a * c
19 b_rest = set(rest) - set(comb)
20 if len(str(b)) != len(b_rest):
21 continue
22 b_set = set(map(int, list(str(b))))
23 if b_rest == b_set:
24 global count
25 count += 1
26
27
28for i in range(1, length + 1):
29 perm_a = permutations(nums, i)
30 for p in perm_a:
31 comb_a = combinations(p, i)
32 for c in comb_a:
33 a = int("".join(map(str, c)))
34 if a < n:
35 rest = list(set(nums) - set(c))
36 get_c(a, rest)
37
38
39print(count)
116. 飞行员兄弟 | 原题链接
题目类似于费解的开关，想不到递推或者递归的写法，但是用广搜可以 AC。
因为最优解中肯定没有重复使用的开关，而且解与路径无关，因此给 16 个开关按照 0-15 编号，当一个开关被操作后，下一次操作只能在这个编号大于这个开关的开关中完成。
1from collections import deque
2
3
4def toggle(field, x, y):
5 new_field = [row[:] for row in field]
6 for i in range(4):
7 new_field[x][i] = not field[x][i]
8 new_field[i][y] = not field[i][y]
9 new_field[x][y] = not field[x][y]
10 return new_field
11
12
13field = list()
14for _ in range(4):
15 row = [True if s == "-" else False for s in input().strip()]
16 field.append(row)
17
18queue = deque()
19step = list()
20queue.append((field, step))
21
22while queue:
23 field, step = queue.popleft()
24 if all([all(s) for s in field]):
25 print(len(step))
26 for s in step:
27 print(" ".join(map(lambda x: str(x + 1), s)))
28 exit()
29
30 if not step:
31 last_x, last_y = (0, -1)
32 else:
33 last_x, last_y = step[-1]
34 for i in range(last_x * 4 + last_y + 1, 16):
35 curr_x = i // 4
36 curr_y = i % 4
37 new_field = toggle(field, curr_x, curr_y)
38 new_step = step[:]
39 new_step.append((curr_x, curr_y))
40 queue.append((new_field, new_step))
1208. 翻硬币 | 原题链接
1toggle = {"o": "*", "*": "o"}
2
3init = list(input().strip())
4dest = list(input().strip())
5
6if init == dest:
7 print(0)
8 exit()
9
10length = len(init)
11step = 0
12
13for i in range(length - 1):
14 if init[i] != dest[i]:
15 init[i] = toggle[init[i]]
16 init[i + 1] = toggle[init[i + 1]]
17 step += 1
18
19print(step)