t = [100, 50, 20, 5]  # 面值，需要进行排序sort/sorted

def change(t, n):
    """
    找零问题
    :param t: 面值列表 
    :param n: 需要零钱
    :return: 
    """
    m = [0 for _ in range(len(t))]  # 生成[0,0,0,0]对应每一个面值的个数
    for i, money in enumerate(t):  # 循环面值
        m[i] = n // money  # 面值对应区域 = 从最大面值开始，需要对面值列表进行排序
        n = n % money  # 剩余零钱
    return m, n

print(change(t, 376))

goods = [(60, 10),(100, 20),(120, 30)]  # 每个商品元组表示(价格, 重量)
goods.sort(key=lambda x: x[0]/x[1], reverse=True)  # 每克商品的价格进行排序


def fractional_backpack(goods, w):
    """
    分数背包
    :param goods: 商品列表
    :param w: 背包容量
    :return:
    """
    m = [0 for _ in range(len(goods))]  # [0,0,0] 对应商品个数
    total_v = 0  # 价值总数
    for i, (prize, weight) in enumerate(goods):
        print(m)
        if w >= weight:  # 当背包容量大于商品，继续拿
            m[i] += 1  # 拿到对应商品的个数，如果拿完了
            total_v += prize  # 增加价值
            w -= weight  # 减少容量
        else:  # 容量不够
            m[i] = w / weight  # 取商品的几分之几，实现尽量多拿贪心算法
            total_v += m[i] * prize  # 价值
            w = 0  # 拿完了，容量=0
            break
    return total_v, m

print(fractional_backpack(goods, 500))

from functools import cmp_to_key

li = [32, 94, 128, 1286, 6, 71]


def xy_cmp(x, y):
    """
    函数必须有两个参数用来进行比较
    :param x:
    :param y:
    :return:
    """
    if x + y < y + x:  # x放前面
        print('<', x, y)
        return 1
    elif x + y > y + x:  # y放前面
        print('>',x,y)
        return -1
    else:  # 相同位置排序无所谓
        return 0


def number_join(li):
    li = list(map(str, li))  # 全部转换为str
    li.sort(key=cmp_to_key(xy_cmp))  # cmp_to_key(比较函数)
    return "".join(li)


print(number_join(li))

# 元组[0]=开始时间，元组[1]=结束时间
activities = [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)]

activities.sort(key=lambda x:x[1])  # 保证活动是按照结束时间排好序的

def activity_selection(a):
    res = [a[0]]  # 最早的活动
    for i in range(1, len(a)):
        if a[i][0] >= res[-1][1]:   # 当前活动的开始时间大于等于最后一个入选活动的结束时间
            # 不冲突
            res.append(a[i])
    return res

print(activity_selection(activities))

# 子问题的重复计算
def fibnacci(n):
    """
    递归法
    :param n:
    :return:
    """
    if n == 1 or n == 2:
        return 1
    else:
        return fibnacci(n-1) + fibnacci(n-2)




# 动态规划（DP）的思想 = 递推式 + 重复子问题
def fibnacci_no_recurision(n):
    """
    非递归
    :param n:
    :return:
    """
    f = [0,1,1]  # 先确定前2个数为1,1 0的作用是让f[2]=f[0]+f[1]
    if n > 2:
        for i in range(n-2):  # 去掉前两个
            num = f[-1] + f[-2]
            f.append(num)
    return f[n]

print(fibnacci_no_recurision(100))

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def gcd2(a, b):
    while b > 0:
        r = a % b
        a = b
        b = r
    return a


print(gcd2(12,16))