动态规划之最优二叉搜索树

# -*- coding: UTF-8 -*- #
'''
@filename: Dynamic_magic_compression.py
@author:JIN
@time:2022-10-31
'''
import math
def Compress(P,n):
    global Lmax,header
    Lmax=256
    header=11
    S = [0 for i in range(n+1)]
    b = [0 for i in range(n+1)]
    L = [0 for i in range(n+1)]
    for i in range(1,n+1):
        b[i]=math.ceil(math.log(P[i-1]+1,2))   #表示第i个像素灰度的二进制位数
        bmax=b[i]                                #每次将当前循环的那个像素设为位数最大值
        S[i]=S[i-1]+bmax                         #S[i] =min{S[i - j] + j * bmax}中第一种情况，
                                                # 前面的像素点为一段，刚刚循环添入耳像素点独自为一组
        L[i]=1                                   #表示当前第i个像素 所在的段  中有只有一个数字 就是他自己

        for j in range(2,min(range(i,256))+1):    #循环其他S[i] =min{S[i - j] + j * bmax}情况
           # print("第",i,"下",i-j,"P[i-j]为",P[i-j])
            if bmax <=math.ceil(math.log(P[i-j]+1,2)):
                #print("bmax", i, "下", i - j, "P[i-j]为", P[i - j])
                bmax=math.ceil(math.log(P[i-j]+1,2))
            #print(bmax,"%%%%", i, "下", i - j)
           # print(S[i])
          #  temp=S[i-j]+j*bmax
            #print(temp)
            if S[i] >= S[i-j]+j*bmax:
                S[i] =S[i - j] + j * bmax     #如果循环下其他情况的S[i]更小那么取那个最小的
                L[i]= j                    #当前第i个数所在段 有几个数字
                b[i]= bmax           #我加，跟新当前组，所需的存储位数
        S[i]=S[i]+header    #每次循环结束 更新S[i]存放前i个数字的最优处理方式
    return L,S
def Traceback(n,L):
    j=1      #j用来追踪段数
    C=[0 for i in range(n)]
    while n!=0:
        C[j]=L[n]   #
        n=n-L[n]
        j=j+1
    return C,j

if __name__ == '__main__':
    numb1 = input('请输入图像灰度序列').split()
    P = list(map(int, numb1))
    n=len(P)#图像灰度序列个数
    #print(P)
    L,S=Compress(P,n)
    #print(L)
    C,j=Traceback(n, L)
    print("图像压缩后最小的空间为",S[-1])
    print("将原灰度分为了",j-1,"段序列")
    for i in range(j-1):
        num=C[j-1-i]
        print("段长为",num)

最后

以上就是坚强钥匙为你收集整理的动态规划之最优二叉搜索树的全部内容，希望文章能够帮你解决动态规划之最优二叉搜索树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。