82
правки
Изменения
Нет описания правки
# Рассмотрим первый список (с монетами самого низкого номинала). Разобьем в нем все монеты на пары (1 и 2, 3 и 4 и т. д.) Заменим каждую пару монет одной новой монетой, номинал и вес которой равен сумме номиналов и весов старых. Если число монет было нечетно, то последнюю монету, которая не имеет пары, исключим из рассмотрения.
# Объединим первый список со вторым так, чтобы монеты в получившемся списке остались упорядочены по весу.
# Будем повторять шаги 2-3 до тех пор, пока у нас не останется один список. В нем будут содержаться , в котором содержатся монеты номиналом номинала 1 (<tex>2^0</tex>), упорядоченные по весу. Возьмем первые <tex>S</tex> монет из списка. Это и будет ответ к задаче.
== Сведение к генерации кода Хоффмана с длиной кодового слова не более L бит. ==
{| class="wikitable"
| Номинал = <tex> 2^{-2} </tex> || <tex>(2^{-2}; 1)</tex> || <tex>(2^{-2}; 2)</tex> || <tex>(2^{-2}; 3)</tex>
|-
| Номинал = <tex> 2^{-1} </tex> || <tex>(2^{-1}; 1)</tex> || <tex>(2^{-1}; 2)</tex> || <tex>(2^{-2}; 3)</tex>
|}
Выполним объединение первого списка по парам и исключим последний элемент, т.к. для него нет пары:
| Номинал = <tex> 2^{-2} </tex> || <tex>(2^{-1}; 3)</tex> || ||
|-
| Номинал = <tex> 2^{-1} </tex> || <tex>(2^{-1}; 1)</tex> || <tex>(2^{-1}; 2)</tex> || <tex>(2^{-2}; 3)</tex>
|}
