Question

Постройте код для следующего алфавита: a(0.45), b(0.15), c(0.3), d(0.1). В скобках указаны вероятности, с которыми встречаются символы данного алфавита.

Answer 1

Var n: integer; begin    randomize;    n := random (99)+1;    if (n>0)and(n<46)    then writeln('a');    if (n>60)and(n<91)    then writeln('c');    if (n>45)and(n<61)    then writeln('b');    if (n>90)    then writeln('d');readlnend.

Answer 2

Вы хотите построить код Хаффмана для данного алфавита. Код Хаффмана - это оптимальный префиксный код, который минимизирует среднюю длину кодового слова для заданного распределения вероятностей.

Вот Python код для построения кода Хаффмана для данного алфавита:

pythonCopy code
import heapq
from collections import defaultdict

def build_huffman_tree(probabilities):
    heap = [[weight, [symbol, ""]] for symbol, weight in probabilities.items()]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    
    return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

def main():
    probabilities = {'a': 0.45, 'b': 0.15, 'c': 0.3, 'd': 0.1}
    huffman_tree = build_huffman_tree(probabilities)
    
    print("Symbol\tProbability\tHuffman Code")
    for symbol, probability, code in huffman_tree:
        print(f"{symbol}\t{probability}\t\t{code}")

if __name__ == "__main__":
    main()

Скопируйте этот код и запустите его в вашей среде разработки или интерпретаторе Python. Результатом будет таблица с символами, их вероятностями и соответствующими кодами Хаффмана.