dynamic_prog.py - master - erddrsf/Pyhse

dynamic_prog.py
104 строки3 KB
erddrsf
Примеры моего кода
01 май 2026, 23:35
01 май 2026, 23:35b05b859
def if_number_in_fibseq(N):
    """Есть  ли число в последовательности фибоначи"""
    g = [0]*100
    g[1] =1;g[2]=1
    for i in range(2,100):
        g[i] = g[i-1]+g[i-2]
        if g[i] == N:
            return i
        elif g[i] > N:
            return -1

def packege_disk(*args,s):
    dp =[]
def last_numb_of_fibseq(N):
    """последняя цифра в числе № N  фибоначи"""
    g = [0]*(N+2)
    g[1] =1;g[2]=1
    for i in range(2,N+2):
        g[i] = g[i-1]+g[i-2]
    return int(str(g[N+1])[-1])

def largest_comon_seq(a,b):
    y = len(b)
    x=len(a)
    A = [[0]*y]+[[0]+[None for _ in range(y-1)] for _ in range(x-1)]
    for i in range(x):
        # for j in range(y):
        print([A[i][j] for j in range(y)])
    for i in range(1,x):
        for j in range(1,y):
            # print(A[i][j],A[i-1][j],A[i][j-1])
            if a[i] == b[j]:
                A[i][j]=1+A[i-1][j-1]
            else:
                A[i][j] = max(A[i-1][j],A[i][j-1])
    for i in range(x):
        print([A[i][j] for j in range(y)])
    return A[-1][-1]

def test_lcs():
    print(largest_comon_seq('adfsdfdsdsddssd','leellldfdfdssd'))


def chess_combinations(x,y):
    A = [[0]*y]+[[0]+[None for _ in range(y-1)] for _ in range(x-1)]
    A[1][1]=1

    for i in range(1,x):
        for j in range(1,y):
            if i==1 and j==1:
                continue
            A[i][j] = A[i-1][j] + A[i][j-1]
    # return A[x,y]

    for i in range(y):
        # for j in range(y):
        print([A[i][j] for j in range(x)])

def test_chess():
    chess_combinations(10,10)

def livinshtein(A,B):
    L = [[i+j if i*j == 0 else 0 for j in range (len(B)+1)] for i in range(len(A)+1)]

    for i in range (1,len(A)+1):
        for j in range(1,len(B)+1):
            if A[i-1] == B[j-1]:
                L[i][j]= L[i-1][j-1]
            else:
                L[i][j] = 1+ min(L[i-1][j-1],L[i-1][j],L[i][j-1])
    return L[-1][-1]
    # print(L)
def test_livinstein():
    print(livinshtein("молоток","молоко"))


def cusnechik(N,ban_cells):
    """Сколькими комбинациями кузнечик может допрыгать до клетки N с запретом некоторых клеток"""
    M=[0,1,2] + [0]*(N-3)
    for i in ban_cells:
        M[i] = False
    for i in range(3,N+1):
        if not M[i]:
            continue
        M[i] = M[i-1] + M[i-2] +M[i-3]
    return M[N]


def test(func,N,TrueN):
    """тестирование поиска числа в фибоначи"""
    print(func.__doc__)
    ans= func(N)
    if ans == TrueN:
        print("Работате")
    else:
        print("Не работате",ans)

if __name__ == "__main__":
    test_livinstein()
    # test_lcs()
    # test_chess()
    # test(cusnechik, 21, 8)
    # test(if_number_in_fibseq,21,8)
    # test(last_numb_of_fibseq,700,1)