今回は【基礎理論(アルゴリズム)編】アルゴリズムとフローチャートについて紹介します。
この内容は基本情報技術者試験の午後試験で必須のアルゴリズムでも問われます。
確実に得点できるようによく学習しておきましょう！
アルゴリズムについて
アルゴリズムとは、特定の問題を解決するための処理手順のことを指します。
例えば、「ホールケーキを4等分する」という問題を解決する方法を考えてみましょう。
「90度ずつ切り分けていく」や「まず半分に切り分けてから、それを更に半分に切り分ける」などなど…
様々な方法が思い浮かぶと思いますが、こういった手順のことをアルゴリズムと呼ぶわけですね。
さて、アルゴリズムには3つの基本構造があり、複雑な処理も全てそれらの組み合わせで表現できると言われています。
まずはその3構造をご紹介しましょう。
- 順次
順次処理は、“ある処理が終わったら次の処理に進む”という処理構造になります。
ごく自然な処理構造ですね。
他の処理構造では、次の処理を飛ばしたり前の処理に戻ったりする事もあるので、順次構造も大切な処理構造の一つです。
「1行読んだら次の行を読む」という風にしてこの記事を読んでいただいているのであれば、それも順次処理ですね！ - 選択(分岐)
選択処理は、“ある条件を満たした場合にのみ処理を行う”(満たさない場合は別の処理を行う)ことを指しています。
プログラミング言語ではよくif文などで実装されています。
ifは日本語で「もし～なら」の意味なので、選択処理は「～ならば・・・を行う」という処理になるんですね！
「興味がわかなければ読み飛ばす」という読み方をされているのであれば、それは選択(分岐)処理になります。
(できれば読み飛ばさないでください…) - 繰り返し
繰り返し処理は、“ある条件を満たしている間は同じ処理を繰り返す”という処理構造になります。
条件判定を行う点は選択(分岐)処理に似ていますが、選択処理には繰り返しの仕組みがありません。
繰り返し処理は何度も同じ処理を繰り返すことができるので、選択処理と区別をつけるようにしてください。
「理解が深まるまでこの記事を読み返す」という勉強の仕方をされているのであれば、それは繰り返し処理を行っていることになります！
フローチャートについて
先ほどはアルゴリズムの基本的な構造をご紹介しましたが、ここからはフローチャートについて説明していきたいと思います。
フローチャートとは、記号を使用してアルゴリズムを視覚的に表現したもののことを指します。
フローチャートを使用すると、アルゴリズムの全体像を整理して捉えやすくなるため、作業の効率化を図ることができるんですね！
それでは、フローチャートでどのような記号が用いられるのかを確認してみましょう。
フローチャートでは、これらの記号を用いてアルゴリズムを表現していくことになります。
先ほど説明した選択(分岐)処理には“判断”の記号を、繰り返し処理には“ループ端”の記号を使用したりするんですね！
疑似言語について
基本情報処理技術者の午後試験では、必須問題としてアルゴリズムが出題されます。
これらの問題はアルゴリズムをプログラミング言語のように記述する“疑似言語”で出題されることになるので、フローチャートだけではなく、疑似言語での表現も学んでおきましょう。
(基本情報技術者試験は2023年4月に改訂を控えていますが、改定後の疑似言語の記述形式はすでに周知されています。詳しくは国家資格・試験部の公式Webサイト(https://www.jitec.ipa.go.jp/)をご覧ください。)
さて、改定までの疑似言語の記述方法を確認しておきましょう。
以下に示す表は【令和元年度 秋期 基本情報技術者試験 午後】の注記文を引用して作成したものになります。
試験問題には必ず疑似言語の仕様に関する説明が載っていますが、事前に覚えておくとスムーズに問題が解けると思いますので、上記の表は必ず押さえておきましょう。
また、表中にある前判定繰り返し処理と後判定繰り返し処理の違いについてはここで説明しておきたいと思います。
名前の通りですが、両者の間には条件判定のタイミングが処理の前なのか後なのかという点において違いがあります。
前判定繰返し処理は、事前に条件判定を行う為、条件を満たしていなかった場合は繰り返し処理に該当する部分を一度も実行せずに終わることがあります。
後判定繰返し処理は、処理後に条件判定を行う為、初めから条件を満たしていなかった場合でも一回は繰り返し処理を実行するという特徴があります。
似たような処理ですが、条件を満たしていなくても必ず1回は実行される後判定繰返し処理には気を付けておきましょう。
以上でアルゴリズムについての説明は終わりになります。
フローチャートと疑似言語の具体的な使用例は演習問題をやりながら確認していきましょう！
まとめ
- アルゴリズムは特定の問題を解決するための処理手順
- フローチャートはアルゴリズムを視覚的に表現する方法
- 疑似言語はアルゴリズムをプログラミング言語のように表現することができる
演習問題
1.アルゴリズムに関する記述として最も正しいものを選んでください
A.「ある処理の後に次の処理を行う」といった処理構造を選択処理と呼ぶ
B.後判定繰返し処理は条件を満たしていない場合でも必ず1回は実行される
C.「条件を満たしている場合は特定の処理を行う」といった処理構造を順次処理と呼ぶ。
2.次のフローチャートの示すアルゴリズムの結果として最も正しいaの値を選んでください
(ただし、a%2は「aを2で割った余り」を表しています。)
A.8.5
B.8
C.9
3.次の疑似言語の示すアルゴリズムの結果として最も正しいNの値を選んでください
A.0
B.10
C.-20
D.40
答えは次回の記事で確認してください。
前回の演習問題～解答例
1.解答:C
解説:
A.親と比べると、子の要素の方が“深さ”の値が大きくなります
B.枝(ブランチ)に関する記述です
C.正しい記述です
D.添え字でデータを管理するのは配列の特徴です
2.解答:C
解説:
A.深さが1だけ異なっていても“左詰め”で葉が配置されていれば完全二分木と呼べます
B.二分探索に使われるのは二分探索木です
C.正しい記述です。
D.全ての親が2つ以下の子要素をもつ木構造を二分木と呼ぶので、2つだけとは限りません。
3.解答:A
解説:
逆ポーランド記法の場合、左から順に数値を読んでいって、演算子に当たったら直前の2つの数値をその演算子で計算します。
問題文の数式であれば、次のように計算できます。
93÷13+2×-(÷の直前の9と3で割り算する)→313+2×-(+の前の1と3で足し算する)
→342×-(×の前の4と2で掛け算する)→38-(-の前の3と8で引き算する)→3-8→-5
