算法设计课程期末考试笔记

逆序对计算的分治算法

# 逆序对计算的分治算法
def count_inversions_dc(A):
    lenA = len(A)
    if lenA <= 1:
        return 0, A
    middle = lenA // 2
    leftA = A[:middle]
    rightA = A[middle:]
    countLA, leftA = count_inversions_dc(leftA)
    countRA, rightA = count_inversions_dc(rightA)
    countLRA, mergedA = mac(leftA, rightA)

    return countLA + countRA + countLRA, mergedA

def mac(A, B):
    i, j, count = 0, 0, 0
    alist = []
    lenA = len(A)
    lenB = len(B)
    while i < lenA and j < lenB:
        if A[i] < B[j]:
            alist.append(A[i])
            i += 1
        else:
            count += lenA - i
            alist.append(B[j])
            j += 1
    while i < lenA:
        alist.append(A[i])
        i += 1
    while j < lenB:
        alist.append(B[j])
        j += 1
    return count, alist

if __name__ == '__main__':
    a = [2, 4, 1, 3, 5]
    c, b = count_inversions_dc(a)
    print(c, b)

硬币找零的贪心算法

def gmc(amt):
    coin = [1, 5, 10, 25, 100]
    cl = []
    sc = sorted(coin, reverse=True)
    for cv in sc:
        cc = int(amt / cv)
        cl += [cv, ] * cc
        amt -= cv * cc
        if amt <= 0.0:
            break
    return cl


if __name__ == '__main__':
    print(gmc(38))

连续子序列和最大值动态规划算法

def zxlmax(alist):
    table = [0] * (len(alist) + 1)
    for i in range(1, len(alist) + 1):
        table[i] = max(table[i - 1] + alist[i - 1], alist[i-1])
    return table

def tbs(alist, table):
    import numpy as np
    select = []
    max_sum = max(table)
    ind_max = np.argmax(table)
    while ind_max >= 1:
        if table[ind_max] == alist[ind_max - 1] + table[ind_max - 1]:
            select.append(alist[ind_max - 1])
            ind_max -= 1
        else:
            select.append(alist[ind_max - 1])
            break
    return select

if __name__ == '__main__':
    a = [2, 11, 4, 13, -5]
    table = zxlmax(a)
    s=tbs(a,table)
    print(s, table)

矩阵连乘最优结合问题

gk = lambda i,j :str(i)+','+str(j)
def mmc(p):
    n=len(p)-1
    m={}
    for i in range (1,n+1):
        for j in range (i,n+1):
            m[gk(i,j)]=float("inf")
    return lc(m,p,1,n)


def lc(m,p,i,j):
    if m[gk(i,j)]<float("inf"):
        return m[gk(i,j)]
    if i==j :
        return 0
    else:
        for k in range(i,j):
            q=lc(m,p,i,k)+lc(m,p,k+1,j)+p[i-1]*p[k]*p[j]
        if q< m[gk(i,j)]:
            m[gk(i,j)]=q
    return m[gk(i,j)]

if __name__ == '__main__':
    p=[30,35,15,5,10,20,25]
    print(gk(1,2))
    print(mmc(p))

二维0-1背包问题

def bb(W,wt,val,n):
    K=[[0 for x in range(W+1)] for x in range (n+1)]

    for i in range (n+1):
        for w in range(W+1):
            if i==0 or w==0:
                K[i][w]=0
            elif wt[i-1]<=w:
                K[i][w]=max(val[i-1]+K[i-1][w-wt[i-1],K[i-1][w]])
            else:
                K[i][w]=K[i-1][w]
    return K

def aa(w,wt,val,n):
    if n==0 or w==0:
        return 0
    if wt[n-1]>w:
        return aa(w,wt,val,n-1)
    else:
        return max(val[n-1]+aa(w-wt[n-1],wt,val,n-1),aa(w,wt,val,n-1))

间隔任务规划

def gmi(joblist):
    js=[]
    nj=len(joblist)
    joblist.sort(key=lambda x: x[2])
    for n in range(nj):
        if not js:
            js.append(joblist[n])
        else:
            if js[-1][2]<joblist[n][1]:
                js.append(joblist[n])
    return js

求最大岛屿问题

dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
vis = [[0 for col in range(7)] for row in range(7)]
res = 0
ans = 0
graph = [[0, 0, 0, 0, 1, 1, 0],
         [0, 1, 1, 0, 1, 1, 0],
         [0, 1, 1, 0, 0, 0, 0],
         [0, 0, 1, 0, 0, 1, 1],
         [0, 0, 0, 0, 0, 0, 0],
         [0, 0, 1, 1, 0, 0, 0],
         [0, 0, 0, 1, 0, 0, 1], ]


def dfs(x, y):
    flag = 0
    global res
    global ans
    global graph
    global dx
    global dy
    for i in range(0, 4):
        tox = x + dx[i]
        toy = y + dy[i]
        if tox < 0 or tox > 6 or toy < 0 or toy > 6:
            continue
        if vis[tox][toy] == 0 and graph[tox][toy]:
            vis[tox][toy] = 1
            ans = ans + 1
            dfs(tox, toy)
    return


if __name__ == '__main__':
    for i in range(0, 7):
        for j in range(0, 7):
            if graph[i][j] == 1:
                vis[i][j] = 1
                ans = 1
                dfs(i, j)
                res = max(res, ans)
    print(res)

八皇后问题

import pdb
import random


def Place(k):
    # 注意：k从索引0开始
    for j in range(k):
        if abs(k - j) == abs(rect[k] - rect[j]) or rect[k] == rect[j]:
            return False
    return True


def QueensLV(n):  # 返回一个bool值，得到解返回True，否则False
    k = 0  # 第一个索引为0
    rect[k] = random.randint(0, n)
    while (Place(k)):
        if k == n - 1:
            print('八皇后问题的一个解为：', rect)
            return True
        k += 1
        rect[k] = random.randint(0, n)
    return False


if __name__ == '__main__':
    n = input('请输入皇后数量：')
    n = int(n)
    rect = [0 for i in range(n)]
    print('输入的棋盘：', rect)
    errorcount = 0  # 失败次数
    while (not QueensLV(n)):
        errorcount += 1
    print('共尝试了{}次放置皇后的位置'.format(errorcount))