アルゴリズム設計と問題解決

プログラム開発ライフサイクルとは、プログラムを作成するために用いられる一連の工程のことである。4つの工程がある。

分析

分析では問題を理解する。2つの重要なスキルが役立つ：

• 抽象化 — 重要な詳細のみを残し、他は無視する；
• 分解 — 大きな問題をより小さく扱いやすい部分に分割する。

設計

設計では、しばしば分解を用いて解決策を計画する。構造図（システムを小さなボックスに分割するチャート）において、サブシステムとして各部品を表すことができる。

コーディングとテスト

コーディングではプログラムコードを書く。反復テストを用いる—構築しながら小さな部分を繰り返しテストする。テストでは、テストデータを用いて全体プログラムを実行し、正しく動作するかを確認する。

解決策を計画する方法には3つの主要な方法がある。

• 構造図 — システムの部品とそれらがどう組み合わさるかを示す；
• フローチャート — ボックスと矢印を用いて順序立てて手順を示す図；
• 擬似コード — コードのような単純な英語で記述された手順（本物の言語ではない）。

アルゴリズムとは、正しい順序で並んだ問題解決の一連の手順である。すべてのアルゴリズムは3つの部分に分割できる：

• 入力 — 入力されるデータ；
• 処理 — データに対する作業；
• 出力 — 出力される結果。

これを「入力、処理、出力への分解」と呼ぶ。例えば「3つの得点の平均を求める」場合：入力は3つの得点、処理は足して3で割り算すること、出力は平均である。

データが入力された際、ミスを減らすために内容を確認する。

検証（Validation）は、データが合理的であり、ルールに従っているかを確認します。データが真実かどうかをチェックすることはできませんが、許容範囲内であるかどうかは確認できます。

照合（Verification）は、データが正確にコピーまたは入力されたか（入力中に誤りがなかったか）を確認します。2つの方法があります：

• 視覚的照合（visual check） — 人が入力したデータを元データと比較する；
• 二重入力（double entry） — データを2回入力し、両方のコピーを比較する。

トレース表は、アルゴリズムを実行する際、ステップごとに各変数の値を記録するものです。これにより以下が行えます：

• アルゴリズムが正しく動作しているかを確認する；
• 与えられたデータを使ってアルゴリズムを追跡することで、アルゴリズムが何を処理するかを把握する。

例：入力値5对于这个アルゴリズムをトレースしてください。

INPUT N
Total ← 0
FOR I ← 1 TO N
    Total ← Total + I
NEXT I
OUTPUT Total

このトレースから、アルゴリズムは1からnまでの和を計算していることがわかります。入力が5の場合、出力は15です。

** worked example.** このアルゴリズムをトレースして、出力を与えてください。

X ← 20
Count ← 0
WHILE X > 1
    X ← DIV(X, 2)
    Count ← Count + 1
ENDWHILE
OUTPUT Count

DIV は除算の整数部分のみを返します。各パスにつき1行ずつ書きます：x は10（カウント1）、次に5（カウント2）、次に2（カウント3）、次に1（カウント4）となります。ここで x > 1 が false となるためループは停止し、出力は 4 となります。これらの得点を確保するための習慣として、パスの後に条件をチェックするのではなく、各パスの前に条件をチェックすること、そしてすべてのパスに対して新しい行を書くことが挙げられます。値を頭の中で記憶しようとすると、トレースが間違える原因になります。

テストデータとは、プログラムを検証するために使用するデータのことです。知っておくべき4つのタイプがあります。

これらの一般的なアルゴリズムを知っている必要があります。

線形探索

線形探索 は、先頭から開始して各項目をターゲットと比較する。値が見つかるかリストの終わりまで達するまで停止する。リストはソートされている必要はない。以下の例では位置1から4を使用する。

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, SearchValue : INTEGER
DECLARE Found : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
INPUT SearchValue
Found ← FALSE
I ← 1
WHILE I <= 4 AND NOT Found
    IF List[I] = SearchValue
      THEN
        Found ← TRUE
    ENDIF
    I ← I + 1
ENDWHILE
OUTPUT Found

解答例の比較。 5 を検索する場合、8、3、5 を順に比較します：3回の比較を行い、Found が TRUE になります。4番目の項目はチェックされません。9 を検索する場合、4つの値すべてを比較します；Found は FALSE のままです。配列の外側にある位置 5 を読み込もうとする前に停止してください。

バブルソート

バブルソートはリストを整列させます。隣り合う値を比較し、左の値が大きい場合に交換します。通常、一度のパスでは不十分です。この完全なバージョンは、あるパスで交換が行われないまでパスを繰り返します。

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Temp : INTEGER
DECLARE Swapped : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
REPEAT
    Swapped ← FALSE
    FOR I ← 1 TO 3
        IF List[I] > List[I + 1]
          THEN
            Temp ← List[I]
            List[I] ← List[I + 1]
            List[I + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT I
UNTIL NOT Swapped
OUTPUT List[1], ", ", List[2], ", ", List[3], ", ", List[4]

解答例のパス。 8, 3, 5, 1 から始めます。1回目のパスでリストは 3, 8, 5, 1 に、次は 3, 5, 8, 1 に、さらに 3, 5, 1, 8 になります。これにより最大値が最後になりますが、残りは未ソートのままです。2回目のパスは 3, 1, 5, 8 で終わり、3回目のパスは 1, 3, 5, 8 で終わります。4回目のパスでは交换が行われず、このバージョンで停止できることが確認されます。各パスの開始時に Swapped を FALSE にリセットし、交换发生时に TRUE に設定します。

合計とカウント

総和計算は必要な値をすべて合計に加算します：Total ← Total + Value。カウントは必要なアイテムごとに 1 を加算します：Count ← Count + 1。値を処理する前に両方をゼロに初期化します。

** worked example.** 4つの試行入力は −20, 4, 50, 6 です。値が −20 より大きく、かつ 50 より小さい場合にのみ受け入れます。この例では4つの試行を処理しますが、4つの受け入れ値ではありません。

DECLARE I, Count : INTEGER
DECLARE Value, Total : REAL
Total ← 0
Count ← 0
FOR I ← 1 TO 4
    INPUT Value
    IF Value > -20 AND Value < 50
      THEN
        Total ← Total + Value
        Count ← Count + 1
    ENDIF
NEXT I
IF Count > 0
  THEN
    OUTPUT Total, ", ", Count, ", ", Total / Count
  ELSE
    OUTPUT "No accepted values"
ENDIF

厳密な境界値は −20 と 50 を除外します。両方の更新は受け入れテスト内にあるため、除外された試行は合計やカウントを変えません。受け入れ値の平均は以下の通りです：

4で割らないでください：追加されたのは2つの値だけです。どの値も受け入れられない場合、カウントはゼロであり、平均を計算することはできません；代わりにゼロ除算を避けるメッセージを出力します。

** 固定数の受け入れ値への転送。** タスクが 50 個の受け入れ値を求める場合、4の試行ではなく、固定の FOR ループを WHILE Count < 50 に置き、ENDWHILE で閉じます。内部には同じ入力と受け入れテストを保持します。除外された入力は Count を変化させないため、次の入力が求められます。完了時、Count は 50 ですが、試行数はそれ以上である可能性があります。合計を出力し、平均を Total / Count として計算します。

最大値、最小値、平均値

最大値は最大の値、最小値は最小の値です。平均は合計を値の数で割ったものです。非空リストの場合、最初の要素から両方を初期化します。残りの各要素について、新しい値が大きい場合は最大値を更新し、小さい場合は最小値を更新します。

** worked example.** リストは −8, −3, −12, −5 です。最大値をゼロから始めると失敗します：リストの要素はいずれもゼロより大きくないため、アルゴリズムはリストに含まれない数を出力します。−8 から始めれば、データが正であるという仮定なしに機能します。

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Maximum, Minimum, Total : INTEGER
List[1] ← -8
List[2] ← -3
List[3] ← -12
List[4] ← -5
Maximum ← List[1]
Minimum ← List[1]
Total ← List[1]
FOR I ← 2 TO 4
    IF List[I] > Maximum
      THEN
        Maximum ← List[I]
    ENDIF
    IF List[I] < Minimum
      THEN
        Minimum ← List[I]
    ENDIF
    Total ← Total + List[I]
NEXT I
OUTPUT Maximum, ", ", Minimum, ", ", Total / 4

最大値は −3、最小値は −12 です。平均はすべての4つの値を使用します：

平均は最小値と最大値の間にあります；これは計算が正しいことの証明ではなく、有用なチェックです。最初の要素から初期化するには、非空リストが必要です。その要素を読む前に、空のリストは別扱いしてください。

• 4つのライフサイクル段階：分析 → 設計 → コーディング → テスト。抽象化は重要な要素のみを残し、分解は問題を部分に分割します。
• **検証（Validation）**はデータが合理的か（範囲、長さ、型、存在、フォーマットのチェック）を確認し、**照合（verification）**は正確にコピーされたか（視覚的照合または二重入力）を確認します。
• 4つのテストデータタイプを覚えます：通常（受け入れられる）、異常（拒否される）、極端（最大/最小でも許容される値）、境界（制限値の両側）。
• トレース表（各ステップにおける各変数の値）は、アルゴリズムが何を行うかを示す。
• 標準アルゴリズムを知っています：線形探索（各項目を順に確認）とバブルソート（交換が必要なくなるまで隣り合うペアを交换）。