Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

平成31年度春季基本情報午後問8

情報処理技術者試験 C

平成31年度春季 基本情報技術者試験(FE)の午後問題8は、

  • ハフマン符号化を用いた文字列圧縮

に関する問題でした。

f:id:rahaema:20190422092926p:plain

ハフマン符号は、出現頻度が高い文字については短いビット列を、出現頻度が低いものに対しては長いビット列を割り当てることで、文字列全体のビット長を短くできるというアルゴリズムです。学生時代に習ったときには、ちょっと感動したことを今でも覚えています。 文字列の圧縮を行う前に各文字の出現頻度を求める必要があるので、文字列に対して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

情報処理技術者試験 C

平成18年度春季 基本情報技術者試験(FE)の午後問題10は、

  • 入力された英単語を検索し、訳語を表示するプログラム

に関する問題でした。面白いデータ構造ですね。

f:id:rahaema:20190420170815p:plain

プログラム例(h18h_fe_pm10.c)

ユーザインタフェースに関する関数(displayArea, clearField, appendField,inputChar)は、ncursesを使って実装しました。また、関数registWordは、英単語、訳語を登録する関数です。

実行結果

macOS Mojaveでの実行です。

$ gcc -lncurses h18h_fe_pm10.c  && ./a.out


平成18年度春季 基本情報技術者試験(FE)の午後問題10

関連

平成18年度秋季ソフトウェア開発午後問5(2)

情報処理技術者試験 C

一昨日取り組んだ「平成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

実行結果

f:id:rahaema:20190419184836j:plain

関連

平成18年度秋季ソフトウェア開発午後問5

情報処理技術者試験 C

平成18年度秋季 ソフトウェア開発技術者試験(SW)の午後問題5は、

  • 2分探索木

に関する問題でした。2分探索木については、平成27年度秋季応用情報午後問3でも出題されており、その際はRubyで実行していますので、今回はC言語で作成してみました。

プログラム例(h18a_sw_pm5.c)

実験(1)

問題文中の図1に対して、25, 40, 80, 45, 52 を追加して実行してみます。

$ gcc h18a_sw_pm5.c && ./a.out > tree.dot && dot -Tjpeg tree.dot -o output.jpg

f:id:rahaema:20190416211305p:plain

実験(2)

main関数のdot_print関数呼び出しの前にノードの削除機能を持つdelete関数を追加して実行してみます。

  root = delete(64, root);      /* 子を持たないケース */
  root = delete(78, root);      /* 右の子のみ持つケース */
  root = delete(20, root);      /* 左右の子を持つケース */

削除したいノードが

  • 子を持たないケース
  • 片方の子のみを持つケース

のときは、単純ですが、左右の子を持つケースの場合は少し複雑になりますね。20を削除しようとすると、20の左部分木の中での最大値15を20の位置に持ってくる事になります。

f:id:rahaema:20190416214426p:plain

実験(3)

次に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

追記(2019/04/18)

関連

平成18年度秋季基本情報午後問10

情報処理技術者試験 C

平成18年度秋季 基本情報技術者試験(FE)の午後問題10は、

  • 対象文字列を先頭から1文字ずつ順に調べ、パターン文字列が表現している条件を満足しているかどうかを判定するプログラム(正規表現もどき)

に関する問題でした。

f:id:rahaema:20190409222253p:plain

プログラム例(h18a_fe_pm10.c)

実行結果

本問のパターン文字列のルールだと、平成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"にマッチするのでまずいですが…。

平成18年度秋季基本情報午後問6

情報処理技術者試験 C

平成18年度秋季 基本情報技術者試験(FE)の午後問題6は、

  • 4けたの数字をなるべく少ない回数の推測で当てるゲーム Hit & Blow

に関する問題でした。

f:id:rahaema:20190408212259p:plain

プログラム例(h18a_fe_pm6.c)

実行結果

$ gcc h18a_fe_pm6.c && ./a.out
[1回目] 各けたが異なる4けたの数を入力してください: 1234
1234は0Hit, 1Blowです。

[2回目] 各けたが異なる4けたの数を入力してください: 2345
2345は0Hit, 2Blowです。

[3回目] 各けたが異なる4けたの数を入力してください: 3456
3456は3Hit, 0Blowです。

[4回目] 各けたが異なる4けたの数を入力してください: 3457
3457は2Hit, 0Blowです。

[5回目] 各けたが異なる4けたの数を入力してください: 8456
正解です。

関連

平成19年度春季ソフトウェア開発午後問5

情報処理技術者試験 C

平成19年度春季 ソフトウェア開発技術者試験(SW)の午後問題5は、

に関する問題でした。

f:id:rahaema:20190408054325p:plain

プログラム例(h19h_sw_pm5.c)

実行結果

$ gcc h19h_sw_pm5.c && ./a.out
123-45-67+89
123-4-5-6-7+8-9
123+45-67+8-9
123+4-5+67-89
12-3-4+5-6+7+89
12+3-4+5+67+8+9
12+3+4+5-6-7+89
1+23-4+56+7+8+9
1+23-4+5+6+78-9
1+2+34-5+67-8+9
1+2+3-4+5+6+78+9
-1+2-3+4+5+6+78+9

関連