【基本情報技術者試験】アルゴリズムとフローチャート(流れ図)とは？

こんにちは。

今回は基本情報技術者試験の対策として、アルゴリズムとフローチャートの解説をしていこうと思います。

アルゴリズムとフローチャート(流れ図)とは？

アルゴリズムとは

アルゴリズムとは、問題を解決するときの処理手順のことです。

数学の問題で別解が複数存在するように、アルゴリズムにも複数の表現方法があります。

コンピュータ科学や数学に関しても、アルゴリズムは入力をもとに処理を行い、出力を得るために論理アルゴリズムはデータを処理したり、問題を解決したり、目標を達成するための方法を提供します。

フローチャート(流れ図)とは

アルゴリズムの表現方法には

• 文章
• 図
• 関数
• プログラム言語

の４つがあります。

このうち、図で表現することをフローチャート(流れ図)といいます。

基本情報技術者試験ではアルゴリズムの表現方法のうちこの流れ図が最もよく出題されるので、今回は流れ図について解説をしていこうと思います。

フローチャート(流れ図)の記号

フローチャートには以下の記号が使われます。

この楕円形の記号は端子と呼ばれ、記号の中に「開始」または「終了」と記載することによって処理手順の開始と終了を表すことができます。

この長方形の記号は処理と呼ばれ、その名の通り処理を記号の中に記載することによって様々な処理を表すことができます。

このひし形の記号は判断と呼ばれ、条件を記号の中に記載することによって処理を分岐させることができます。

この記号はループ端と呼ばれ、繰り返し処理の開始と終了を表します。

開始を表すときは上の向きで使い、終了を表すときは逆さの向きで使います。

これらの記号を線や矢印で繋ぎフローチャートを作成します。

フローチャートを作成してみよう

それでは試しに「ある数値を７の倍数に変換するアルゴリズム」をフローチャートで表してみましょう。

ある数値を７の倍数に変換するアルゴリズムをフローチャートで表すと以下のようになります。

判断記号にX÷7=0という条件を記載して処理を分岐させています。

このように条件分岐を行う際は判定結果を表すYesやNoなどを上の図のように記載する必要があります。

条件に当てはまればYes、当てはまらなければNoの方に進みます。

Xが７で割り切れる場合にXを返すので、７の倍数に変換するアルゴリズムにしっかりなっていますね。

基本情報技術者試験の過去問にチャレンジしてみよう

まず以下の２つの問題を解いてみてください。

---

問1.解答

まず直前の④の処理について考えます。

「m ← m－n」という処理をしているので、”更新前のm”の値は、”更新後のm”と”n”の和です。④の処理後は m＝n になっていますから、”更新前のm”の値は 2n で表すことができます。

次に⑤の処理について考えます。

「n ← n－m」という処理をしているので、”更新前のn”の値は、”更新後のn”と”m”の和です。m＝2n ですから、”更新前のn”の値は 3n で表すことができます。

これより前にはm及びnを更新する処理はないので、処理開始時に m：n＝2：3 であれば最終的に m＝n となることがわかります。

mはa、nはbが代入される変数なので初期値aとbの関係は a：b＝2：3、これを式に変換すると「3a＝2b」となります。

よって「エ」が正解です。

---

問2.解答

流れ図を見ると、被乗数がX、乗数がY、結果としてZを出力するので「X × Y ＝ Z」が成立すれば良いことがわかります。

細かな説明がない流れ図の穴埋めでは論理的に答えを導くのは難しいので、XおよびYにトレースが簡単な数値を設定して、出力Zが適切な値かどうかで正しい組合せを探すのが確実な解法です。

ここではX＝3，Y＝3を使います（16ビット表記だと「0000 0000 0000 0011）。

また、あるビット列を左に1ビットシフトすると2倍、右に1ビットシフトすると1／2したのと同じになります（ビットあふれは無視します）。

ア…唯一”3×3″の正しい結果である”9″を出力する「ア」の組合せが正解となります。

1. Yの0ビット目は1なので、Z←(0＋3) //Z＝3
2. Xを1ビット左シフト //X＝6
3. Yを1ビット右シフト //Y＝1
4. i←(1＋1) //i＝2
5. Yの第0ビットは1なので、Z←(3＋6) //Z＝9
6. Xを1ビット左シフト //X＝12
7. Yを1ビット右シフト //Y＝0
8. 以後、Yの第0ビットはi>16になるまで0なので、加算は行われずにループ終了
9. Zを出力する //Z＝9

イ…誤りです。

1. Yの第0ビットは1なので、Z←(0＋3) //Z＝3
2. Xを1ビット右シフト //X＝1
3. Yを1ビット左シフト //Y＝6
4. i←(1＋1) //i＝2
5. Yを左にシフトすると第0ビットに0が挿入される。以後、Yの第0ビットはi>16になるまで常に0なので、加算は行われずにループ終了
6. Zを出力する //Z＝3

ウ…誤りです。

1. Yの第15ビットは0なので加算はなし
2. Xを1ビット左シフト //X＝6
3. Yを1ビット右シフト //Y＝1
4. i←(1＋1) //i＝2
5. Yを右にシフトすると第15ビットには0が挿入される。以後、Yの第15ビットはi>16になるまで常に0なので、加算は行われずにループ終了
6. Zを出力する //Z＝0

エ…誤りです。

1. Yの第15ビットは0なので加算はなし
2. Xを1ビット右シフト //X＝1
3. Yを1ビット左シフト //Y＝6
4. i←(1＋1) //i＝2
5. Yの第15ビットは0なので加算はなし
6. Xを1ビット右シフト //X＝0
7. Yを1ビット左シフト //Y＝12
8. Xが0になったので、加算処理が行われたとしてもZは0のままでループ終了
9. Zを出力する //Z＝0

このアルゴリズムを一言で言うならば、Yの第nビットが1であれば、ZにX×2ⁿを加算する処理を繰り返すものということになります。

まとめ

今回は基本情報技術者試験の対策としてアルゴリズムとフローチャートについて解説しました！

最後までご精読いただきありがとうございました。