数据结构学习-python实现04--0410

# 谢尔宾斯基三角
import turtle

t = turtle.Turtle()
points = {'left': (-200, -100), 'top': (0, 200), 'right': (200, -100)} 

def sierpinski(degree, points):
    colormap = ['blue', 'red', 'green', 'white', 'yellow', 'orange']
    drawtriangle(points, colormap[degree])
    if degree > 0:
        sierpinski(degree - 1,
                   {'left': points['left'],
                    'top': getmid(points['left'], points['top']),
                    'right': getmid(points['left'], points['right'])})
        sierpinski(degree - 1,
                   {'left': getmid(points['left'], points['top']),
                    'top': points['top'],
                    'right': getmid(points['top'], points['right'])})
        sierpinski(degree - 1,
                   {'left': getmid(points['left'], points['right']),
                    'top': getmid(points['top'], points['right']),
                    'right': points['right']})


def drawtriangle(points, color):
    t.fillcolor(color)
    t.penup()
    t.goto(points['top'])
    t.pendown()
    t.begin_fill()
    t.goto(points['left'])
    t.goto(points['right'])
    t.goto(points['top'])
    t.end_fill()


def getmid(p1, p2):
    return ( (p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)


sierpinski(5, points)
turtle.done()

# 汉诺塔移动，思想：若最大盘片不移动，相当于不存在，所以只需移动较小一层级，最终对应于只移动一只。
def move_tower(height, frompole, withpole, topole):
    if height >= 1:
        move_tower(height-1, frompole, topole, withpole)
        move_disk(height, frompole, topole)
        move_tower(height-1, withpole, frompole, topole)


def move_disk(disk, frompole, topole):
    print(f"Moving disk[{disk}] from {frompole} to {topole}")  # 学习这种用法


move_tower(4, '#1', '#2', '#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


print(recmc([1, 5, 10, 25], 63))

# 自动售货机找零问题的升级算法，记录其他情况下的最优算法，进行一次查表操作。
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


print(recdc([1, 5, 10, 25], 63, [0]*64))