平成31年度春季 基本情報技術者試験(FE)の午後問題11は、
- 迷路(Maze)
に関する問題でした。Javaでの出題ですが、面白そうな題材なのでRubyで取り組んでみました。
プログラム例(h31h_fe_pm11.rb
)
実行結果
$ ./h31h_fe_pm11.rb ↓ → → → → ↓ ↓ ← ← ← ←
平成31年度春季 基本情報技術者試験(FE)の午後問題9は、
に関する問題でした。
h31h_fe_pm9.c
)文字コードごとの出現回数を数えるプログラム(自分自身)で調べたところ、(空白文字)が393文字で最多、次に
i
で67文字でした。
$ gcc h31h_fe_pm9.c && ./a.out 1423 bytes processed 0 00 0 40 '@' 0 80 0 C0 0 01 0 41 'A' 1 81 0 C1 0 02 0 42 'B' 3 82 0 C2 0 03 2 43 'C' 4 83 0 C3 0 04 0 44 'D' 0 84 0 C4 0 05 4 45 'E' 1 85 0 C5 0 06 2 46 'F' 0 86 0 C6 0 07 0 47 'G' 2 87 0 C7 0 08 0 48 'H' 0 88 0 C8 (以下略)
平成31年度春季 基本情報技術者試験(FE)の午後問題8は、
に関する問題でした。
ハフマン符号は、出現頻度が高い文字については短いビット列を、出現頻度が低いものに対しては長いビット列を割り当てることで、文字列全体のビット長を短くできるというアルゴリズムです。学生時代に習ったときには、ちょっと感動したことを今でも覚えています。 文字列の圧縮を行う前に各文字の出現頻度を求める必要があるので、文字列に対して2回の走査が必要になります*1。この欠点を改善し、1回の走査で圧縮まで行う動的ハフマン符号がありますね。
h31h_fe_pm8.c
)グローバル変数、ローカル変数や引数の仕様など少し変更しています。
$ gcc h31h_fe_pm8.c && ./a.out A: 1 B: 010 C: 00 D: 011
*1:マルチパス
平成18年度春季 基本情報技術者試験(FE)の午後問題10は、
に関する問題でした。面白いデータ構造ですね。
h18h_fe_pm10.c
)ユーザインタフェースに関する関数(displayArea
, clearField
, appendField
,inputChar
)は、ncurses
を使って実装しました。また、関数registWord
は、英単語、訳語を登録する関数です。
macOS Mojaveでの実行です。
$ gcc -lncurses h18h_fe_pm10.c && ./a.out
一昨日取り組んだ「平成18年度秋季ソフトウェア開発午後問5(2分探索木)」の続きです。
main
関数を以下のように置き換えます。99未満の乱数(整数)を発生させ、2分探索木に挿入するという操作を100回繰り返してみました。
int main(void) { NODE *root = NULL; int i, val; srand((unsigned)time(NULL)); // #include <time.h> を追加 for (i = 0; i < 100; i++) { val = rand() % 100; if (!lookup(val, root)) { root = insert(val, root); } } dot_print(root, NULL); return 0; }
$ gcc h18a_sw_pm5.c && ./a.out > tree.dot && dot -Tjpeg tree.dot -o output.jpg && open output.jpg
平成18年度秋季 ソフトウェア開発技術者試験(SW)の午後問題5は、
に関する問題でした。2分探索木については、平成27年度秋季応用情報午後問3でも出題されており、その際はRubyで実行していますので、今回はC言語で作成してみました。
h18a_sw_pm5.c
)問題文中の図1に対して、25, 40, 80, 45, 52 を追加して実行してみます。
$ gcc h18a_sw_pm5.c && ./a.out > tree.dot && dot -Tjpeg tree.dot -o output.jpg
main
関数のdot_print
関数呼び出しの前にノードの削除機能を持つdelete
関数を追加して実行してみます。
root = delete(64, root); /* 子を持たないケース */ root = delete(78, root); /* 右の子のみ持つケース */ root = delete(20, root); /* 左右の子を持つケース */
削除したいノードが
のときは、単純ですが、左右の子を持つケースの場合は少し複雑になりますね。20を削除しようとすると、20の左部分木の中での最大値15を20の位置に持ってくる事になります。
次にmain
関数内のdot_print
関数を
preorder_print_node(root);
と置き換えて実行してみます。preorder_print_node
関数は2分探索木を行きがけ順でなぞりながらノードの値を出力するものです。ノードの値が昇順に出力されていることが分かります。
$ gcc h18a_sw_pm5.c && ./a.out 2 8 15 25 36 40 44 45 50 52 53 80
平成18年度秋季 基本情報技術者試験(FE)の午後問題10は、
に関する問題でした。
本問のパターン文字列のルールだと、平成31年4月9日を表現する"H310409"と令和01年4月9日を表現する"R010409"にマッチさせようと思えば、"[HR][03]10409"と書けば良さそうですね*1。
$ gcc h18a_fe_pm10.c && ./a.out 0 0 0 5 0 5 0 5 5 0 -1 -1 -1 0 0
*1:厳密に言えば、"R310409"にマッチするのでまずいですが…。