アルゴリズムの基本

前回までで、コンピュータは0と1で計算できると分かりました。 でも「計算できる」と「目的を達成できる」は別もの。正しい順番で指示を並べる 必要があります。 その指示の並べ方の設計図が アルゴリズム です。

アルゴリズムは何でできている？ ― 3つの部品

どんなに複雑な処理も、次の 3つの基本構造（制御構造） の組み合わせでできています。

構造	意味	日常の例
順次	上から順に実行	米をとぐ → 炊く → 盛る
分岐（選択）	条件で道を分ける	雨なら傘を持つ、晴れなら持たない
反復（くり返し）	条件の間くり返す	皿が全部きれいになるまで洗う

たった3つ。プログラミングが難しく見えるのは、この3つが 入れ子（くり返しの中に分岐がある、のように中に中がある）になっているだけ。 部品そのものは、ずっとこの3種類です。

フローチャートはどう読む？ ― 手順を図で描く

手順を図にしたものが フローチャート。記号の意味はシンプルです。

• 角丸の四角：開始・終了
• 長方形：処理（何かをする）
• ひし形：分岐（条件で Yes / No に分かれる）
• 矢印：流れの向き

   ( 開始 )
      │
 ┌────┴────┐
 │ 点数 ≥ 60？ │  ← ひし形＝分かれ道
 └──┬───┬──┘
 Yes│    │No
 [合格]  [不合格]
   └──┬──┘
   ( 終了 )

ポイントは ひし形＝分かれ道、これだけ。 ここを押さえれば、どんなフローチャートも迷わず追えるようになります。

同じ「探す」でも速さが変わる？ ― 2つの作戦

辞書から単語を探す場面を考えます。手順しだいで速さがまるで変わります。

作戦A（線形探索）：1ページ目から順にめくる。確実だけど、後ろにあると遅い。

作戦B（二分探索）：まん中を開く。目的より後ろなら前半を丸ごと捨て、前なら後半を捨てる。 これをくり返すと、1回ごとに候補が半分 になります。

実際に動かしてみましょう。「探す数」を選んで「まん中を見る」を押すと、 要らない側がバッサリ消えていきます。たった数回で見つかる速さを体感してください。

探す数: 3812172331384552617084

3

8

12

17

23

31

38

45

52

61

70

84

「まん中を見る」を押してスタート。

調べた回数: 0（全12個）

まん中を見る リセット

候補が半分ずつ減るので、$1000$ ページの辞書でも約10回（$2^{10}=1024$）で1ページに絞れます。

1000ページを二分探索すると…
1回目: 残り 500 → 2回目: 残り 250 → 3回目: 残り 125 → … → 約10回で発見！

同じ「探す」でも、手順しだいで100倍速くなる。 アルゴリズムを工夫する＝賢く近道する ということです。 ただし二分探索は 「あらかじめ並んでいる」ことが前提 なので、そこは要注意。

良いアルゴリズムの条件は？

アルゴリズムには、満たすべきお作法があります。

• 必ず終わる（無限ループしない）
• 手順があいまいでない（だれがやっても同じ結果になる）
• 正しい答えにたどり着く

そのうえで「より速い」「より少ない手間」を目指します。 データが増えたときの手間の増え方の目安を 計算量 と呼び、 二分探索のように候補が半分ずつ減るやり方が好まれます。

手順の設計図（アルゴリズム）が描けるようになりました。 次は、その設計図を コンピュータが分かる言葉 に翻訳します。 いよいよ次回、プログラミング入門 ―― 実際にコードを書いてみましょう。