課題は前回のアルゴリズムをプログラム化。

レポート提出。 出席課題はHuffman符号化の木を葉から生成するアルゴリズム。記号数をN, 2分木のノードになる構造体をData[0..N−1]とする。この構造体には、"0"と"1"に対応する子へのリンクポインタと出現頻度を保持している。木を作るためのポインタ配列をp…

ファノ符号化は、常に最適な符号化、ではない。たとえば、出現頻度が 20, 19, 17 16, 14, 13 の6文字を符号化すると、 20 00 19 010 17 011 16 10 14 110 13 111 と符号化され、「出現頻度が大きいほど短い符号」にはならない。 また、分割の際、2通りの分割…

ランダムに生成した10個の整数を降順にソートして分割を1回行って表示するプログラムを作る課題。1時間半で終了。いぇい

前に書いたアルゴリズムがちょっとわかりづらいので、考え直してみた。分割位置が上に移動する時、上下の和の差の"絶対値"が単調減少する境界を見つければいいんだから、負かどうかの判定は必ずしも必要ではないな。今の境界の値と次に移動した値の差が増加…

シャノン-ファノ符号化で、分割位置を求めるアルゴリズムを考える。関係ないが、この符号化の名前になってる2人は、ほぼ同時期に同じ符号化を思いついたらしい。エジソンとベルみたいなもんだな。 以下、考えたアルゴリズム。 すでに出現頻度順にソートされ…