Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

平成17年度春期基本情報午後問4

情報処理技術者試験 C

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

に関する問題でした。ヒープソートについては、平成30年度春季基本情報午後問8でも出題されていますね。こちらでは、バブルソートとの速度比較も行なっています。また、同じヒープソートでも両者の実装の違い(再帰と繰り返し)に注目するのも面白いかもしれません。

f:id:rahaema:20190503054525p:plain

プログラム例(h17h_fe_pm4.c)

実行結果

$ gcc h17h_fe_pm4.c && ./a.out
Before : 5 17 1 5 7 14 12 3 16 19 13 8 12 18 13 16 8 2 10 0
After  : 0 1 2 3 5 5 7 8 8 10 12 12 13 13 14 16 16 17 18 19

関連

平成17年度春期基本情報午後問2

情報処理技術者試験 C

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

  • 照合文字列に一致する文字列を置換するプログラム

に関する問題でした。

f:id:rahaema:20190502070126p:plain

プログラム例(h17h_fe_pm2.c)

実行結果

図の例を実際に実行してみました。

$ gcc h17h_fe_pm2.c && ./a.out
Before: aabcabb
After : aABCcABCb

関連

平成17年度秋期基本情報午後問4

情報処理技術者試験 C

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

  • 中置表記法による正しい数式を、スタックを用いて後置表記法(逆ポーランド記法)に変換するプログラム

に関する問題でした。

f:id:rahaema:20190501163025p:plain

プログラム例(h17a_fe_pm4.c)

実行結果

$ gcc h17a_fe_pm4.c && ./a.out
(2+4)*3+5*6
24+3*56*+

関連

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

情報処理技術者試験 C

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

に関する問題でした。ちなみに、平成29年度春季基本情報午後問8でも出題されています。

f:id:rahaema:20190429152718p:plain

プログラム例(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年度春季基本情報午後問11

情報処理技術者試験 Ruby

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

  • 迷路(Maze)

に関する問題でした。Javaでの出題ですが、面白そうな題材なのでRubyで取り組んでみました。

f:id:rahaema:20190427052606p:plain

プログラム例(h31h_fe_pm11.rb)

実行結果

$ ./h31h_fe_pm11.rb
↓ → → → → ↓ ↓ ← ← ← ←

関連

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

情報処理技術者試験 C

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

に関する問題でした。

f:id:rahaema:20190424222749p:plain

プログラム例(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

情報処理技術者試験 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:マルチパス