【数据结构与算法——python】递归

递归

数列求和

$listSum(numList) = first(numList) + listSum(rest(numList))$

def listsum(numList):
    if len(numList) == 1:   # 最小规模
        return numList[0]
    else:                   # 减小规模
        return numList[0] + listsum((numList[1:]))

任意进制转换

def toStr(n, base):
    convertString = "0123456789ABCDEF"
    if n < base:
        return convertString[n]
    else:
        return toStr(n // base, base) + convertString[n % base]

递归可视化

螺旋线

import turtle
t=turtle.Turtle()
def drawSpiral(t,lineLen):
    if lineLen>0:
        t.forward(lineLen)
        t.right(90)
        drawSpiral(t,lineLen-5)

drawSpiral(t,100)
turtle.done()

分形树

import turtle


def tree(branch_len):
    if branch_len > 5:
        t.forward(branch_len)
        t.right(20)
        tree(branch_len - 15)
        t.left(40)
        tree(branch_len - 15)
        t.right(20)
        t.backward(branch_len)


t = turtle.Turtle()
t.left(90)
t.penup()
t.backward(100)
t.pendown()
t.pencolor('green')
t.pensize(2)
tree(75)
t.hideturtle()
turtle.done()

谢尔宾斯基三角形

import turtle
def draw_triangle(points, color, my_angle):
  my_angle.fillcolor(color)
  my_angle.up()
  my_angle.goto(points[0][0], points[0][1])
  my_angle.down()
  my_angle.begin_fill()
  my_angle.goto(points[1][0], points[1][1])
  my_angle.goto(points[2][0], points[2][1])
  my_angle.goto(points[0][0], points[0][1])
  my_angle.end_fill()
def get_mid(p1, p2):
  return ((p1[0]+p2[0])/2, (p1[1]+p2[1])/2)
def sierpinski(points, degree, my_angle):
  colormap = ['blue', 'red', 'green', 'yellow',
        'violet', 'orange', 'white']
  draw_triangle(points, colormap[degree], my_angle)
  if degree > 0:
    sierpinski([points[0],
          get_mid(points[0], points[1]),
          get_mid(points[0], points[2])],
          degree - 1, my_angle)
    sierpinski([points[1],
          get_mid(points[0], points[1]),
          get_mid(points[1], points[2])],
          degree - 1, my_angle)
    sierpinski([points[2],
          get_mid(points[2], points[1]),
          get_mid(points[0], points[2])],
          degree - 1, my_angle)
my_turtle = turtle.Turtle()
my_win = turtle.Screen()
my_points = [[-100, -50], [0, 100], [100, -50]]
sierpinski(my_points, 3, my_turtle)
my_win.exitonclick()

汉诺塔

def moveTower(height, fromPole, withPole, toPole):
    if height >= 1:
        moveTower(height - 1, fromPole, toPole, withPole)
        moveDisk(height, fromPole, toPole)
        moveTower(height - 1, withPole, fromPole, toPole)


def moveDisk(disk, fromPole, toPole):
    print(f"moving disk[{disk}] frm {fromPole} to {toPole}")

分治策略

优化问题——贪心策略

找零兑换问题

$numCoins=\begin{cases}1+numCoins(originalamount-1)\\1+numCoins(originalamount-5)\\1+numCoins(originalamount-10)\\1+numCoins(originalamount-25)\end{cases}$

# 1.如果可以直接找零，返回1
# 2.否则：
#   （1）遍历小于change的面值
#   （2）重新代入change值
#   （3）返回最小硬币数量
def recMc(coinValueList, change):
    minCoins = change
    if change in coinValueList:
        return 1
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMc(coinValueList, change - i)
            if numCoins < minCoins:
                minCoins = numCoins
        return minCoins

找零兑换缓存方法

# 增加中间结果表
def recDC(coinValueList, change, knownResults):
    minCoins = change
    if change in coinValueList:
        knownResults[change] = 1
        return 1
    elif knownResults[change] > 0:
        return knownResults[change]
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recDC(coinValueList, change - i, knownResults)
            if numCoins < minCoins:
                minCoins = numCoins
                knownResults[change] = minCoins
        return minCoins

找零兑换动态规划方法

# 从最小值开始到change值，逐个计算最少硬币数
#   1.初始化一个最大值
#   2.减去每个硬币，向后查找最少硬币数
#   3.得到当前最少硬币数，记录
# 返回最后结果
def dpMakeChange(coinValueList,change,minCoins):
    for cents in range(1,change+1):
        coinCount=cents
        for j in [c for c in coinValueList if c<=cents]:
            if minCoins[cents-j]+1<coinCount:
                coinCount=minCoins[cents-j]+1
        minCoins[cents]=coinCount

    return minCoins[change]

找零兑换动态规划方法扩展

# 从最小值开始到change值，逐个计算最少硬币数
#   1.初始化一个最大值
#   2.减去每个硬币，向后查找最少硬币数
#   3.得到当前最少硬币数，记录
# 返回最后结果
def dpMakeChange(coinValueList, change, minCoins, coinsUsed):
    for cents in range(1, change + 1):
        newCoin = 1  # 初始化新加硬币
        coinCount = cents
        for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents - j] + 1 < coinCount:
                coinCount = minCoins[cents - j] + 1
                newCoin = j # 对应最小数量，所减的硬币
        minCoins[cents] = coinCount
        coinsUsed[cents] = newCoin # 记录本步骤加的一个硬币

    return minCoins[change]


def printCoins(coinsUsed, change):
    coin = change
    while coin > 0:
        thisCoin = coinsUsed[coin]
        print(thisCoin)
        coin = coin - thisCoin

动态规划

背包问题

把$m(i,W)$记做：

​ 前 i $(1<=i<=5)$个物品中，组合不超过 W $(1<=W<=20)$重量，得到的最大价值$m(i,W)$应该是$m(i-1,W)$和$m(i-1,W-W_i)+W_i$两者的最大值。
$m(i,W)=\begin{cases}0 & \text{if }\quad i=0\\0 & \text{if }\quad W=0\\m(i-1,W) & \text{if }\quad w_i>W\\max\lbrace m(i-1,W),v_i+M(i-1,W-w_i)\rbrace & otherwise\end{cases}$

# 1.初始化：
#   （1）初始化物品重量和价值
#   （2）初始化最大承受重量
#   （3）初始化二维表格
#           表示前i个物品中，最大重量w的组合，所得到的最大价值
#           当i不取值，或w上限为0，价值为0
# 2.填写二维表格
#   （1）重量超出：放弃该物品
#   （2）比较装与不装的价值

tr = [None,
      {'w': 2, 'v': 3}, {'w': 3, 'v': 4},
      {'w': 4, 'v': 5}, {'w': 5, 'v': 8},
      {'w': 9, 'v': 10}]

max_w = 20

m = {(i, w): 0 for i in range(len(tr))
     for w in range(max_w + 1)}

for i in range(1, len(tr)):
    for w in range(1, max_w + 1):
        if tr[i]['w'] > w:
            m[(i, w)] = m[(i - 1, w)]
        else:
            m[(i, w)] = max(
                m[(i - 1, w)],
                m[(i - 1, w - tr[i]['w'])] + tr[i]['v']
            )

print(m[(len(tr) - 1, max_w)])

转载：https://blog.csdn.net/weixin_43651049/article/details/104750057