基本情報技術者へのステップアップ -アルゴリズムを解く！-

Page Contents

はじめに。
擬似言語に慣れておく
- ●条件分岐
- ●繰り返し処理
実践例をみてみよう。
- 擬似言語の実例
- 擬似言語をJavaに置き換えてみる
プログラム実行イメージ図を見逃さない
擬似言語の対策
参考：平成30年春期の午後問8をJavaに置き換えてみる
- ●設問１
- ●設問２

はじめに。

基本情報技術者の午後試験の問 8、データ構造とアルゴリズムの問題の解き方を考えてみましょう。

個々の問題の考え方は過去問の解説書に任せるとして（！）、まずは設問に対して気合負けしないことが大切です。そのために必要なことは、

擬似言語に慣れておく
プログラム全体の流れを把握する（設問の最初に書いてあるので見落とさないこと）
時間配分に気をつける

です。

擬似言語に慣れておく

最初は、擬似言語に慣れることから始めるとよいと思います。擬似言語で分かりにくい場合は、使い慣れたプログラム言語に変換してみるといいです。今回は、擬似言語をJavaと対比してみてみましょう。

●条件分岐

▲ 条件式
| 　処理
▼

▲ 条件式
| 　処理 1
+---
| 　処理 2
▼

if (条件式) {
    処理;
}

if (条件式) {
    処理 1;
} else {
    処理 2;
}

●繰り返し処理

■ 条件式
| 　処理
■

■
| 　処理
■ 条件式

■ 変数：初期値, 条件式, 増分
| 　処理
■ 条件式

while (条件式) {
    処理;
}

do {
    処理;
} while (条件式);

for ( 変数 = 初期値; 条件式; 増分 ) {
    処理;
}

実践例をみてみよう。

擬似言語の実例

では、平成30年秋期の午後問8を例にして見てみましょう。

擬似言語をJavaに置き換えてみる

擬似言語を読むととても難しそうですが、実際のプログラム（Java）を書いてみるとそんなに複雑ではないことがわかります。

全体のイメージは、設問に書いてある通り「与えられた計算式を解く」プログラムです。擬似言語の読みにくさに負けないようにしてくださいね。

int compute(Char[] Expression, int ExpLen) {
  Char[] Operator = new Char[100];
  int OpCnt;
  int[] Priority = new int[100];
  int[] Value = new int[100];
  Char chr;
  int i;
  int ip;
  int nest;

  // ▼▼▼ プログラム（解析処理）▼▼▼
  OpCnt = 0;
  Value[0] = 0;
  nest = 0;
  for (i = 0; i < ExpLen;, i++) {
    chr = Expression[i];
    if (('0' <= chr) && (chr <= '9')) {
      Value(OpCnt) = 10 * Value[OpCnt] + (int)Chr;
    } 
    if ((chr == '+') || (chr == '-') || (chr == '×') || (chr == '÷')) {
      Operator[OpCnt] = chr;
      if ((chr == '+') || (chr == '-')) {
        Priority[OpCnt] = nest + 1; // ←〇1
      } else {
        Priority[OpCnt] = nest + 2; // ←〇2
      }
      OpCnt = OpCnt + 1;
      Value[OpCnt] = 0;
      if (chr == '(') {
        nest = nest + 10; // ←〇3
      }
      if (chr == ')') {
        nest = nest - 10; // ←〇4
      }
    }
  }
  // ▲▲▲ プログラム（解析処理）▲▲▲

  // ▼▼▼ プログラム（計算処理）▼▼▼
  while(OpCnt > 0) {
    ip = 0; // ←〇5
    for (i = 1; i < OpCnt; i++) { // ←〇6
      if (Priority[ip] < Priority[i]) { // ←〇7
        ip = i;
      }
      chr = Operator[ip];
      if (chr == '+') {
        Value[ip] = Value[ip] + Value[ip + 1];
      }
      if (chr == '-') {
        Value[ip] = Value[ip] - Value[ip + 1];
      }
      if (chr == '×') {
        Value[ip] = Value[ip] * Value[ip + 1];
      }
      if (chr == '÷') {
        Value[ip] = Value[ip] / Value[ip + 1];
      }
      for (i = ip + 1; i < OpCnt; i++) {
        Value[i] = Value[i + 1];
        Operator[i - 1] = Operator[i];
        Priority[i - 1] = Priority[i];
      }
      OpCnt = OpCnt - 1;
    }
  }
  // ▲▲▲ プログラム（計算処理）▲▲▲

  return Value[0];
}

どうでしょうか？？なんとなく読みやすくなった気がしませんか？？このプログラムを読みながら問題を解いてみると少しわかりやすいかもしれません。

プログラム実行イメージ図を見逃さない

また、プログラムの実行イメージが設問にありますので、プログラムと合わせてみるとより分かりやすいと思います。

擬似言語の対策

なので、擬似言語対策としては２つあると思っています。

擬似言語を直接読めるようになるまで練習する
擬似言語を得意なプログラミング言語に置き換えて書いてみる

1.ができれば相当心強いですが、2.は解き始めるまでに時間が必要です。

ここで重要なのは時間配分です。アルゴリズムの問題の配点は20点で、試験時間が150分（2.5時間）なので、150(分)÷(20/100(点))=30(分)。

つまり、アルゴリズムの問題にかけれる時間は30分が目安です。

試験前の勉強のときは、次の方法を試してみましょう。

まずは、30分を目安に問題を解く
次に、最後まで時間をかけて解いてみる

参考：平成30年春期の午後問8をJavaに置き換えてみる

最後に。おまけとして、cをプログラム（Java）にしたものを書いておきます。過去問を解く際の参考にしてください。

全体のイメージは「ヒープを利用したデータを昇順に整列するアルゴリズム」です。

●設問１

int lchild(int i) {
  return 2 * i ＋ 1;
}
int rchild(int i) {
  return 2 * i ＋ 2;
}
int parent(int i) {
  return (i - 1) / 2;
}

void makeHeap(int[] data, int[] heap, int hnum) {
  int i;
  int k;
  for (i = 0; i < hnum; i++) {
    heap[i] = data[i]
    k = i;
    while(k > 0) {
      if ([ a ]) {
        swap(heap, k, [ b ]);
        k = parent(k);
      } else {
        break;
      }
    }
  }
}

void swap(int[] heap, int i, int j) {
  int tmp;
  tmp = heap[i];
  heap[i] = heap[j];
  heap[j] = tmp;
}

●設問２

void heapSort(int[] data, int[] heap, int hnum) {
  int last;
  makeHeap(data, heap, hnum);
  for (last = humn - 1; last > 0; i--) {
    swap(heap, 0, last);
    downHeap(heap, last - 1);
  }
}

void downHeap(int[] heap, int hlast) {
  int n;
  int tmp;
  n = 0;
  while(lchild(n) <= hlast) {
    tmp = lchild(n);
    if (rchild(n) <= hlast) {
      if (heap[tmp] <= heap[rchild(n)]) {
        tmp = rchild(n);
      }
    }
    if (heap[tmp] > heap[n]) {
      swap(heap, n, tmp);
    } else {
      return;
    }
    n = tmp;
  }
}

@Strategy