递推和递归

概念

  • 递归: 从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问题，是逆向的
  • 递推: 是从简单问题出发，一步步的向前发展，最终求得问题。是正向的

一般来说，递推的效率高于递归(当然是递推可以计算的情况下)，比如：斐波那契数列

案例

递归实现指数型枚举

题目

描述

从 $1∼n$ 这 $n$ 个整数中随机选取任意多个，输出所有可能的选择方案

难度

简单

输入格式

输入一个整数 $n$

输出格式

每行输出一种方案

同一行内的数必须升序排列，相邻两个数用恰好 $1$ 个空格隔开。

对于没有选任何数的方案，输出空行

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意

数据范围

输入样例

1
3

输出样例

1
2
3
4
5
6
7
3
2
2 3
1
1 3
1 2
1 2 3

求解

递归方式

1
2
3
4
5
6
7
8
9
10
11
n = input()

def dfs(u, state):
    if u == n:
        res = [str(i + 1) for i in range(n) if state >> i & 1]
        print(" ".join(res))
        return
    dfs(u + 1, state)
    dfs(u + 1, state | 1 << u)
    
dfs(0, 0)

位运算方式

给定n，求出$[1,n]$的组合，比如$n=5$，其组合数为$C_5^1+C_5^2+C_5^3+C_5^4+C_5^5 = 32$

这里可以把每位是否选择用$n$位的二进制表达，比如$11 \cdots 11$，一直减1，减到0时结束，期间每个二进制就是选择的结果，输出对应结果就好

1
2
3
4
5
6
7
8
9
10
11
def solution(n):
    a = 1 << n
    ct = 0
    import time
    t0 = time.time()
    res = []
    while a := a - 1:
        ct += 1
        res.append(bin(a))
    print('\n'.join(res))
    print("ct", ct, time.time() - t0)

递归实现组合型枚举

题目

描述

从 $1∼n$ 这 $n$ 个整数中随机选取$m$个，输出所有可能的选择方案

难度

简单

输入格式

两个整数 $n$，$m$在同一行用空格隔开

输出格式

按照从小到大的顺序输出所有方案，每行 1 个

首先，同一行内的数升序排列，相邻两个数用一个空格隔开

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）

数据范围

输入样例

1
5 3

输出样例

1
2
3
4
5
6
7
8
9
10
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5

求解

递归方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = input()
m = input()


def dfs(u, sum_, state):
    # 不满足要求的剪枝
    if sum_ + n - u < m:
        return
    if u == n:
        res = [str(i + 1) for i in range(n) if state >> i & 1]
        print(" ".join(res))
    dfs(u + 1, sum_, state)
    dfs(u + 1, sum_ + 1, state | 1 << u)

dfs(0, 0, 0)

位运算方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def lowbit(x: int):
    return x & -x    

def cal_one(v):
    ct = 0
    while v:
        v -= lowbit(v)
        ct += 1
    return ct


def solution_m(n, m):
    # 获取m位的组合
    a = 1 << n
    ct = 0
    while a := a - 1:
        if cal_one(a) == m:
            ct += 1
            print(bin(a))
    print("ct", ct)


if __name__ == '__main__':
    solution_m(5, 3)

递归实现排列型枚举

题目

描述

从 $1∼n$ 这 $n$ 个整数排成一行后随机打乱顺序，输出所有可能的次序

难度

简单

输入格式

一个整数 $n$

输出格式

按照从小到大的顺序输出所有方案，每行 1 个

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

输入样例

1
3

输出样例

1
2
3
4
5
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

思路

每次选取没有选过的数

求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = input()
path = []


def dfs(u, state):
    if u == n:
        print(" ".join(path))
        return

    for i in range(n):
        if not (state >> i & 1):
            path.append(str(i + 1))
            dfs(u + 1, state | (1 << i))
            path.pop()

dfs(0, 0)

费解的开关

题目

描述

求a的b次方对p取模的值

难度

简单

输入格式

三个整数a,b,p，在同一行用空格隔开

输出格式

输出一个整数，表示$(a^b) \% p$的结果

数据范围

输入样例

1
2
3 2 7
123456789 0 1

输出样例

1
2
2
0

思路

快速幂

1
2
3
4
5
6
7
8
9
10
11
3 ^ 10000000

# 先计算出
3 ^ 1 = 3
3 ^ 2 = 9
3 ^ 4 = 81
3 ^ 8 = 
3 ^ 16 = 
3 ^ 32 = 
...
3 ^ (2^19) = xxx

🥕核心: 再看下10000000的二进制表示，把对应为1的位乘起来就可以

10000000的二进制表示为0b100110001001011010000000，因此只要对应位置的值乘起来就是3 ^ 10000000

🥕根据数学常识，每一个正整数可以唯一表示为若干指数不重复的2的次幕的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def ck_sum_of_power(in_n: int):
    """
    检验整数可以由若干个不重复的2的次幂的和
    @param in_n:
    @return:
    """
    nb = in_n
    res = 0
    v = 1
    while nb:
        if nb & 1:
            res += v
        v *= 2
        nb >>= 1
    return res


if __name__ == '__main__':
    print(all([ck_sum_of_power(in_n=i) == i for i in range(100)]))

也就是说，如果b在二进制表示下有$k$位，其中第$i(0<i<k)$位的数字是$c_i$，则

于是

因为$k= \lceil log2(b+1) \rceil $，所以上式乘积项的数量不多于$\lceil log2(b+1) \rceil$个

又因为$a^{2^i} = {a^{(2^{i-1})}}^2$，所以我们很容易通过$k$次递推求出每个乘积项，当$c_i=1$时，把该乘积项累积到答案中

b&1运算可以取出b在二进制表示下的最低位，而b>>1运算可以舍去最低位，在递推的过程中将二者结合，就可以遍历b在二进制表示下的所有数位$c_i$，整个算法的时间复杂度为O($log2(b)$)

求解

1
2
3
4
5
6
7
8
9
10
11
12
def solution(a: int, b: int, p: int) -> int:
    res = 1 % p
    while b:
        # 如果b的个位是1
        if b & 1:
            res = res *  a % p
        # 准备十位
        a = a * a % p
        # 去掉各位
        b >>= 1

    return res

三层汉诺塔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def hanoi(n, from_, temp, to):
    """
    @param n: 剩余盘子数量
    @param from_: 当前位置
    @param temp: 临时位置
    @param to: 目标位置
    @return:
    """
    if n == 1:
        print(from_ + " -> " + to)
        return
    hanoi(n - 1, from_, to, temp)
    print(from_ + " -> " + to)
    hanoi(n - 1, temp, from_, to)


def solution(n: int, from_, temp, to):
    hanoi(n, from_, temp, to)


if __name__ == '__main__':
    solution(n=3, from_='A', temp='B', to='C')
    
# 输出
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

🐸青蛙跳阶

题目

思路

  • 递归: 青蛙跳阶可以使用递归求解
  • 带记忆的递归: 而递归求解中存在大量的重复计算，可以引入状态记忆，避免大量的重复计算
  • 递推: 除了递归方式，也可以使用递推的方式计算，目标是算出F(1)、F(2)…F(N)，只需要两个状态变量存储
  • 动态规划: 使用动态规划的方式，拆分子问题，记住过往，减少重复计算，关键在于状态转移转矩阵计算状态转移

求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from functools import lru_cache

@lru_cache()
def fab(n: int):
    # 带记忆的递归
    return 1 if n <= 1 else fab(n - 1) + fab(n - 2)

def fab_no_stock(n: int):
    # 递推
    res = 0
    one, two = 1, 1
    while n := n - 1:
        res = one + two
        one, two = two, res
    return res

if __name__ == '__main__':
    p_t = 10
    res = fab(n=p_t)
    print(res)

    res_no = fab_no_stock(n=p_t)
    print(res_no)