アルゴリズムと流れ図

ねらい

処理の手順を組み立てる方法を学びます。このレッスンを終えると、流れ図を読み書きでき、どんな処理も3つの基本の型で表せることを説明できるようになります。

アルゴリズムは、料理のレシピと同じです

アルゴリズムは、問題を解くための手順です。料理のレシピと同じで、次の性質を持ちます。

• 順序が決まっている。手順を入れ替えると結果が変わります。
• 曖昧さがない。「適量」では、誰がやっても同じ結果になりません。
• 必ず終わる。いつまでも終わらない手順は、アルゴリズムとは呼びません。

同じ問題に対して、アルゴリズムは複数あります。どれを選ぶかで、かかる時間と必要な記憶領域が変わります。

流れ図の記号

手順を図で表したものを流れ図（フローチャート）といいます。記号の意味は決まっています。

ひし形からは、必ず2本以上の線が出ます。条件が「はい」か「いいえ」で分かれるからです。

3つの基本の型

どんなに複雑な処理も、次の3つの組み合わせで表せます。

• 順次… 上から順に、1つずつ実行します。
• 選択（分岐）… 条件によって、進む道が分かれます。
• 繰返し（反復）… 条件を満たす間、同じ処理を繰り返します。

変数と代入

変数は、値を入れておく箱です。名前を付けて、後から取り出したり書き換えたりできます。

代入は、右の値を左の箱へ入れるという意味です。数学の等号とは違います。

• x ← x ＋ 1 は、「いまのxに1を足した値を、xへ入れ直す」という意味です。数学として読むと成り立ちませんが、手順としては「1つ増やす」を表しています。

2つの変数の中身を入れ替えるには、3つ目の箱が要ります。xとyを入れ替えたいとき、x ← y としてしまうと、xに入っていた値が失われます。先に別の箱へ退避してから入れ替えます。

処理にかかる時間

アルゴリズムの良し悪しは、データが増えたときにどれだけ時間が増えるかで比べます。

• 先頭から順に見る線形探索は、件数が2倍になると時間もおよそ2倍になります。
• 範囲を半分ずつ絞る2分探索は、件数が2倍になっても比較の回数は1回増えるだけです。
• 計算式（ハッシュ関数）で格納場所を割り出すハッシュ探索は、件数が増えても探す時間がほとんど変わりません。ただし、異なる値が同じ場所を取り合う「衝突」が起きることがあり、その対処も必要です。たとえば「キーを7で割った余り」をハッシュ値とすると、10と24はどちらも余りが3になり、同じ場所を取り合います。

件数が少ないうちは差が出ませんが、増えたときに大きな差になります。扱うデータの規模を考えて選ぶ、というのが判断の基準です。

まとめ

アルゴリズムは、順序が決まり、曖昧さがなく、必ず終わる手順です。流れ図では、ひし形が判断、長方形が処理を表します。順次・選択・繰返しの3つの組み合わせで、どんな処理も表せます。繰返しでは、終了条件に近づく変化があるかを必ず確かめます。

理解の確認

変数 x に 5、変数 y に 8 が入っています。この2つの値を入れ替えて、x が 8、y が 5 になるようにしたいとき、x ← y を実行してから y ← x を実行するとどうなるでしょうか。正しい手順もあわせて示してください。

答え: 両方とも8になり、5が失われます。まず x ← y でxに8が入ります。この時点で、xにあった5はどこにも残っていません。続けて y ← x を実行すると、xの中身（すでに8）がyへ入るので、xもyも8になります。

正しくは、3つ目の変数に退避してから行います。

1. t ← x（tに5を退避する）
2. x ← y（xに8が入る）
3. y ← t（yに退避しておいた5が入る）

代入は「右の値を左の箱へ入れる」操作で、入れた時点で左の箱の元の値は消えるため、上書きされる前に別の場所へ避けておく必要があります。

擬似言語で手順を追う

流れ図は図で手順を表しますが、同じ手順を文字だけで書く方法もあります。これを擬似言語といいます。たとえば「1から5までの数をすべて足す」という繰返し処理は、次のように書けます。

合計 ← 0
iを1から5まで1ずつ増やす:
  合計 ← 合計 ＋ i

擬似言語を読み解く近道は、上から順に、実際に値を書き出しながら追うことです。これをトレースといいます。上の手順をトレースすると、次のようになります。

繰返しが終わったとき、合計には15（1から5までの和）が入っています。表に書き出しながら1行ずつ追うと、頭の中だけで追うより間違いにくくなります。