高中信息技术之递归题解（一）

1. 爬楼梯#

爬一个 n 级楼梯，他一步可以最多爬 k 级楼梯，并且他每步至少爬一级台阶（他不能爬小数级台阶，也不能往回走）。

输入两个数 n 和 k ，你需要输出 n 个数，分别表示他走 1 步爬完楼梯的方案数，走 2 步爬完楼梯的方案数，⋯，走 n 步爬完楼梯的方案数。

1
ans = [0 for _ in range(1145)]
2

3
def solve(step, height):
4
    if(height > n):
5
        return
6
    elif(height == n):
7
        ans[step] += 1
8
        return
9
    else:
10
        for i in range(1, k+1):
11
            solve(step+1, height+i)
12

13
n, k = map(int, input().split())
14
solve(0, 0)
15
print(*ans[1:n+1])

首先确定递归函数所要包含的状态：步数和爬到了第几级。然后确定边界条件：当超过了 height 时，即为到达终点，那么给当前步数的方案数加上一。最后确定起始条件：刚开始步数为 $0$ ，也是在第 $0$ 个台阶。

2. 跷跷板#

有 n 个人在玩翘翘板，你需要将这 n 个人分成两组，使他们的体重差最小。

2.1 常规做法#

考虑到对于每个人，可以将其体重放到组A，也可以放到组B，那么我们就可以在每一个分支的时候进行两种情况的下一轮递归。代码如下：

1
g1 = []
2
g2 = []
3
ans = 11145141919810
4
def dfs(step):
5
    global ans
6
    if(step==n):
7
        ans = min(ans, abs(sum(g2) - sum(g1)))
8
    else:
9
        g1.append(w[step])
10
        dfs(step+1)
11
        g1.pop(-1)
12
        g2.append(w[step])
13
        dfs(step+1)
14
        g2.pop(-1)
15

16
n = int(input())
17
w = list(map(int, input().split(" ")))
18

19
dfs(0)
20
print(ans)

其中， g1 g2 为体重的列表。当步数到达 $n$ 时即为到达终点，那么计算最小体重差；否则进行枚举，若选取其到组A，就放进去；然后考虑组B，但在考虑组B前，要先清除之前的状态，我们称之为回溯，先 pop 掉之前数组里的内容，然后再进行新的枚举。

2.2 二进制枚举#

对于这类 0/1 问题，我们还可以使用二进制枚举，使得空间更小且时间复杂度常数更小。

1
bi = 0
2
n = int(input())
3
a = list(map(int, input().split()))
4
ans = 1145141919810
5

6
while bi < (1 << (n + 1)):
7
    su = [0, 0]
8
    for i in range(n):
9
        stat = 1 & (bi >> i)
10
        su[stat] += a[i]
11
    ans = min(abs(su[0] - su[1]), ans)
12
    bi += 1
13
print(ans)

对于每一个二进制位，它表示的是组A或组B，然后进行计算。

3. 数的拆分#

任何一个大于 1 的自然数 n，总可以拆分成若干个小于 n 的自然数之和。

现在给你一个自然数 n，要求你求出 n 拆分成一些数字的和的方式。

假设当前 dfs 传进来一个要拆分的数字。那么，我们可以考虑先从这个大数中分离出一个小数出来。显然，这个小数的范围为 $0 \sim (n-1)$ 。又因为我们需要将数字从小到大排列，那么在枚举拆出来的小数的时候，从已拆出数列表的最后一个开始枚举起即可。

1
n = int(input())
2
arr = []
3
def dfs(step):
4
    if(sum(arr)==n):
5
        for i in range(len(arr)):
6
            print(arr[i], end="+" if i != len(arr)-1 else "\n")
7
    elif(sum(arr)>n):
8
        return
9
    else:
10
        if(not arr):
11
            for i in range(1, n):
12
                arr.append(i)
13
                dfs(step+1)
14
                arr.pop(-1)
15
        else:
16
            for i in range(arr[-1], n - sum(arr) + 1):
17
                arr.append(i)
18
                dfs(step+1)
19
                arr.pop(-1)
20
dfs(0)

4. 全排列#

按照字典序从小到大输出长度为 n 的全排列。

首先生成一个从 $1 \sim n$ 的数列，然后新引入一个标记是否用过的数组 used ，如果已经使用过，那么在下一轮递归的时候就不考虑再使用这个数字了。

1
n = int(input())
2
arr = []
3
used = [False for i in range(n+1)]
4
def dfs(step):
5
    if(len(arr)==n):
6
        print(*arr)
7
    else:
8
        for i in range(1, n+1):
9
            if(not used[i]):
10
                used[i] = True
11
                arr.append(i)
12
                dfs(step+1)
13
                used[i] = False
14
                arr.pop(-1)
15
dfs(0)

5. 走迷宫#

斯宝走进了另一个迷宫。

这个迷宫共有 n×m 个格子，第 i 行第 j 个格子用 (i,j) 表示。

每个格子共有两个状态：

. 表示这个位置是个空地，可以行走。
# 表示这个位置是堵墙，不能行走，也不能穿过。

斯宝每次可以从一个位置，向上下左右四个方向走一格，但是不能跃出迷宫外。具体的，如果她在 (i,j) ，那么她可以到达 (i−1,j),(i,j−1),(i+1,j),(i,j+1) 四个位置（如果四个位置都在迷宫内）。

斯宝一开始在 (1,1) 位置，她希望能走到 (n,m) ，可是她现在在迷宫里面，所以请求你帮助她求出任意一种，能到达 (n,m) 的方案。

如果没有可行的方案，输出 -1。

保证 (1,1) 和 (n,m) 两点为空地。

这是属于图的搜索，对于每一点，我们可以从上、下、左、右四个方向进行下一轮递归。递归时注意边界，不能越界；同时保存路径，在回溯时及时弹出旧的废弃路径。

1
inp = input().split()
2
n, m = int(inp[0]), int(inp[1])
3
mp = []
4
for i in range(n):
5
    s = input()
6
    mp.append([c for c in s])
7

8
# print(n, m, mp)
9

10
vis = [[False] * m for _ in range(n)]
11
path = []
12
Flag = False
13

14
def output():
15
    print(len(path))
16
    for i in path:
17
        print(i[0] + 1, i[1] + 1)
18

19
def dfs(x, y):
20
    path.append((x, y))
21
    if x == n - 1 and y == m - 1:
22
        Flag = True
23
        output()
24
        exit(0)
25
    vis[x][y] = True
26
    dx = [-1, 0, 1, 0]
27
    dy = [0, 1, 0, -1]
28
    for i in range(4):
29
        nx = x + dx[i]
30
        ny = y + dy[i]
31
        if nx >= 0 and nx < n and ny >= 0 and ny < m and not vis [nx][ny] and mp[nx][ny] == '.':
32
            dfs(nx, ny)
33
    path.pop()
34

35
dfs(0, 0)
36

37
if not Flag:
38
    print(-1)