アルゴリズムとプログラミング1~アルゴリズムと流れ図(フローチャート)~

snack
snack

「アルゴリズムとプログラミング」は非常にボリュームが多い上に難解で、苦手にしている人が多い分野っす。

ボキタロー
ボキタロー

勉強するのに時間がかかりそうだね。

snack
snack

ただ、この分野からの出題は100問中1~3問程度なんすよ。

ボキタロー
ボキタロー

たったそれだけしかでないの?じゃあ勉強してもコスパが悪いね。

snack
snack

そうなんす。なので、ちょっとこの分野がしんどいと思う人は今回と次回の内容はスルーしてもらってもいいっすよ。他がしっかりとできれば十分合格はできるっすからね。

目標・アルゴリズムの基本的な考え方と,擬似言語などによる表現方法,プログラミングの目的を理解する。
説明・業務の分析やシステム化を行うために,アルゴリズムの基本的な考え方を理解する。
・簡単なアルゴリズムを流れ図や擬似言語で表現する方法を理解する。
・アルゴリズムを実行するためにプログラミングを行うことを理解する。
アルゴリズムとプログラミングの概要

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

コンピューターに、ある特定の目的を達成させるための処理手順のことをアルゴリズムといいます。

アルゴリズムは文章で書くこともできますが、それだとわかりにくく相手に伝わりづらいので、流れ図(フローチャート)で図式化して視覚的にわかりやすく表現することがあります。

流れ図で用いる記号は、JIS規格によって次のように標準化が図られています。

記号読み方説明
端子流れ図の開始と終了を表す。
処理演算などの処理を表す。
判断「YesかNoか」などの、処理を分岐するための条件を表す。
ループループ(繰り返し)の開始と終了を表す。
処理の順番を表す。

アルゴリズムの基本構造

一見、複雑に見えるアルゴリズムも突き詰めていくと、順次・選択・繰返しという3つの基本構造の組み合わせによって構成されています。

順次構造

プログラムの上から順番に連続して処理を実行します。

順次構造

選択構造

条件によって処理を分岐します。

選択構造

繰返し構造

条件によって同じ処理を反復します。まず条件を判断してから処理を行う前判定型と処理の結果を受けて判定する後判定型があります。

繰返し構造

言葉で説明してもわかりにくいので、実際に流れ図を書いてみましょう。1から5までの合計を求めるプログラムを流れ図にすると次のようになります。iとansは変数とします。「→」は変数に値を代入するという意味です。

流れ図
snack
snack

流れ図の問題を解く場合はトレース表を作成するのが効果的っす。

参考

流れ図の上から順番通りに処理をたどっていくことをトレースといい、その結果(変数の値)を表にしたものをトレース表といいます。

処理変数 ans変数 i
初期値01
1(=0+1) 2
3(=1+2)3
6(=3+3)4
10(=6+4)5
15(=10+5)6
(i>5のため終了)
トレース表

さらっと学習(代表的なアルゴリズム)

アルゴリズムの中にはよく使われる”お決まりのもの”がいくつもあります。ここでは、そういった代表的なアルゴリズムを学習していきます。

併合(マージ)

複数のファイルやデータ、プログラムなどを、決められたルールに従って一つに統合するアルゴリズムです。ただし、結合の際にデータの並び順に変更はかけません。

参考

結合時にデータの並び替えを行うアルゴリズムはマージソートといい、単なる併合(マージ)とは区別して使うことが一般的です。

探索のアルゴリズム

複数のデータの中から条件に一致した値を見つけるために用いられるアルゴリズムを探索(検索・サーチ)といいます。代表的なものとして、線形探索法(リニアサーチ)二分探索法(バイナリサーチ)があります。

線形探索法(リニアサーチ)

先頭から順に比較を行い、条件に合うデータが見つかれば終了するアルゴリズムです。

線形探索法(リニアサーチ)

シンプルでわかりやすいアルゴリズムですが、対象となるデータが膨大で、しかも探したいデータが後ろのほうにある場合はデータを照会する回数が多くなり時間がかかってしまうといった短所があります。


二分探索法(バイナリサーチ)

昇順または降順に並んでいるデータの集合の中央にあるデータから、探しているデータがその前後どちらにあるかを判断し、データを半分に絞り込むという作業を繰り返すことで、データを探索するアルゴリズムです。

二分探索法(バイナリサーチ)

線形探索法に比べて、データを照会する回数が少なくて済みますが、要素の値が昇順または降順に並んでいる必要があります。

整列のアルゴリズム

データを昇順(小さい順)か降順(大きい順)に並べ替えるアルゴリズムを整列(ソート)といいます。ITパスポート試験では、選択ソートバブルソートクイックソートが出題されます。

選択ソート

データの中から最小値を見つけ、先頭要素と入れ替えます。続いて残りのデータの中から最小値を探し、2番目の要素と入れ替えます。これを繰り返すことで整列を行います。

選択ソート

バブルソート

隣り合う要素の大小を比較して、入れ替えを繰り返しながら整列させるソートアルゴリズムです。

バブルソート

クイックソート

適当な値(ピボット)を境界値として選択し、ピボット未満の要素を先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割することを繰り返すことで整列を行います。

クイックソート

確認○×問題

問1

図1のように二つの正の整数A1、A2を入力すると、二つの数値B1、B2を出力するボックスがある。B1はA2と同じ値であり、B2はA1をA2で割った余りである。図2のように、このボックスを2個つないだ構成において、左側のボックスのA1として49、A2として11を入力したとき、右側のボックスから出力されるB2の値は「5」となる。

答え:×

・左側のボックス:入力A1=49、入力A2=11

出力B1は「11」(A2 → B1)となります。

出力B2は「5」(A1/A2の余り→ B2)となります。

・右側のボックス:入力A1=B1=11、入力A2=B2=5

出力B1は「5」(A2 → B1)となります。

出力B2は「1」(A1/A2の余り→ B2)となります。

以上より、右側のボックスから出力されるB2の値は「1」となります。

問2

9けたの数字に対して、次のルールでチェックディジットを最後尾につけることにした。チェックディジットを付加した10けたの数字として「6655333331」は正しい。

ルール1:各けたの数字を合計する。

ルール2:ルール1で得られた数が2けたになった場合は、得られた数の各けたの数字を合計する。この操作を、得られた数が1けたになるまで繰り返す。

ルール3:最終的に得られた1けたの数をチェックディジットとする。

答え:〇

チェックディジット(検査数字)とは、符号の入力誤りなどを検出するために元の符号に付加される数字のことです。チェックディジットを最後尾につける前の9桁の数字は「665533333」なので、これを使って検証していきます。

・ルール1:各けたの数字を合計。

6+6+5+5+3+3+3+3+3=37

・ルール2:ルール1で得られた数が2けたなので、各けたの数字を合計。

3+7=10

2けたなので、再度各けたの数字を合計。

1+0=1

・ルール3:最終的に得られた1けたの数「1」をチェックディジットとして最後尾につける。

「665533333」+「1」→「6655333331」

問3

大文字の英字から成る文字列の暗号化を考える。暗号化の手順と例は次のとおりである。この手順で暗号化した結果が “EGE” であるとき、元の文字列は”DEB”である。

答え:〇

手順にしたがって、元の文字列”DEB”を暗号化してみます。

・手順1:英字を文字番号に変換。

”D”→”3”

”E”→”4”

”B”→”1”

・手順2:n文字目にnを加算。

1文字目に1を加算→3+1=”4”

2文字目に2を加算→4+2=”6”

3文字目に3を加算→1+3=”4”

・手順3:26で割った余りを新たな文字番号に。

4÷26=0・・・余り”4”

6÷26=0・・・余り”6”

4÷26=0・・・余り”4”

・手順4:文字番号を英字に変換。

”4”→”E”

”6”→”G”

”4”→”E”

以上より、暗号化した結果が “EGE” であるとき、元の文字列は”DEB”となります。

問4

流れ図で示す処理を終了したとき、xの値は28となる。

答え:×

トレース表を作っていきます。「x=y」になるまで条件に応じた処理を繰り返します。

処理xy
初期値9842
①(x>y)56(=98-42)42
②(x>y)14(=56-42)42
③(x≦y)1428(=42-14)
④(x≦y)1414(=28-14)
5(x=y)1414

以上より、処理を終了したときのxの値は14となります。

問5

表に示す構成のデータを、流れ図の手順で処理する場合について考える。流れ図中のx、y、zをそれぞれデータ区分A、B、Cと適切に対応させれば、比較(「xか?」、「yか?」、「zか?」)の回数の合計は、最低170回で済む。

答え:〇

もし分岐がYesの場合はその処理は終了となり、Noの場合は次の分岐に渡されます。つまり、件数の多いデータ区分を先の分岐で処理したほうが全体の比較回数を少なくすることができます。

したがって、もっとも件数の多いデータ区分Cをx、次に多いデータ区分Bをy、データ区分Aをzとして処理することで、分岐処理の回数を最も少なくすることができます。

分岐処理YesNo比較回数
x(データC)か?50(データC)50(C以外)100
y(データB)か?30(データB)20(BとC以外)50
z(データA)か?10(データA)10(その他)20

以上より、最も少ない比較回数の合計は、100+50+20=170回となります。

問6

配列に格納されているデータを探索するときの、探索アルゴリズムに関する以下の記述のうち、適切なものは2つある。

  1. 2分探索法は、探索対象となる配列の先頭の要素から順に探索する。
  2. 線形探索法で探索するのに必要な計算量は、探索対象となる配列の要素数に比例する。
  3. 線形探索法を用いるためには、探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
  4. 探索対象となる配列が同一であれば、探索に必要な計算量は探索する値によらず、2分探索法が線形探索法よりも少ない。

答え:×

1の記述(誤り):探索対象となる配列の先頭の要素から順に探索するのは線形探索法(リニアサーチ)です。

2の記述(正しい):線形探索法は先頭の要素から順に探索する方法のため、探索対象となる配列の要素数が増えれば、比例的に探索するのに必要な計算量も増加します。

3の記述(誤り):要素の値が昇順又は降順にソート(整列)されている必要があるのは二分探索法(バイナリサーチ)です。

4の記述(誤り):探索対象となる配列が同一であれば、平均的な比較回数は2分探索法が線形探索法よりも少なくなります。ただし、配列の先頭のほうに探したいデータがあるような場合は、線形探索法のほうが比較回数が少なくなる場合もあります。

問7

隣り合う要素の大小を比較して、入れ替えを繰り返しながら整列させるソートアルゴリズムをクイックソートという。

答え:×

設問はバブルソートの説明となります。なおクイックソートとは、適当な値(ピボット)を境界値として選択し、ピボット未満の要素を先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割することを繰り返すことで整列を行うアルゴリズムです。