Mae向きなブログ

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

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

情報処理技術者試験 C

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

  • トポロジカルソート

に関する問題でした。

プログラム例(h19a_sw_pm5.c)

実行結果

図1の赤文字はノード番号です。実行結果をみると、図2と同じ結果となりました。

f:id:rahaema:20190407170110p:plain

$ gcc h19a_sw_pm5.c && ./a.out
ノード 0 : トポロジカルソート値 2
ノード 1 : トポロジカルソート値 4
ノード 2 : トポロジカルソート値 3
ノード 3 : トポロジカルソート値 5
ノード 4 : トポロジカルソート値 1
ノード 5 : トポロジカルソート値 6

関連

平成19年度春季基本情報午後問10

情報処理技術者試験 C

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

  • リーグ戦の勝敗表を出力するプログラム

に関する問題でした。

f:id:rahaema:20190406185209p:plain

プログラム例(h19h_fe_pm10.c)

  • 52行目は、rank++ではないですね。実行してみて気づきました。本番の試験では実行はできないので、注意!!

  • sort関数は、本問と同じ回の問4で出題された挿入ソートを用いました。

実行結果

$ gcc h19h_fe_pm10.c && ./a.out
順位    チーム名   勝ち   負け    勝率
1       Kings        33     17   0.660
2       Queens       32     18   0.640
3       Bishops      27     23   0.540
3       Knights      27     23   0.540
5       Rooks        19     31   0.380
6       Pawns        12     38   0.240

関連

平成19年度春季基本情報午後問6

情報処理技術者試験 C

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

  • 双六（すごろく）ゲーム

に関する問題でした。

f:id:rahaema:20190406070806p:plain

プログラム例(h19h_fe_pm6.c)

main関数とprtpiece関数内で同じようなswitch case文が登場するので、そこが少し納得できない部分ですが、機能の中に、「割り当てられている動作指示の内容を表示する」とあるので、このままにしておきました。

実行結果

$ gcc h19h_fe_pm6.c && ./a.out
双六を開始します。
プレーヤID : 0
    Start |**                     | Goal!
プレーヤID : 1
    Start |*****                  | Goal!
        ジャンプ!
    Start |                       | Goal!
プレーヤID : 2
    Start |********               | Goal!
        ジャンプ!
    Start |**                     | Goal!
プレーヤID : 3
    Start |********               | Goal!
        ジャンプ!
    Start |**                     | Goal!
プレーヤID : 0
    Start |**********             | Goal!
プレーヤID : 1
    Start |*********              | Goal!
        1回休み!
プレーヤID : 2
    Start |*********              | Goal!
        1回休み!
プレーヤID : 3
    Start |*****                  | Goal!
        ジャンプ!
    Start |                       | Goal!
プレーヤID : 0
    Start |*****************      | Goal!
プレーヤID : 3
    Start |***********            | Goal!
プレーヤID : 0
    Start |***********************| Goal!
プレーヤID : 0 の勝ちです。

関連

平成19年度春季基本情報午後問4

情報処理技術者試験 C

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

  • 挿入ソート

に関する問題でした。

f:id:rahaema:20190405052439p:plain

プログラム例(h19h_fe_pm4.c)

実行結果

バブルソートと速度比較を行ってみました。計算量は O(n^2) と両者同じですが、実行速度にこれだけの差が出てきますね。同じ計算量なのになぜこれほど違うのか考察してみると更に理解が深まると思います。

$ gcc h19h_fe_pm4.c && ./a.out
Insert Sort  = 8.529973[s]
Bubble Sort = 31.681880[s]

関連

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

情報処理技術者試験 C

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

  • 8文字×6文字の文字パターンを回転又は反転して標準出力に出力する関数invert

に関する問題でした。

f:id:rahaema:20190331182602p:plain

プログラム例(h19a_fe_pm6.c)

実行結果

$ gcc h19a_fe_pm6.c && ./a.out
######
#
#
#
###
#
#
#

########
   #   #
   #   #
       #
       #
       #

#
#
#
#   #
#   #
########

#
#
#
###
#
#
#
######

######
     #
     #
     #
   ###
     #
     #
     #

平成19年度秋季基本情報午後問4

情報処理技術者試験 C

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

  • スタックを使って、実数値を10新文字列(文字列)に変換する副プログラムFloatFormat

に関する問題でした。

f:id:rahaema:20190328183751p:plain

プログラム例(h19a_fe_pm4.c)

疑似言語を具現化するにあたり、FloatFormat関数の仕様を以下のように変更してあります。

  • 返り値が文字列の長さでしたが、char型へのポインタを返すように変更
  • 仮引数名Floatをvalに変更

実行結果

$ gcc h19a_fe_pm4.c && ./a.out
12.345
34.56
-12.3
0.01
0.0
-0.01

関連

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

情報処理技術者試験 C

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

に関する問題でした。

f:id:rahaema:20190326183842p:plain

プログラム例(h20h_sw_pm5.c)*1

実行結果

$ gcc h20h_sw_pm5.c && ./a.out
1 2 3 4 5 6 7 8

バブルソートとの速度比較

これだけで終わっては面白くないので、効率の悪いことで有名な O(n^2) のアルゴリズムであるバブルソートと速度比較を行ってみました。

次のようにプログラムを加筆修正しました。

#include <time.h>

void bubble_sort(int [], int );

void bubble_sort(int a[], int n) {
  int i, j, tmp;
  for (i = 0; i < n - 1; i++) {
    for (j = n - 1; j > i; j--) {
      if (a[j - 1] > a[j]) {
        tmp = a[j - 1];
        a[j - 1] = a[j];
        a[j] = tmp;
      }
    }
  }
}

int main(void) {
  int hnum = 100000, i;
  int arr1[hnum], arr2[hnum];
  clock_t c1, c2;

  srand((unsigned)time(NULL));
  for (i = 0; i < hnum; i++) {
    arr1[i] = arr2[i] = rand();
  }

  c1 = clock();
  merge_sort(arr1, 0, hnum - 1);
  c2 = clock();
  printf("Merge Sort  = %f[s]\n", (double)(c2-c1)/CLOCKS_PER_SEC);

  c1 = clock();
  bubble_sort(arr2, hnum);
  c2 = clock();
  printf("Bubble Sort = %f[s]\n", (double)(c2-c1)/CLOCKS_PER_SEC);
  return 0;
}

実行結果

要素の数を100000個でやってみたのが以下です。

$ gcc h20h_sw_pm5_cmp.c && ./a.out
Merge Sort  = 0.044918[s]
Bubble Sort = 36.233415[s]

以前、ヒープソートとバブルソートでの速度比較を行ったときも、O(n \log n)とO(n^2)の性能差を肌で感じることができましたが、O(n \log n)のアルゴリズムであるマージソートも高速ですね。

関連

*1:実装の都合でフローチャートの関数構成と少し変更しています。