EXCEL
对于T(N)，如果存在~T(N)，使得当N→∞时有(T(N)-~T(N))/T(N)→0，那么就说~T(N)是T(N)当N→∞时的渐进性态。

C++
#include<iostream>
using namespace std;

int factorial(int n){
    if(n==0) return 1;
    else{
        return n*factorial(n-1);
    }
}

C++
#include<iostream>
using namespace std;

int fibonacci(int n){
    if(n<=1) return 1;
    else return fibonacci(n-1)+fibonacci(n-2);
} 

PYTHON
def hanoi(n,a,b,c):
    #将a上的n个圆盘经过c移动到b
    if(n>0):
        hanoi(n-1,a,c,b)
        move(a,b)
        hanoi(n-1,c,b,a)

PYTHON
def binarySearch(a,x):
    #a是数组,x是要搜索的数
    a=sorted(a)
    #a要求有序（从小到大）
    n=len(a)
    left,right=0,n-1
    while(left<=right):
        middle=(left+right)//2
        if(x==a[middle]):
            return middle
        elif(x>a[middle]):
            left=middle+1
        else:
            right=middle-1
    #未找到
    return -1

MATHEMATICA
X=[A][B],Y=[C][D],其中X，Y有n位；A，B，C，D均有n/2位
由此可以得到：
X=A*2^(n/2)+B , Y=C*2^(n/2)+D

XY=(A*2^(n/2)+B)(C*2^(n/2)+D)
  =A*C*2^n+(A*D+C*B)*2^(n/2)+B*D
  =A*C*2^n+((A-B)(D-C)+A*C+B*D)*2^(n/2)+B*D

PYTHON
def merge(arr,left,mid,right):
    #left，right为需要合并的数组范围
    #mid为中间下标，左边比中值小，右边比中值大
    i=left
    j=mid+1
    #复制一个临时数组
    aux=arr[:]
    for k in range(left,right+1):
        #如果左指针超过mid，即右边还有剩余
        if(i>mid):
            arr[k]=aux[j]
            j=j+1
        #如果右指针超过right，即左边还有剩余
        elif(j>right):
            arr[k]=aux[i]
            i=i+1
        #如果左边小，则左边合并
        elif(aux[i]<aux[j]):
            arr[k]=aux[i]
            i=i+1
        #如果右边小
        else:
            arr[k]=aux[j]
            j=j+1


def mergeSort(arr,left,right):
    #如果已经遍历完
    if(left>=right):
        return ;
    #取中值，拆成左右两边
    mid=(left+right)//2
    #对左半边进行归并排序
    mergeSort(arr,left,mid)
    #对右半边进行归并排序
    mergeSort(arr,mid+1,right)
    #合并算法
    merge(arr,left,mid,right)

PYTHON
def quicksort(arr,low,high):
    if low<high :
        index=getindex(arr,low,high)
        quicksort(arr,low,index-1)
        quicksort(arr,index+1,high)

#快速排序算法核心
#作用：将小于基准值的数放在其左边，大于在右边
def getindex(arr,low,high):
    #默认第一个数字为标准值
    temp=arr[low]
    #当未遍历完，即左右指针未相遇
    while(low<high):
        #如果右边大于标准值，右指针左移
        while((low<high)and(arr[high]>=temp)):
            high=high-1
        #此时右指针对应值小于标准值，将其复制给左指针位置
        arr[low]=arr[high]
        #当左边小于标准值，左指针右移
        while((low<high)and(arr[low]<=temp)):
            low=low+1
        #此时左指针对应值大于标准值，将其复制给右指针位置
        arr[high]=arr[low]
    #将标准值赋值给左右指针相遇的位置
    arr[low]=temp
    #此时low左边全部小于等于arr[low],low右边全部大于等于arr[low]
    return low

PYTHON
"""
Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 最近点对问题
"""

#按x坐标排序的点
class Point1:
    #x,y为坐标，id为序号
    def __init__(self,xx,yy,index):
        self.x=xx
        self.y=yy
        self.id=index


#按y坐标排序的点
class Point2(Point1):
    #x，y为坐标，id为该点按x排序时的序号
    def __init__(self,xx,yy,index):
        self.x=xx
        self.y=yy
        self.id=index
        
#表示输出的平面点对
class Pair:
    #a，b为点，dist为距离
    def __init__(self, aa, bb,dd):
        self.a=aa
        self.b=bb
        self.dist=dd
    
#求平面上任意两点u,v的距离
def dist(u,v):
    dx=u.x-v.x
    dy=u.y-v.y
    return dx*dx+dy*dy

#归并排序
def merge(S,order,left,mid,right):
    i=left
    j=mid+1
    aux=S[:]
    #按x排序
    if(order=='x'):
        for k in range(left,right+1):
            if(i>mid):
                S[k]=aux[j]
                j=j+1
            elif(j>right):
                S[k]=aux[i]
                i=i+1
            elif(S[i].x<aux[j].x):
                S[k]=aux[i]
                i=i+1
            else:
                S[k]=aux[j]
                j=j+1
    #按y排序
    elif(order=='y'):
        for k in range(left,right+1):
            if(i>mid):
                S[k]=aux[j]
                j=j+1
            elif(j>right):
                S[k]=aux[i]
                i=i+1
            elif(S[i].y<aux[j].y):
                S[k]=aux[i]
                i=i+1
            else:
                S[k]=aux[j]
                j=j+1

#归并排序
def mergeSort(S,x,left,right):
    if(left>=right):
        return ;
    mid=(left+right)//2
    mergeSort(S,x,left,mid)
    mergeSort(S,x,mid+1,right)
    merge(S,x,left,mid,right)

#计算最接近点对
def closePair(S,Y,Z,l,r):
    #两个点
    if(r-l==1):
        return Pair(S[l],S[r],dist(S[l],S[r]))
    #三个点
    if(r-l==2):
        d1=dist(S[l],S[l+1])
        d2=dist(S[l+1],S[r])
        d3=dist(S[l],S[r])
        if((d1<=d2)and(d1<=d3)):
            return Pair(S[l],S[l+1],d1)
        if(d2<=d3):
            return Pair(S[l+1],S[r],d2)
        else:
            return Pair(S[l],S[r],d3)
    #多于三个点
    m=(l+r)//2
    f=l
    g=m+1
    for i in range(l,r+1):
        if(Y[i].id>m):
            Z[g]=Y[i] 
            g=g+1
        else:
            Z[f]=Y[i]
            f=f+1
    #递归求解
    best = closePair(S,Z,Y,l,m)
    right = closePair(S,Z,Y,m+1,r)
    #选最近的点对
    if(right.dist<best.dist):
        best=right
    merge(Y,"y",l,m,r)

    k=l
    #距离中线最近的
    for i in range(l,r+1):
        if(abs(S[m].x-Y[i].x)<best.dist):
            Z[k]=Y[i]
            k=k+1
    for i in range(l,k):
        for j in range(i+1,k):
            if(Z[j].y-Z[i].y<best.dist):
                dp=dist(Z[i],Z[j])
                if(dp<best.dist):
                    best=Pair(S[Z[i].id],S[Z[j].id],dp)
    #返回最近点对
    return best


#一维点集
def cpair1(S):
    #先设为正无穷
    min_d=float("inf")
    S=sorted(S)
    for i in range(1,len(S)):
        dist=abs(S[i]-S[i-1])
        if(dist<min_d):
            pair=[]
            min_d=dist
            pair.append([S[i-1],S[i]])
        elif(dist==min_d):
            pair.append([S[i-1],S[i]])
    print("Closest point:")
    for i in pair:
        print(i,end=" ")
    print("
Min_dist:",min_d)

#二维点集
def cpair2(S):
    Y=[]
    n=len(S)
    if(n<2):
        return ;
    #按X坐标排序
    mergeSort(S,"x",0,n-1)
    #以Point2类型赋值
    for i in range(n):
        p=Point2(S[i].x,S[i].y,i)
        Y.append(p)
    #按y坐标排序
    mergeSort(Y,"y",0,n-1)
    Z=Y[:]
    return closePair(S,Y,Z,0,n-1)
    
    
def main():
    #输入一维还是二维点平面
    model=input("Please choose model of '1' or '2':").split()[0]
    S=[]
    #一维点对
    if(model == '1'):
        point=input("Please input a group of number in order:
").split()
        #如果输入空点对
        if(len(point)==0):
            raise ValueError("您输入了空点对！")
        #转换类型
        for i in range(len(point)):
            S.append(int(point[i]))
        #输出最近点对
        cpair1(S)
    #二维点对
    elif(model == '2'):
        #输入点数
        n=int(input("Please input how many points:
"))
        if(n==0):
            raise ValueError("您输入了0个点！")
        for i in range(n):
            words=f"please input the No.{i+1} point (like: x y) in x order:"
            point=input(words).split()
            p=Point1(int(point[0]),int(point[1]),i)
            S.append(p)
        #找到最近的一对点对
        best=cpair2(S)
        print(f"The closest points are ({best.a.x},{best.a.y}) and ({best.b.x},{best.b.y}).")
        print(f"And the distance is {best.dist**0.5}.")
    else:
        raise ValueError("没有这个选项！")

if __name__ == "__main__":
    #异常处理
    try:
        main()
    except Exception as e:
        print("您的输入不合法！出错信息如下：")
        print(e)

PYTHON
"""
Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 矩阵连乘问题
"""

#计算最优值
def matrixChain(p,m,s):
    #m[i][j]表示A[i]到A[j]所需的最少数乘次数
    #s[i][j]表示A[i]到A[j]所需的最少数乘法对应的分隔位置
    n=len(p)-1
    for r in range(2,n+1):
        for i in range(1,n-r+2):
            #沿斜线方向递进
            j=r+i-1
            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]
            s[i][j]=i
            k=i+1
            #寻找i到j间最优分隔k
            while(k<j):
                t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]
                if(t<m[i][j]):
                    m[i][j]=t
                    s[i][j]=k
                k=k+1

#根据S递归输出
def traceback(s,i,j):
    if(i==j):
        print(f"A[{i}]",end="")
        return ;
    print("(",end="")
    traceback(s,i,s[i][j])
    traceback(s,s[i][j]+1,j)
    print(")",end="")



def main():
    p=[]
    y=0
    #输入矩阵个数
    n=input("Please iuput the number of matrix:").split()
    #异常处理
    if(len(n)==0):
        raise ValueError("您输入了空矩阵！")
    n=int(n[0])
    #输入每个矩阵的信息
    for i in range(n):
        s=input(f"Input No.{i+1} Matrix size,eg:5 5
").split()
        #判断是否能与前一项相乘
        if(len(p)>=1):
            if(y!=int(s[0])):
                raise ValueError("您输入的矩阵不能相乘！")
        x,y=int(s[0]),int(s[1])
        p.append(x)
    p.append(y)
    m=[]
    s=[]
    for i in range(n+1):
        m.append([0]*(n+1))
        s.append([0]*(n+1))
    matrixChain(p,m,s)  
    traceback(s,1,n)
    print("
Count times:",m[1][n])
    

    

if __name__ =="__main__":
    #异常处理
    try:
        main()
    except Exception as e:
        print("您的输入不合法！出错信息如下：")
        print(e)

PYTHON
"""
Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 最长公共子序列问题
"""

def IcsLength(x,y,b):
    m=len(x)
    n=len(y)
    #初始化
    c=[]
    for j in range(m+1):
        c.append([0]*(n+1))
    #逐个比较
    for i in range(1,m+1):
        for j in range(1,n+1):
            #如果相等那么此时的最长公共长度为去除该位置的最长公共长度+1
            if(x[i-1]==y[j-1]):
                c[i][j]=c[i-1][j-1]+1
                #记录c[i][j]的值是第一类子问题的解得到的
                b[i][j]=1
            #如果对应位置不相等，则比较两个序列去掉这个不等值后哪边的最长子序列会更长
            elif(c[i-1][j]>=c[i][j-1]):
                c[i][j]=c[i-1][j]
                b[i][j]=2
            else:
                c[i][j]=c[i][j-1]
                b[i][j]=3
    return c[m][n]

#根据b[i][j]输出最长子序列
def Ics(i,j,x,b):
    if(i==0 or j==0):
        return ;
    #如果是第一类子问题的解，则说明该位置是公共部分
    if(b[i][j]==1):
        Ics(i-1,j-1,x,b)
        print(x[i-1],end="")
    #如果是第二类子问题的解，则说明此时Zk≠Xm
    elif(b[i][j]==2):
        Ics(i-1,j,x,b)
    #Zk≠Yn
    else:
        Ics(i,j-1,x,b)

def main():
    #输入字符串
    A=input("Please input No.1 Ics:").split()
    B=input("Please input No.2 Ics:").split()
    b=[]
    for i in range(len(A)+1):
        b.append([0]*(len(B)+1))
    print("The longest length:",IcsLength(A,B,b))
    Ics(len(A),len(B),A,b)

if __name__=="__main__":
    #异常处理
    try:
        main()
    except Exception as e:
        print("您的输入不会合法！出错信息如下：")
        print(e)

PYTHON
"""
Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 凸多边形最优三角剖分问题
"""
from isConvex import isConvex

#计算最优值
def minWeightTriangulation(n,t,s,v):
    #t[i][j]是凸子多边形vi-1,vi,...,vj的最优三角剖分对应的权函数值
    for r in range(2,n+1):
        for i in range(1,n-r+2):
            j=r+i-1
            t[i][j]=t[i+1][j]+weight(i-1,i,j,v)
            s[i][j]=i
            k=i+1
            #遍历i到j的所有边
            while(k<j):
                u=t[i][k]+t[k+1][j]+weight(i-1,k,j,v)
                if(u<t[i][j]):
                    t[i][j]=u
                    s[i][j]=k
                k=k+1

#根据s输出划分结果
def traceback(s,i,j):
    if(i==j):
        print(f"B[{i}]",end="")
        return ;
    print("(",end="")
    traceback(s,i,s[i][j])
    traceback(s,s[i][j]+1,j)
    print(")",end="")

#根据距离计算权重
def weight(i,j,k,v):
    return dist(i,j,v)+dist(i,k,v)+dist(k,j,v)

#计算距离
def dist(i,j,v):
    return (v[i][0]-v[j][0])**2+(v[i][1]-v[j][1])**2

def main():
    v=[]
    #可选择手动输入和使用默认值
    ans=input("Do you want to use default v[]:(y / n )")
    if(ans=="y" or ans=="Y"):
        v=[[6,1],[13,1],[16,4],[13,7],[6,7],[3,4]]
        graph="""-----@######@-------
----#--------#------
---#----------#-----
--@------------@----
---#----------#-----
----#--------#------
-----@######@-------
"""
        print(graph)
        for i in v:
            print(f"({i[0]},{i[1]})",end=" ")
    
    elif(ans=="n" or ans=="N"):
        n=int(input("Please input the number of points:
"))
        if(n==0):
            raise ValueError("您输入了0！")
        for i in range(n):
            a=input(f"Input X and Y of No.{i+1} point:(eg:X Y)
").split()
            v.append([int(a[0]),int(a[1])])
        
    else:
        raise ValueError("对不起没有这个选项！")
    #判断是不是图多边形
    if(not isConvex(v)):
        raise ValueError("您输入的不是凸多边形！请确认是否按顺序输入！")
    t=[]
    s=[]
    n=len(v)
    #初始化
    for i in range(n):
        t.append([0]*(n))
        s.append([0]*(n))
    minWeightTriangulation(n-1,t,s,v)
    traceback(s,0,n-1)

if __name__=="__main__":
    #异常处理
    try:
        main()
    except Exception as e:
        print("您的输入不合法！出错信息如下：")
        print(e)

PYTHON
#判断是否为凸多边形
'''
计算直线表达式
param vertex1: 前一个顶点
param vertex2: 后一个顶点
return (type, param): 返回直线的类别及其描述参数
'''
def kb(vertex1, vertex2):
    x1 = vertex1[0]
    y1 = vertex1[1]
    x2 = vertex2[0]
    y2 = vertex2[1]
    
    if x1==x2:
        return (0, x1)      # 0-垂直直线
    if y1==y2:              
        return (1, y1)      # 1-水平直线
    else:
        k = (y1-y2)/(x1-x2)
        b = y1 - k*x1
        return (2, k, b)    # 2-倾斜直线

'''
判断是否为凸多边形
param vertexes: 构成多边形的所有顶点坐标列表，如[[0，0], [50, 0], [0, 50]]
return convex: 布尔类型，为True说明该多边形为凸多边形，否则为凹多边形
'''
def isConvex(vertexes):
    # 默认为凸多边形
    convex = True   
    
    # 多边形至少包含三个顶点
    l = len(vertexes)
    if l<3:
        raise ValueError("多边形至少包含三个顶点！")
    
    # 对每两个点组成的直线做判断
    for i in range(l):
        pre = i
        nex = (i+1)%l
        
        # 得到直线
        line = kb(vertexes[pre], vertexes[nex])
        
        # 计算所有点和直线的距离（可能为正也可能为负）
        if line[0]==0:
            offset = [vertex[0]-vertexes[pre][0] for vertex in vertexes]
        elif line[0]==1:
            offset = [vertex[1]-vertexes[pre][1] for vertex in vertexes]
        else:
            k, b = line[1], line[2]
            offset = [k*vertex[0]+b-vertex[1] for vertex in vertexes]
        
        # 计算两两距离的乘积，如果出现负数则存在两个点位于直线两侧，因此为凹多边形
        for o in offset:
            for s in offset:
                if o*s<0:
                    convex = False
                    break
            if convex==False:
                break
                    
        if convex==False:
            break
            
    # 打印判断结果
    if convex==True:
        print("该多边形为凸多边形！")
    else:
        print("该多边形为凹多边形！")
    
    return convex

PYTHON
"""
Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 0-1背包问题--动态规划
"""

#跳跃点法
def knapsack_Pro(n,v,w,C,p,x):
    #head指向每一阶段跳跃点集合的开始
    head=[0 for i in range(n+1)]
    p[0][0],p[0][1]=0,0
    left,right,pnext,head[1]=0,0,1,1
    for i in range(n):
        k=left
        for j in range(left,right+1):
            if(p[j][0]+w[i]>C):
                break 
            y=p[j][0]+w[i]
            m=p[j][1]+v[i]
            #重量小于此数的跳跃点直接加进来，不会被支配
            while(k<=right and p[k][0]<y):
                p[pnext][0]=p[k][0]
                p[pnext][1]=p[k][1]
                pnext+=1
                k+=1
            #两个if判断新产生的点能否加入p
            if(k<=right and p[k][0]==y):
                if(m<p[k][1]):
                    m=p[k][1]
                k+=1
            if(m>p[pnext-1][1]):
                p[pnext][0]=y
                p[pnext][1]=m
                pnext+=1
            #取出可以支配的点
            while(k<=right and p[k][1]<=p[pnext-1][1]):
                k+=1

        #上面break后
        while(k<=right):
            p[pnext][0]=p[k][0]
            p[pnext][1]=p[k][1]
            pnext+=1
            k+=1
        
        left=right+1
        right=pnext-1
        head[i+1]=pnext
    traceback_Pro(n,w,v,p,head,x)

def traceback_Pro(n,w,v,p,head,x):
    j=p[head[n]-1][0]
    m=p[head[n]-1][1]
    print("max value:",m,"max weight:",j)
    for i in range(n)[::-1]:
        for k in range(head[i],head[i+1]-1):
            if(p[k][0]+w[i]==j and p[k][1]+v[i]==m):
                x[i]=1
                j=p[k][0]
                m=p[k][1]
                break


def knapsack(v,w,C,m):
    #m[i][j]指背包容量为j，可选择物品为i，i+1，...，n时的0-1背包问题的最优值
    n=len(v)-1
    #只剩一个物品的情况
    for j in range(C):
        m[n][j] = v[n] if j>=min(w[n]-1,C) else 0
    #普通情况
    for i in range(1,n)[::-1]:
        for j in range(C):
            m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]) if j>w[i]-1 else m[i+1][j]
    #第一件物品
    if(n>0):
        m[0][C-1]=m[1][C-1]
        if C-1>=w[0]:
            m[0][C-1]=max(m[0][C-1],m[1][C-1-w[0]]+v[0])

def traceback(m,w,C,x):
    c=C-1
    for i in range(len(w)-1):
        #没选物品i则x[i]=0
        if (m[i][c]==m[i+1][c]):
            x[i]=0
        else:
            x[i]=1
            c -= w[i]
    #对于最后一个物品
    x[len(w)-1]=1 if m[len(w)-1][c]>0 else 0

#输出格式
def cout(x,v,w):
    total_v=0
    total_w=0
    print("Choose:")
    for i in range(len(v)):
        if x[i]==1:
            print(f"No.{i+1} item: value is {v[i]} , weight is {w[i]}")
            total_v +=v[i]
            total_w +=w[i]
    print(f"total value: {total_v}")
    print(f"total weight: {total_w}")

def main():
    v=[]    #物品的价值列表
    w=[]    #物品的重量列表
    #输入物品数量
    n=input("Please input the number of items:
")
    if(n=="" or n=="0"):
        raise ValueError("您输入了空值或0！")
    else:
        n=int(n)
    x=[0 for i in range(n+1)]
    #选择两种算法（课本上的）
    ans=input("Choose Knapsack or Knapsack_Pro?(1 or 2)
").split()[0]
    if ans=='1':
        m=[]    #m(i,j)指背包容量为j，可选择物品为i，i+1，...，n时的0-1背包问题的最优值
        for i in range(n):
            item=input(f"please input No.{i+1} item's value(v) and weight(w):(eg:v w)
").split()
            v.append(int(item[0]))
            w.append(int(item[1]))
        C=int(input("Please input the max weight of bag:
"))
        if(C<=0):
            raise ValueError("背包容量不能≤0")
        for i in range(n):
            m.append([0]*C)
        knapsack(v,w,C,m)
        traceback(m,w,C,x)
        cout(x,v,w)
    elif ans=='2':
        for i in range(n):
            item=input(f"please input No.{i+1} item's value(v) and weight(w):(eg:v w)
").split()
            v.append(float(item[0]))
            w.append(float(item[1]))
        #初始化
        p=[[0 for i in range(2)]for j in range(n*n)]
        C=float(input("Please input the max weight of bag:
"))
        if(C<=0):
            raise ValueError("背包容量不能小于等于0")
        if(n==1):
            if(w[0]<=C):
                x[0]=1
            else:
                x[0]=0
        else:
            knapsack_Pro(n,v,w,C,p,x)
        for i in range(n):
            if(x[i]==1):
                print("choose: value:",v[i],"weight:",w[i])
    else:
        raise ValueError(f"您输入了{ans}没有该选项！")

if __name__=="__main__":
    #异常处理
    try:
        main()
    except Exception as e:
        print("您的输入不合法！出错信息如下：")
        print(e)

"""
Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 活动安排问题
"""

#活动类，每个活动包括开始时间和结束时间
class activity():
    def __init__(self,ss,ff):
        self.s=ss
        self.f=ff
    

def greedySelector(arr,a):
    n=len(arr)-1
    a[0]=True
    j=0
    count=1
    #满足开始时间大于上一个活动的结束时间的加入（设为True）
    #O(n)
    for i in range(1,n+1):
        if(arr[i].s>=arr[j].f):
            a[i]=True
            j=i
            count+=1
        else:
            a[i]=False
    return count

def main():
    activities=[]
    #输入数据
    n=int(input("please input the number of activities:
"))
    #异常处理
    if(n==0):
        raise ValueError("您输入了0！")
    print("Use greedy selector , activities should be ordered by the end_time.")
    for i in range(n):
        item=input("please input the begin-time and end-time:(eg: 3 6)
").split()
        if(len(item)!=2):
            raise ValueError("您输入的数据个数不合法！")
        s=activity(float(item[0]),float(item[1])) 
        activities.append(s)
    #以结束时间非减序排序
    activities=sorted(activities,key=lambda x:x.f)
    #初始化选择集合a
    a=[False for i in range(n)]
    count=greedySelector(activities,a)
    print("Maximum number of activities:",count)
    print("Choose:",a)

if __name__ == "__main__":
    try:
        main()
    except Exception as e:
        print("您的输入不合法！出错信息如下：")
        print(e)