算法进阶

贪心算法

对问题求解时,总是做出在当前看来是最好的选择.不从整体最优上加以考虑,所做出的是在某种意义上的局部最优解. 不保证会得到最优解,但是在某些问题上贪心算法的解就是最优解. 要会判定一个问题能否用贪心算法来计算.

特殊问题:

找零问题
背包问题(0-1背包/分数背包)
拼接最大数字问题
活动选择问题

数字拼接 有n个非负整数,将其按照字符串拼接的方式拼接为一个整数,如何拼接使其最大

from functools import cmp_to_key
li = [32,94,128,1286,6,71]

def xy_cmp(x,y):
    if x+y < y+x:
        return 1
    elif x+y > y+x:
        return -1
    else:
        return 0


def number_join(li):
    li = list(map(str,li))
    li.sort(key=cmp_to_key(xy_cmp))
    return "".join(li)

print(number_join(li))

活动选择问题 假设有n个活动,这些活动要占用用一片场地,而场地在某时刻只能提供一个活动使用. 安排哪些活动能够使该场地举办的活动个数最多?

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

动态规划

最优子结构

可以将求解规模为n的原问题,划分为规模更小的子问题组合两个子问题的最优解,并在所有肯恩的方案中选取组合收益最大的,构成原问题的最优解 最优子结构:问题的最优解由相关子问题的最优解组合而成,这些子问题可以独立求解

自顶向下复杂度爆炸

def cut_rod_recurision(p,n):
    if n==0:
        return 0
    else:
        res = p[n]
        for i in range(1,n):
            res = max(res,cut_rod_recurision(p,i) + cut_rod_recurision(p,n-i))
        return res

自下而上复杂度可控

def cut_rod_extend(p,n):
    r = [0]
    s = [0]
    for i in range(1,n+1):
        res_r = 0 #价格的最大值
        res_s = 0 #价格最大值对应方案的左边不切割部分的长度
        for j in range(1,i+1):
            if p[j] + r[i - j] > res_r:
                res_r = p[j] + r[i-j]
                res_s = j
        r.append(res_r)
        s.append(res_s)
    return r[n],s

重构解(输出最优方案)

def cut_rod_solution(p,n):
    r,s = cut_rod_extend(p,n)
    ans = []
    while n > 0:
        ans.append(s[n])
        n -= s[n]
    return ans

动态规划问题关键特征

最优子结构

原问题的最优解中涉及多少个子问题
在确定最优解使用哪些子问题时,需要考虑多少种选择 重叠子问题

最长公共子序列问题

欧几里得算法问题

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(gcd(12,16))

RSA加密算法

传统密码:加密算法是秘密的

现代密码系统:加密算法是公开的,秘钥是秘密的

对称加密
非对称加密

RSA非对称加密系统: 公钥:用来加密,是公开的私钥:用来解密,是私有的

RSA加密算法过程

随机选取两个质数p和q 计算n=pq 选取一个与φ(n)互质的小奇数e,φ(n)=(p-1)(q-1) 对模φ(n),计算e的乘法逆元d,即满足(ed) mod φ(n) = 1 公钥(e,n) 私钥(d,n)

加密过程:c = (m^e) mod n 解密过程:m = (c^d) mod n

github address:

https://github.com/chenbokaix250/ForSomeForMySelf

算法3——算法进阶

相关文章：