第2部　3つの基本構造

第2部　3つの基本構造

このワークの目標

どれほど複雑に見えるアルゴリズムでも、基本となる構造は次の3つです。

1. 順次
2. 選択
3. 反復

このワークでは、プログラムの細かな書き方ではなく、処理の組み立て方に注目します。

• 順次・選択・反復の違いを説明できる
• 3つの基本構造を組み合わせてアルゴリズムを作れる
• 複数の処理を一つの大きな処理ブロックとして見られる
• 大きな処理ブロックの中を、さらに細かな処理へ分けられる
• アルゴリズム全体を、大きな処理ブロックの順次として捉えられる

1．アルゴリズムを作る3つの基本構造

アルゴリズムは、処理を実行する順番を決めたものです。

処理の進み方は、次の3種類に分けられます。

複雑なアルゴリズムも、この3つを組み合わせて作られています。

1-1．順次

順次は、処理を決められた順番に実行する構造です。

図1-1　順次構造

図1-1では、3つの処理を上から順番に実行します。

処理A
  ↓
処理B
  ↓
処理C

例えば、ゲームを起動するときは、次のような順番で処理します。

画面を用意する
  ↓
画像を読み込む
  ↓
ゲームを開始する

1-2．選択

選択は、条件によって実行する処理を選ぶ構造です。

図1-2　選択構造

図1-2では、条件 a > b の結果に応じて、左右どちらか一方の処理を実行します。分岐した流れは、その後で一つに合流します。

プレイヤーの体力が0以下か
  ├─ はい　→ ゲームオーバーにする
  └─ いいえ→ ゲームを続ける

すべての処理を実行するのではなく、条件に合った処理を選びます。

1-3．反復

反復は、同じ処理を繰り返す構造です。

図1-3　反復構造

図1-3では、条件 a <= 10 が成り立つ間、a ← a + 1 を繰り返します。条件が成り立たなくなると、反復の外へ進みます。

すべての敵について繰り返す
  敵を移動する
  敵の状態を更新する
繰り返し終わり

練習1　3つの基本構造を見分けよう

次の処理が、順次・選択・反復のどれに当たるか答えよう。

2．3つの基本構造を組み合わせる

実際のアルゴリズムでは、順次・選択・反復を組み合わせます。

例えば、プレイヤーを更新する処理を考えてみましょう。

キー入力を調べる
  ↓
右キーが押されているか
  ├─ はい　→ プレイヤーを右へ移動する
  └─ いいえ→ 何もしない
  ↓
プレイヤーの座標を更新する

このアルゴリズム全体は上から順番に進みます。その途中に、右キーが押されているかを調べる選択が入っています。

順次
  ├─ キー入力を調べる
  ├─ 選択
  │    ├─ 押されている　→ 右へ移動する
  │    └─ 押されていない→ 何もしない
  └─ 座標を更新する

2-1．反復の中に選択を入れる

複数の敵のうち、生きている敵だけを更新する処理を考えます。

すべての敵について繰り返す
  敵が生きているか
    ├─ はい　→ 敵を更新する
    └─ いいえ→ 何もしない
繰り返し終わり

この処理では、反復の中に選択が入っています。

2-2．選択の中に順次を入れる

プレイヤーが敵に当たったか
  ├─ はい
  │    体力を減らす
  │      ↓
  │    ダメージ音を鳴らす
  │      ↓
  │    プレイヤーを後ろへ戻す
  │
  └─ いいえ
       何もしない

「はい」の中には、3つの処理を順番に行う順次が入っています。

練習2　外側と内側の構造を答えよう

すべてのアイテムについて繰り返す
  プレイヤーとアイテムが当たったか
    ├─ はい　→ アイテムを取得する
    └─ いいえ→ 何もしない
繰り返し終わり

外側の構造：＿＿＿＿＿＿
内側の構造：＿＿＿＿＿＿

外側の構造：反復
内側の構造：選択

練習3　基本構造を組み合わせよう

次の処理を組み合わせて、「生きている敵をすべて描画する」アルゴリズムを作ろう。

• 敵を描画する
• すべての敵について繰り返す
• 敵が生きているか調べる
• 生きていなければ何もしない

＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
  ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
    ├─ はい　→ ＿＿＿＿＿＿＿＿＿＿＿＿
    └─ いいえ→ ＿＿＿＿＿＿＿＿＿＿＿＿
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

すべての敵について繰り返す
  敵が生きているか調べる
    ├─ はい　→ 敵を描画する
    └─ いいえ→ 何もしない
繰り返し終わり

3．複数の処理を一つのブロックとして見る

関連する複数の処理をまとめて、一つの大きな処理ブロックとして見ることができます。

例えば、次の3つの処理を考えます。

キー入力を調べる
  ↓
入力に合わせて移動方向を決める
  ↓
プレイヤーの座標を変更する

この3つをまとめて、次のような一つの処理として扱えます。

［プレイヤーを更新する］

細かく見ると複数の処理ですが、大きく見ると一つの処理です。

3-1．細かく見るか、大きく見るか

大きく見た場合

［プレイヤーを更新する］

細かく見た場合

［プレイヤーを更新する］
  ├─ キー入力を調べる
  ├─ 移動方向を決める
  └─ 座標を変更する

さらに「移動方向を決める」の中を見ると、選択が入っています。

［移動方向を決める］
  ├─ 右キーが押されている→ 右向きにする
  └─ 左キーが押されている→ 左向きにする

一つの処理ブロックの中を、さらに細かな処理ブロックへ分けて考えられます。

3-2．ブロックの中にも3つの基本構造がある

大きな処理ブロックの中も、順次・選択・反復の組み合わせで作られています。

［敵を更新する］
  └─ すべての敵について繰り返す
       ├─ 敵が生きているか調べる
       │    ├─ はい　→ 敵を移動する
       │    └─ いいえ→ 何もしない
       └─ 敵のアニメーションを進める

外から見ると「敵を更新する」という一つの処理です。しかし、中を見ると反復・選択・順次が組み合わされています。

練習4　処理を一つのブロックにまとめよう

次の処理全体に、分かりやすい名前を付けよう。

プレイヤーと敵が当たっているか調べる
  ↓
当たっていればプレイヤーの体力を減らす
  ↓
体力が0以下ならゲームオーバーにする

［＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿］

［プレイヤーのダメージ処理を行う］

練習5　大きなブロックを細かく分けよう

「ゲーム画面を描画する」という大きな処理を、3つ以上の小さな処理に分けよう。

［ゲーム画面を描画する］
  ├─ ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
  ├─ ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
  └─ ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

［ゲーム画面を描画する］
  ├─ 背景を描画する
  ├─ プレイヤーを描画する
  ├─ 敵を描画する
  └─ 得点を描画する

4．アルゴリズムを再帰的に見る

一つの処理ブロックの中を細かく見ると、そこにも複数の処理があります。

さらに、その中の処理ブロックを細かく見ると、また複数の処理があります。

ゲームを実行する
  ├─ ゲームを準備する
  │    ├─ 画面を用意する
  │    ├─ 画像を読み込む
  │    └─ 変数を初期化する
  │
  ├─ ゲームを進める
  │    ├─ 入力を調べる
  │    ├─ ゲームを更新する
  │    └─ 画面を描画する
  │
  └─ ゲームを終了する
       ├─ 画像を解放する
       └─ 画面を閉じる

このように、アルゴリズムは大きな処理から小さな処理へ、同じように分けながら考えられます。

ここでいう再帰的に見るとは、一つの処理ブロックの中を、同じ考え方でさらに細かく見ていくことです。後で学ぶ「再帰関数」とは別の話です。

4-1．内側の基本構造から順番にまとめる

複雑なフローチャートを、一度に理解しようとする必要はありません。まず、一番内側にある順次・選択・反復のいずれかを探します。

見つけた基本構造を「処理A」のような一つの処理へ置き換えると、フローチャートが少し簡単になります。次に、処理Aを含む別の基本構造を「処理B」へ置き換えます。この操作を内側から外側へ繰り返します。

図2-1〜図2-3では、複雑なフローチャートの中から基本構造を一つずつ見つけ、処理A、処理B、処理C……という一つの処理へ順番に置き換えています。

複雑な流れ図
  → 内側にある反復や選択を処理A、処理Bにする
  → 連続する処理を処理C、処理Dにする
  → 新しく見えてきた反復を処理Eにする
  → 連続する処理を処理Fにする
  → 外側の選択を処理Gにする
  → 最後に全体を処理Hとしてまとめる

このように、どれほど複雑に見えるアルゴリズムでも、基本構造を再帰的にまとめていくと、最上位では大きな処理が並ぶ順次構造へ帰着できます。

4-2．どの大きさで見るかを変える

まず大きな処理へ分け、その後で一つずつ中身を考えていきます。

練習6　階層を完成させよう

［ゲームを実行する］
  ├─ ［ゲームを準備する］
  │    ├─ 画像を読み込む
  │    └─ ＿＿＿＿＿＿＿＿＿＿＿＿
  │
  ├─ ［ゲームを進める］
  │    ├─ 入力を調べる
  │    ├─ ＿＿＿＿＿＿＿＿＿＿＿＿
  │    └─ 画面を描画する
  │
  └─ ［ゲームを終了する］
       └─ ＿＿＿＿＿＿＿＿＿＿＿＿

［ゲームを実行する］
  ├─ ［ゲームを準備する］
  │    ├─ 画像を読み込む
  │    └─ 変数を初期化する
  │
  ├─ ［ゲームを進める］
  │    ├─ 入力を調べる
  │    ├─ ゲームを更新する
  │    └─ 画面を描画する
  │
  └─ ［ゲームを終了する］
       └─ 画像を解放する

5．穴埋め問題

問題1　基本構造とブロック

1. 処理を上から順番に実行する構造を（　①　）という。
2. 条件によって実行する処理を選ぶ構造を（　②　）という。
3. 同じ処理を繰り返す構造を（　③　）という。
4. 複数の処理をまとめて、一つの大きな（　④　）として見られる。
5. アルゴリズム全体を大きく見ると、処理ブロックの（　⑤　）として捉えられる。

問題2　組み合わせを完成させよう

「すべての敵について、生きている敵だけを移動する」アルゴリズムを完成させよう。

＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
  ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
    ├─ はい　→ ＿＿＿＿＿＿＿＿＿＿＿＿
    └─ いいえ→ 何もしない
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

すべての敵について繰り返す
  敵が生きているか調べる
    ├─ はい　→ 敵を移動する
    └─ いいえ→ 何もしない
繰り返し終わり

6．総合問題

問題1　ゲームの処理を大きなブロックに分けよう

次の処理を、3つの大きな処理ブロックへ分けよう。

• ゲームで使用した画像を解放する
• プレイヤーや敵を更新する
• 画像や音を読み込む
• プレイヤーや敵を描画する
• 変数を初期化する
• キー入力を調べる

［ゲームを準備する］
  ├─ ＿＿＿＿＿＿＿＿＿＿＿＿
  └─ ＿＿＿＿＿＿＿＿＿＿＿＿

［ゲームを進める］
  ├─ ＿＿＿＿＿＿＿＿＿＿＿＿
  ├─ ＿＿＿＿＿＿＿＿＿＿＿＿
  └─ ＿＿＿＿＿＿＿＿＿＿＿＿

［ゲームを終了する］
  └─ ＿＿＿＿＿＿＿＿＿＿＿＿

次に、一番大きな単位で見た処理順を書こう。

［＿＿＿＿＿＿＿＿＿＿］
          ↓
［＿＿＿＿＿＿＿＿＿＿］
          ↓
［＿＿＿＿＿＿＿＿＿＿］

［ゲームを準備する］
  ├─ 画像や音を読み込む
  └─ 変数を初期化する

［ゲームを進める］
  ├─ キー入力を調べる
  ├─ プレイヤーや敵を更新する
  └─ プレイヤーや敵を描画する

［ゲームを終了する］
  └─ ゲームで使用した画像を解放する

［ゲームを準備する］
          ↓
［ゲームを進める］
          ↓
［ゲームを終了する］

問題2　正しい説明を選ぼう

正しいものには○、誤っているものには×を書こう。

7．まとめ

アルゴリズムを作る基本構造は、順次・選択・反復の3つです。

順次：処理を順番に実行する
選択：条件によって処理を選ぶ
反復：同じ処理を繰り返す

この3つは、互いの中に組み合わせて使えます。

また、複数の処理を一つの大きな処理ブロックとして見たり、一つの処理ブロックの中をさらに細かな処理へ分けたりできます。

アルゴリズム全体
  ↓
大きな処理ブロック
  ↓
順次・選択・反復の組み合わせ
  ↓
一つ一つの具体的な処理

細かく見ると、順次・選択・反復が組み合わされています。

大きく見ると、アルゴリズム全体は、まとまった処理ブロックを順番に実行する順次構造として捉えられます。

8．学習チェック

• 順次・選択・反復の違いを説明できる
• 3つの基本構造を組み合わせられる
• 選択の中に順次を組み込める
• 反復の中に選択を組み込める
• 複数の処理を一つの処理ブロックとしてまとめられる
• 大きな処理ブロックを細かな処理へ分けられる
• アルゴリズムを再帰的・階層的に見られる
• アルゴリズム全体を大きな処理ブロックの順次として捉えられる