【Educoder离散数学实训】计算机问题求解之递归 ※

【Educoder离散数学实训】计算机问题求解之递归 ※

关于递归，其实简单讲就是自己调用自己。往细了说，分为递归和回溯两个部分。只不过这个实训没真正意义上用到回溯而已。

T1 基于递推公式的递归

老规矩，稍微聊两句。这种基于递推公式、动态规划等方式的递归都是树形结构，其本质都是遍历，没必要递归的。之后有几个题我没写递归，直接循环就行。

#第一题
def power(a, n):
    #**********  Begin  **********#
    if n == 0 :
        return 1
    elif n == 1 :
        return a
    else :
        return a * power(a, n - 1)
    #**********  End  **********#
…
    print('*' * 20)

    for n in range(11):
        print(fib2(n))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

T2 无递推公式的递归

这个题给我们一种思路，递归其实就是数学归纳。
本质上讲，递归就是从终点开始考虑问题。

#第一题
def isPal(s):
    # 请在下面编写代码
    n = len(s)
    if n == 0 or n == 1 :
        return True
    else :
        if s[0] == s[-1] :
            return isPal(s[1 : n - 1])
        else :
…    for n in range(6):
        print(vonNeumann(n))
        
    ALPHABET = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
    for n in range(1,5):
        print('*' * 20)
        string = ALPHABET[:n]
        print(perm(string))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

T3 递归与数学归纳法

注意前两个排序需要直接修改序列，我第二种排序更改了主函数的输出方式。

from random import *

#第一题
def findNomap(A, f):
    for a in A:
        mapped = False
        for m in f:
            if m[1] == a:
                mapped = True
                break
        if mapped == False:
            return a
    return None

def mapping(A, f):
    # 请在下面编写代码
    #**********  Begin  **********#
    n = len(A)
    if n == 1 :
        return A
    else :
        mdl = findNomap(A, f)
        if mdl :
            A.remove(mdl)
            for x in f :
                if x[0] == mdl or x[1] == mdl :
                    f.remove(x)
            return mapping(A, f)
        else :
            return A
    #**********  End  **********#
    # 请不要修改下面的代码


#第二题
def InsertSort(seq, i):
    # 请在下面编写代码
    #**********  Begin  **********#
    if i == 0 :
        return
    else :
        i = i + 1
        mdl = seq[:i - 1]
        InsertSort(mdl, i - 2)
        for j in range(i - 1) :
            if mdl[j] > seq[i - 1] :
                for k in range(j) :
                    seq[k] = mdl[k]
                seq[j] = seq[i - 1]
                for k in range(j, i - 1) :
                    seq[k + 1] = mdl[k]
                return
        for j in range(i - 1) :
            seq[j] = mdl[j]
    #**********  End  **********#
    # 请不要修改下面的代码


#第三题
def SelectSort(seq, i):
    # 请在下面编写代码
    #**********  Begin  **********#
    if i == 0 :
        return seq
    else :
        # print(seq, i)
        i = i + 1
        mx, Id = seq[0], 0
        for j in range(1, i) :
            if seq[j] > mx :
                mx, Id = seq[j], j
        return SelectSort(seq[:Id] + seq[Id + 1:], i - 2) + [mx]
    #**********  End  **********#
   
    #请不要修改下面的代码


#第四题
def QuickSort(seq):
    #请在下面编写代码
    #**********  Begin  **********#
    n = len(seq)
    if n == 1 :
        return seq
    elif n == 0 :
        return seq
    else :
        L1, L2 = [], []
        for i in range(1, n) :
            if seq[i] < seq[0] :
                L1.append(seq[i])
            else :
                L2.append(seq[i])
        return QuickSort(L1) + [seq[0]] + QuickSort(L2)
    #**********  End  **********#
    #请不要修改下面的代码


if __name__=="__main__":
    f = [(1, 3), (2, 1), (3, 1), (4, 5), (5, 5), (6, 4), (7, 6)]
    g = [(1, 3), (3, 1), (4, 5), (6, 4), (5, 7), (7, 6)]
    h = [(1, 3), (3, 2), (4, 4), (6, 7), (2, 2), (7, 5)]
    for l in [f, g, h]:
        A = [1, 2, 3, 4, 5, 6, 7]
        print(mapping(A, l))

    print('*' * 20)

    seed(999)
    test = [[],[],[],[]]
    for i in range(4):
        for j in range(10):
            test[i].append(randint(1,100))

    for l in test:
        InsertSort(l, len(l)-1)
        print(l)

    print('*' * 20)

    seed(9999)
    test1 = [[], [], [], []]
    for i in range(4):
        for j in range(10):
            test1[i].append(randint(100, 1000))

    for l in test1:
        print(SelectSort(l, len(l) - 1))

    print('*' * 20)
    seed(99999)
    test2 = [[], [], [], []]
    for i in range(4):
        for j in range(10):
            test2[i].append(randint(10, 1000))

    for l in test2:
        print(QuickSort(l))


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

T4 递归与动态编程

确实没有啥递归的必要，有两个题直接循环就完事儿了。
至于那个$memo$，意义在于有些位置会被递归多次。例如说一个位置$cos{t}_{i,j}$，只要有$x\ge i$且$y\ge j$，那么$(i,j)$这个位置就会被递归一次。非常的耗时间而且没意义。那么我们用一个$memory$数组，如果这个位置被递归过就存下来即可。

from random import *
from time import clock
#**********  Begin  **********#
#第一题
def minPathCost(cost, i, j):
    # 请在下面编写代码
    #**********  Begin  **********#
    # if i == 0 and j == 0 :
    #     return cost[0][0]
    # Min = 10**10
    # if i > 0 :
    #     Min = min(Min, minPathCost(cost, i - 1, j))
    # if j > 0 :
    #     Min = min(Min, minPathCost(cost, i, j - 1))
    # Min += cost[i][j]
    # return Min
    f= []
    for x in range(i + 1) :
        mdl = [0] * (j + 1)
        f.append(mdl)
    for x in range(i + 1) :
        for y in range(j + 1) :
            if x == 0 and y == 0 :
                f[x][y] = cost[x][y]
                continue
            f[x][y] = 10 ** 10
            if x > 0 :
                f[x][y] = min(f[x][y], f[x - 1][y])
            if y > 0 :
                f[x][y] = min(f[x][y], f[x][y - 1])
            f[x][y] += cost[x][y]
    return f[i][j]
    #**********  End  **********#
    # 请不要修改下面的代码


#第二题
def minPathCost_Memo(cost, i, j, memo):
    # 请在下面编写代码
    #**********  Begin  **********#
    if memo[i][j] :
        return memo[i][j]
    if i == 0 and j == 0 :
        memo[i][j] = cost[i][j]
        return cost[0][0]
    Min = 10**10
    if i > 0 :
        Min = min(Min, minPathCost(cost, i - 1, j))
    if j > 0 :
        Min = min(Min, minPathCost(cost, i, j - 1))
    Min += cost[i][j]
    memo[i][j] = Min
    return Min
    #**********  End  **********#
    # 请不要修改下面的代码

#第三题
def countWays(n):
    # 请在下面编写代码
    #**********  Begin  **********#
    if n == 1 :
        return 1
    elif n == 2 :
        return 2
    else :
        return countWays(n - 1) + countWays(n - 2)
    #**********  End  **********#
    # 请不要修改下面的代码

#第四题
def countWays_Memo(n, memo={}):
    # 请在下面编写代码
    f = [0] * (n + 2)
    f[1], f[2] = 1, 2
    for i in range(3, n + 1) :
        f[i] = f[i - 1] + f[i - 2]
    return f[n]
    #**********  End  **********#
    # 请不要修改下面的代码
#**********  end  **********#

if __name__=="__main__":
    randseeds = [9, 99, 999, 9999, 99999]
    for trial in range(5):
        seed(randseeds[trial])
        cost = []
        for i in range(10):
            temp = []
            for j in range(10):
                temp.append(randint(1,10))
            cost.append(temp)

        #start = clock()
        print(minPathCost(cost, 9, 9))
        #print(clock() - start)

    print('*' * 20)

    randseeds = [9, 99, 999, 9999, 99999]
    for trial in range(5):
        seed(randseeds[trial])
        cost = []
        for i in range(100):
            temp = []
            for j in range(100):
                temp.append(randint(1, 10))
            cost.append(temp)

        memo = []
        for i in range(100):
            memo.append([0] * 100)
        #start = clock()
        print(minPathCost_Memo(cost, 99, 99, memo))
        #print(clock()-start)

    print('*' * 20)

    for n in range(25,35):
        print(countWays(n))
    print('*' * 20)

    for n in range(90,100):
        print(countWays_Memo(n))





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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128