Problem 219
の編集
http://odz.sakura.ne.jp/projecteuler/index.php?Problem+219
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
(no template pages)
*[[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ペンスとなる. この例は非対称なコスト分布となるが, なんと(同じサイズの中で)もっとも安い符号の１つである. 短く書くと, Cost(6)=35 となる. Cost(&tex{10^{9}};)を求めよ. [訳注 ペンス: ペニーの複数形]
タイムスタンプを変更しない
*[[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ペンスとなる. この例は非対称なコスト分布となるが, なんと(同じサイズの中で)もっとも安い符号の１つである. 短く書くと, Cost(6)=35 となる. Cost(&tex{10^{9}};)を求めよ. [訳注 ペンス: ペニーの複数形]
テキスト整形のルールを表示する
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
