問題の仕様：入力、出力、手順
コードを書く前に、問題を正確に説明しよう。これを仕様という。
- 入力：どんなデータが与えられるか。種類と範囲も書く（例：「n個の整数、1 ≤ n ≤ 1000」）。
- 出力：何を返すか（例：「その中で一番大きい数」）。
- 条件：始める前に成り立っていること（事前条件）と、終わったあとに成り立っていること（事後条件）。
手順を書く
アルゴリズムとは、どんな正しい入力でも正しい出力に変える、有限で明確な手順の並びだ。次のように書ける。
- ふつうの文章：「数を1つずつ見て、今までで一番大きければ覚えておく。」
- 番号つきの手順：1. best ← 最初の数。2. 次の数 x について、x > best なら best ← x。3. best を出力する。
- 擬似コードやフローチャート：もっと正確に書きたいとき。
小さな入力で手計算して確かめよう。変わった場合（全部同じ、負の数、数が1個だけ）も試す。
トップダウン設計とボトムアップ設計
トップダウン（段階的詳細化）：作業全体から始めて、いくつかの大きな手順に分け、それぞれをさらに分けて、コードにしやすくなるまで続ける。例：「成績表を作る」→ 点数を読む → 平均を出す → 評価をつける → 印刷する。
ボトムアップ：先に、再利用できる小さな部品（最大値を探す関数、並べ替える関数）を作ってテストし、それらをつなげて全体のプログラムにする。
実際の開発では両方を混ぜる。計画はトップダウン、作ってテストするのはボトムアップだ。
分割統治法と半分にする方法
分割統治法は3つの動きでできている。問題を同じ種類の小さな部分に分ける。それぞれを（たいてい再帰で）解く。答えを合わせる。
- 二分探索（半分にする）：並んだ列で、真ん中と比べて半分を捨てる。n個なら約 log₂ n 回で済む。16個なら4回、1 000 000個なら20回。
- マージソート：列を2つに分け、それぞれを並べ替えて、合わせる。時間は O(n log n)。
- べき乗の高速化：a⁸ = ((a²)²)²。7回ではなく3回のかけ算で済む。
- 二分法で解を探す：関数の符号が変わる区間を、半分ずつにせばめる。
貪欲法
貪欲法は、そのとき一番よさそうな選択をして、あとで変えないやり方だ。
- 50、20、10、5、2、1のコインでおつりを作る：大きいコインから取る。この種類のコインなら最適になる。
- 1日でできるだけ多くの活動を選ぶ：いつも一番早く終わるものを選ぶ。最適になる。
- 分数ナップサック：1kgあたりの価値が高い物から入れる。最適になる。
でも貪欲法はいつも正しいとは限らない。コインが1、3、4のとき、6を貪欲に作ると 4 + 1 + 1（3枚）だが、3 + 3 なら2枚で済む。貪欲法を信じるには、正しいと証明するか、確実な方法と比べてテストする必要がある。
動的計画法とバックトラック
動的計画法（DP）
同じ小さな問題が何度も出てくるときは、それぞれを一度だけ解いて、答えを表に保存する。金額 a の最小枚数は best[a] = 1 + min(best[a - c])（c ≤ a となるコイン c すべてについて）で、best[0] = 0 から始める。コインが1、3、4なら best = 0, 1, 2, 1, 1, 2, 2 になる。表を小さい方から大きい方へうめるのがボトムアップ。答えをメモしながら再帰するのがトップダウン（メモ化）だ。くわしくは別の「動的計画法」の授業を見よう。
バックトラック
解を、選択を1つずつ重ねて作る。選んだものがルールに反したり、行き止まりになったら、それを取り消して次の候補を試す。迷路、数独、Nクイーン、すべての部分集合を並べる問題などに使う。かしこい力まかせ法で、うまくいかない枝をまるごと飛ばせる。
力まかせ法
考えられる答えをすべて試す。いつも正しいが、遅すぎることが多い（部分集合は2ⁿ個、並べ方は n! 通り）。
手法の選び方：正しさ、効率、データ構造
| 手法 | 使うとき | 例 | ふつうの時間 |
|---|---|---|---|
| 力まかせ法 | 入力がとても小さい | 3けたの暗証番号を全部試す | 2ⁿ や n! が多い |
| 分割統治法 | 部分どうしが独立している | 二分探索、マージソート | O(log n)、O(n log n) |
| 貪欲法 | その場の最良の選択が安全だと証明できる | 活動選択、おつり | O(n log n) |
| 動的計画法 | 小さな問題がくり返し出る | コイン問題、最短経路 | 表の大きさ |
| バックトラック | ルールつきの探索 | 迷路、数独 | 指数的。ただし枝を切る |
理由を説明する
正しさ：アルゴリズムが必ず止まり、正しい出力を出すことを示す（ループ不変条件、証明、変わった場合のテスト）。効率：n が大きくなるときの手順の数を数え（ビッグオー）、ほかの方法と比べる。
データ構造が助けてくれる
配列は表に（DP）、スタックはバックトラックに（戻る場所を覚える）、キューは1段ずつの探索に使う。二分木は、各ノードの子が最大2つになるようにデータをしまう。二分探索木では、小さいキーは左、大きいキーは右に置くので、探すたびに1段ごとに仕事が半分になる。二分探索と同じ考え方だ。
やってみよう：コインと数当てゲーム
- 友だちと1から100までの数当てゲームをしよう。いつも真ん中について聞く。7回の質問でいつも勝てるかな？（2⁷ = 128。）
- コインが1、3、4のとき、金額0から10までのDP表を紙に書こう。貪欲法はどこで失敗する？
- 3Dの最後のステップを開こう。コイン1、7、10で金額14を試す。貪欲法は 10 + 1 + 1 + 1 + 1、DPは 7 + 7 になる。
- 「リストの中で一番小さい数を探す」手順を書いて、5、5、5 の場合と、数が1個だけの場合でテストしよう。
重要な公式と用語
- 仕様 = 入力 + 出力 + 条件
- 半分にする方法：約 log₂ n 回（16 → 4、1024 → 10）
- コインDP：best[0] = 0; best[a] = 1 + min best[a - c]
- 分割統治 = 分ける + 解く + 合わせる
- 貪欲法は速いが、最適だと証明が必要
例題
1. n個の数の中で一番大きい数を探す問題の仕様と手順を書こう。
入力：n ≥ 1 個の数。出力：一番大きい数。手順：1. best ← 最初の数。2. ほかの各数 x について、x > best なら best ← x。3. best を出力する。4, 9, 2, 7, 12, 5, 10, 3 なら、7回の比較で 12 が出力される。
2. 1から1000までの数を見つけるのに、半分にする方法で何回質問が必要？
質問のたびに範囲が半分になる：1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1。つまり10回（2¹⁰ = 1024 ≥ 1000）。
3. 50、20、10、5、2、1のコインで、87を貪欲法で払おう。
50（残り37）、20（17）、10（7）、5（2）、2（0）：50 + 20 + 10 + 5 + 2 = 5枚。
4. コイン1、3、4で、金額7までのDP表をうめよう。
best[0]=0、[1]=1、[2]=2、[3]=1、[4]=1、[5]=min(best4, best2, best1)+1=2、[6]=min(best5, best3, best2)+1=2、[7]=min(best6, best4, best3)+1=2（3 + 4）。
5. 活動（開始-終了）：A 9-11、B 10-12、C 11-13、D 12-14、E 13-15。重ならないように、できるだけ多く選ぼう。
終わるのが一番早いものを選ぶ貪欲法：A（11に終了）、次に C（11に開始、13に終了）、次に E（13に開始）。3つの活動：A、C、E。
6. クラスの平均点と最高得点の生徒を知らせるプログラムを、トップダウンで計画しよう。
レベル1：データを読む → 計算する → 印刷する。レベル2：名前と点数をリストに読みこむ。合計と平均を計算する。最高点とその名前を探す。両方を印刷する。そのあと各部分をコードにして、ボトムアップでテストする。
よくある間違い
- 入力と出力を決める前にコードを書き始める。多くの「バグ」は、実は仕様があいまいなだけ。
- 貪欲法がいつも最適だと思いこむ。証明できるときだけ使える（コイン1、3、4で失敗する）。
- 並んでいないリストで二分探索を使う。半分にするには、整列したデータが必要。
- DPと分割統治法を混同する。DPは重なる小問題を保存して使う。分割統治法は独立した部分に分ける。