#author("2022-11-03T03:14:37+00:00","","")
*[[Problem 219:http://projecteuler.net/problem=219]] 「非対称コスト符号化」 [#b71c90cd]

AとBをビット列(0と1の連続列)とする. ~
Bの''左''端から"Aの長さ"ビットがAと一致する時, AをBの"接頭部"(prefix)と呼ぶ. ~
例えば 00110 は ''00110''1001 の接頭部だが, 00111 や 100110 の接頭部ではない.

サイズnの"接頭符号"(prefix-free code)とは, 次の条件を満たす n 個の異なるビット列の集合である: どのビット列も他のビット列の接頭部ではない. 下の例はサイズ6の接頭符号である.

CENTER:0000, 0001, 001, 01, 10, 11

ここでビット0を送るのに1ペニー, ビット1を送るのに4ペンスかかると仮定する. ~
上で挙げた接頭符号にかかる総計は35ペンスとなる.
この例は非対称なコスト分布となるが, なんと(同じサイズの中で)もっとも安い符号の1つである. 短く書くと, Cost(6)=35 となる.

Cost(10&sup{9};)を求めよ.
Cost(&tex{10^{9}};)を求めよ.

[訳注  ペンス: ペニーの複数形]

IP:112.68.65.182 TIME:"2022-11-03 (木) 12:14:37" REFERER:"http://odz.sakura.ne.jp/projecteuler/?cmd=edit&page=Problem+219" USER_AGENT:"Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/107.0.0.0 Safari/537.36"

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS