回 8-5 分野 8 考え方
分割統治法は、大きな問題を同じ形の小さな問題に分け、小さい問題の答えを組み合わせて元の答えを作る方法です。1 段か 2 段ずつ上る階段の上り方は、n 段の通り数 = (n − 1) 段の通り数 + (n − 2) 段の通り数 と小さい答えで書け、10 段で 89 通りです。分けた小問題が重なるときは、答えを覚えておく (メモ化、動的計画法) と速くなります。
大きな問題を、同じ形の小さい問題の答えで書く式を作り、ループと再帰で回数を数えて確かめます。
文 ゆめさくコード編集部公開 2026年10月30日更新 2026年10月30日出典を確かめた日 2026年10月30日
10 段の階段を、1 段か 2 段ずつ上る方法は何通りか
答えは 89 通りです。全部の上り方を並べなくても、小さい段数の答えから順に出せます。
10 段目に立つ直前の 1 歩は、9 段目から 1 段上ったか、8 段目から 2 段上ったかのどちらかです。だから「10 段の通り数 = 9 段の通り数 + 8 段の通り数」です。9 段も 8 段も、同じ形でさらに小さい段に分けられます。
大きな問題を、同じ形の小さな問題に分けて、その答えから元の答えを作る考え方を、この回では小問題に分けると呼びます。アルゴリズムでは、分けて解いて組み合わせる方法を分割統治法と呼びます。分割統治はもとは政治の言葉 (支配する相手を分けて治める) ですが、ここでは問題の解き方の名前として使います。
小問題に分ける 2 つの形
形 1、1 つ小さい答えから作る
階段の上り方の数を f(n) と書きます。最後の 1 歩で場合を分けると、次の式になります。
f(n) = f(n − 1) + f(n − 2)、f(0) = 1、f(1) = 1
f(0) = 1 は「0 段は、上らないという 1 通り」と決めた値です。小さい方から表にすると、次の通りです。
| n | f(n) | 作り方 |
|---|
| 0 | 1 | 決めた値 |
|---|
| 1 | 1 | 決めた値 |
|---|
| 2 | 2 | 1 + 1 |
|---|
| 3 | 3 | 2 + 1 |
|---|
| 4 | 5 | 3 + 2 |
|---|
| 5 | 8 | 5 + 3 |
|---|
| 6 | 13 | 8 + 5 |
|---|
| 7 | 21 | 13 + 8 |
|---|
| 8 | 34 | 21 + 13 |
|---|
| 9 | 55 | 34 + 21 |
|---|
| 10 | 89 | 55 + 34 |
|---|
前の答えを使って次の答えを書く式を漸化式と呼びます。小さい答えを表に覚えながら大きい答えへ進む方法は、動的計画法 (CS 2-9) です。
形 2、半分に分けて組み合わせる
並べ替え (ソート) のマージソートは、列を半分に分け、それぞれを並べ替えてから、2 つの並んだ列を合わせます。半分の列も同じ形でさらに半分に分け、1 個になったら並べ替え済みとして止めます。
| 段 | やること | 1 段の比べる回数 |
|---|
| 分ける | 長さ n を n/2 と n/2 に分ける | 0 |
|---|
| 解く | 半分ずつを同じ方法で並べ替える | (下の段で数える) |
|---|
| 合わせる | 先頭どうしを比べて小さい方を取る | 多くて n − 1 回 |
|---|
半分にする段は約 log2 n 段あり、どの段でも合わせる手間は合計で約 n なので、全体で約 n × log2 n 回です。2 つずつ全部比べるやり方の約 n²/2 回より、n が大きいほど速くなります。
2 つの形の違い
マージソートで分けた左半分と右半分は、別の数の列なので、同じ小問題は 2 度出てきません。階段の f(10) は、f(9) と f(8) に分け、f(9) はまた f(8) と f(7) に分けるので、f(8) が 2 度出てきます。
| 小問題が重ならない | 小問題が重なる |
|---|
| 例 | マージソート、二分探索 | 階段の上り方、フィボナッチ数 |
|---|
| 速くするには | 分け方と合わせ方を工夫する | 解いた答えを覚えて使い回す (メモ化) |
|---|
| よく呼ばれる名前 | 分割統治法 | 動的計画法 |
|---|
分けるときに決めること
小問題に分けて解くときは、次の 3 つを決めます。
- どう分けるか (最後の 1 歩で分ける、半分に分ける)
- いちばん小さい問題の答え (f(0) = 1、長さ 1 の列はそのまま)
- 小さい答えから大きい答えを作る式 (足す、合わせる)
いちばん小さい問題の答えを決め忘れると、再帰は止まりません。
動かして確かめる
1 本目は、階段の上り方を、小さい段から順にループで出します。全部の上り方を並べて数えた数とも比べます。
動かす 階段の上り方を小さい方から
実行すると、次の通りに出ます
1 段 1 1
2 段 2 2
3 段 3 3
10 段 89 89
式で出した数と、1 段と 2 段の並びを全部作って数えた数が一致しました。10 段で 89 通りです。
2 本目は、同じ式を再帰でそのまま書いたときと、答えを覚えておく (メモ化) ときで、関数が呼ばれる回数を比べます。lru_cache は、同じ引数の答えを覚えて、2 回目からは計算せずに返す仕組みです。
動かす 呼ばれる回数を比べる
実行すると、次の通りに出ます
10 段 89 呼び出し 177
20 段 10946 呼び出し 21891
30 段 1346269 呼び出し 2692537
メモ化 1346269 計算 31
そのまま再帰で書くと、30 段で約 270 万回呼ばれます。同じ小問題を何度も解き直すからです。メモ化すると、新しく計算するのは f(0) から f(30) の 31 回だけです。
3 本目は、マージソートで比べる回数を数え、n × log2 n と比べます。乱数の種を決めて、同じ列で試します。
動かす マージソートの比べる回数
実行すると、次の通りに出ます
8 True
15 24 28
1024 True
8915 10240 523776
65536 True
965830 1048576 2147450880
2 行目の 3 つの数は、マージソートで比べた回数、n × log2 n、全部の 2 つの組の数です。マージソートは n × log2 n より少し少ない回数で並べ終えました。65536 個では、全部の組の約 21 億に対して、比べたのは約 97 万回です。
小問題に分けると外れる所
重なる小問題をそのまま再帰で解く
2 本目の通り、重なる小問題を覚えずに再帰で解くと、呼び出しは段数が 1 増えるごとに約 1.6 倍に増えます。n = 50 なら 400 億回を超え、現実的な時間では終わりません。式が正しくても、同じ答えを何度も作っていないかを見ます。
再帰が深すぎて止まる
Python は、再帰の深さに上限を設けています。上限は sys.getrecursionlimit() で見られ、手元の Python 3 では 1000 でした。メモ化した再帰でも、f(5000) をいきなり呼ぶと、深さが上限を超えて RecursionError になります。
動かす 再帰の深さの上限
実行すると、次の通りに出ます
上限 1000
RecursionError
ループなら桁数 1045
深い問題は、1 本目のように小さい方からループで表を埋めると、深さの上限に当たりません。
分けても速くならない分け方
マージソートが速いのは、半分ずつに分けて段の数を log2 n に抑えたからです。毎回 1 個と残り全部に分けると、段の数が n になり、手間は約 n²/2 に戻ります。分けた小問題の大きさが、どれだけ速く小さくなるかを見ます。
仕事とコンテストでどう使うか
小問題に分ける考えが効く場面は、次の通りです。
- ソートと探索。マージソートは半分に分けて合わせ、二分探索は半分に分けて片方を捨てる
- 動的計画法。料金の最小、通り数、最長の共通部分のように、小さい答えから大きい答えを作れる問題。コーディングテストの定番
- 木の処理。フォルダの容量の合計は、子フォルダの容量の合計から作れる。木構造は、同じ形の小さな木の集まり
- 大きな仕事の分担。大きなデータを分けて別々の機械で処理し、結果を合わせる考え方も同じ形
- 累乗の計算。a^n を a^(n/2) の 2 乗で作ると、掛け算の回数は約 log2 n 回になる (3-2 の繰り返し二乗法)
よくある問い
分割統治法とは何ですか
大きな問題を同じ形の小さな問題に分け、それぞれを解いて答えを組み合わせる方法です。マージソートと二分探索が代表的な例です。分割統治という言葉は、もとは「分けて治める」という政治の言葉です。
分割統治法と動的計画法の違いは何ですか
どちらも小問題に分けて解きます。分けた小問題が重ならないとき (マージソート) は分割統治法と呼び、同じ小問題が何度も出てくるとき (階段の上り方) は、答えを覚えて使い回す動的計画法が効きます。
再帰とループのどちらで書けばよいですか
式をそのまま書くなら再帰が読みやすいです。深さが数千を超える問題や、重なる小問題が多い問題は、小さい方から表を埋めるループで書くと、深さの上限に当たらず、同じ計算もしません。
分割統治法の計算量はどう見積もりますか
何段に分かれるかと、1 段の手間の合計を掛けます。半分ずつに分けると段は約 log2 n 段で、マージソートは 1 段の合わせる手間が約 n なので、約 n × log2 n です。
確認クイズ
答えだと思う選択肢を押すと、その場で正誤と理由が開きます。3 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。
1 問目
1 段、2 段、3 段のどれかずつ上るとき、n 段の上り方の数 g(n) を小さい答えで書いた式はどれですか。
2 問目
マージソートで約 100 万個の数を並べ替えるとき、比べる回数のおよその数はどれですか。
3 問目
f(n) = f(n − 1) + f(n − 2) をメモ化せずに再帰で書くと遅くなります。主な理由はどれですか。
説明課題
「10 段の階段を 1 段か 2 段ずつ上る通り数を、全部並べずに出す方法」を、小問題、いちばん小さい答え、式の言葉を使って 3 文で説明してください。書いたら、下の模範解答を開いて比べてください。
模範解答
自分の説明を書いてから開いて、比べてください。
10 段目に立つ直前の 1 歩は、9 段目からの 1 段か 8 段目からの 2 段なので、10 段の通り数は 9 段と 8 段の通り数の和という小問題に分けられる。いちばん小さい答えを、0 段は 1 通り、1 段は 1 通りと決める。そこから f(n) = f(n − 1) + f(n − 2) で小さい方から順に表を埋めると、10 段は 89 通りと出る。
「この問題は、1 つ小さい同じ問題の答えから作れないか」と問えるようになると、再帰、動的計画法、ソートの仕組みが同じ考えでつながります。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。
もっと深く
この回の続きを、ゆめさくのコースの章や道具で深められます。頁の中の確認クイズに答えたあと、手を動かす量を増やしたいときに使ってください。
一次資料
どれも 2026年10月30日に開いて、題と中身を確かめました。
