平成17年度秋期 基本情報技術者試験(FE)の午後問題4は、
- 中置表記法による正しい数式を、スタックを用いて後置表記法(逆ポーランド記法)に変換するプログラム
に関する問題でした。
プログラム例(h17a_fe_pm4.c)
実行結果
$ gcc h17a_fe_pm4.c && ./a.out (2+4)*3+5*6 24+3*56*+
平成18年度春季ソフトウェア開発午後問5
平成18年度春季 ソフトウェア開発技術者試験(SW)の午後問題6は、
に関する問題でした。ちなみに、平成29年度春季基本情報午後問8でも出題されています。
プログラム例(h18h_sw_pm5.c)
実行
図1 グラフGのデータで実行してみました。実行結果のそれぞれの行はA地点から各地点に行くための経路とその最短距離を示しています。例えば、E地点に行くためには、A→C→Eと辿れば、距離18で最短になります。
$ gcc h18h_sw_pm5.c && ./a.out A A (0) A C B (5) A C (3) A C B D (10) A C E (18)
関連
平成31年度春季基本情報午後問9
平成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年度春季基本情報午後問8
平成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年度春季基本情報午後問10
平成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)
一昨日取り組んだ「平成18年度秋季ソフトウェア開発午後問5(2分探索木)」の続きです。
実験(4)
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
実行結果
