慶應SFC　環境情報学部　情報入試　2019年　大問Ⅲ　過去問解説

(ア)
A,B,C,D,Eの出現確率が同じであれば、1文字当たりの平均ビット長は
2ビット× + 2ビット×  + 2ビット×  + 3ビット×  + 3ビット×
で計算できる。平均ビット長は2.40ビットになる。
出現比率がA:B:C:D:E=1:2:2:2:3だった場合は
2ビット×  + 2ビット×  + 2ビット×  + 3ビット×  + 3ビット×
で計算できる。平均ビット長は2.50ビットになる。

A,B,C,D,E,Fの文字列に割り当てる最適な符号化を考えるには、ハフマン符号化を使う。
ハフマン符号化とは、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てる方法である。
ハフマン符号化にはハフマン木を使う。次のように考える。
まず、すべての文字を集め、出現回数を値とする。
その中から、値が最小のものと2番目のものを取り出す。
それらを子供に持つ新しい親を作る。このとき、親の値は、両方の子供の文字の和とする。
そして今度はその親と、残った文字を比べる。
まずAとBを比べる。

次にCとDを比べる。

次にAとBの親とEを比べる。

次にCとDの親とFを比べる。

そして最後の二つを結ぶ。

そして、一番上から順に左右に0と1を割り振る。

これを上から上位ビットとして、符号を決定する。この場合
A 000
B 001
C 100
D 101
E 01
F 11
となる。

よって平均ビット長は
3ビット×  + 3ビット×  + 3ビット×  + 3ビット×  + 2ビット×  + 2ビット×  = 2.466…
となり、答えは2.47である。

(イ)
トリッキーな問題である。次のように考える。

2進法で表された数xを10進法に変換した数をXで表すと、xの下位の桁に0をつけると10進法では2Xに変わる。
（例えば、x=100、X=8のとき、xの下位の桁に0をつけると1000であり、10進法では16=2Xである）
xの下位の桁に1をつけると10進法では2X+1に変わる。
（例えば、x=100、X=8のとき、xの下位の桁に1をつけると1001であり、10進法では17=2X+1である）

2Xのときは0を入力するということ、2X+1のときは1を入力するということ。

XがR0、つまり3で割った余りが0のときは、2Xも3で割れる。2X+1は3で割った余りが1。
だから、2XはR0、2X+1はR1。

XがR1、つまり3で割った余りが1のときは、2Xは3で割った余りが2、2X+1は3で割れる。
だから、2XはR2、2X+1はR0。

XがR2、つまり3で割った余りが2のときは、2Xは3で割った余りが1、2X+1は3で割った余りが2。
だから、2XはR1、2X+1はR2。

Sに関しては、0か1だから、容易に分かる。

したがって
T1 0
T2 1
T3 9
T4 0
T5 1
T6 1
T7 0
T8 0
T9 1
T10 9
T11 9
T12 9
である。

数の計算は遷移状態図を描き遷移させてみればよい。答えは0。