# Divide and Conquer
## 困難は分割せよ
[方法序説 (岩波文庫 青 613-1) \| デカルト,R., 谷川 多佳子 \|本 \| 通販 \| Amazon](https://amzn.to/49FnUuX)
[ルネ・デカルト - Wikiquote](https://ja.wikiquote.org/wiki/ルネ・デカルト)
👉 [[困難は分割せよ]]
## 分割統治法
[分割統治法 - Wikipedia](https://ja.wikipedia.org/wiki/分割統治法)
**分割統治法**（ぶんかつとうちほう、[英](https://ja.wikipedia.org/wiki/%E8%8B%B1%E8%AA%9E "英語"): divide-and-conquer method）は、そのままでは解決できない大きな問題を小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決する、という[問題解決](https://ja.wikipedia.org/wiki/%E5%95%8F%E9%A1%8C%E8%A7%A3%E6%B1%BA "問題解決")の手法である。
## 擬似コード
分割統治法を擬似コードによって表現すると、以下のような[再帰](https://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0 "再帰")呼出しを使ったものとなる。また、分割統治法になっている何らかの[アルゴリズム](https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0 "アルゴリズム")を実装すると、その基本的な骨組みがこのようになる。
```
function conquer(x) is
if xは簡単にconquerできる then
return conquerの結果
else
(x1, x2, ...) := divide(x) // 複数の小さな副問題に分割
(y1, y2, ...) := (conquer(x1), conquer(x2), ...) // 再帰
return synthesize(y1, y2, ...) // 各副問題の解を合成（最大値を選ぶ、等）
```
## マージソート
[マージソート - Wikipedia](https://ja.wikipedia.org/wiki/マージソート)
**マージソート**は、[ソート](https://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88 "ソート")の[アルゴリズム](https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0 "アルゴリズム")で、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの[分割統治法](https://ja.wikipedia.org/wiki/%E5%88%86%E5%89%B2%E7%B5%B1%E6%B2%BB%E6%B3%95 "分割統治法")による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は[並列化](https://ja.wikipedia.org/wiki/%E4%B8%A6%E5%88%97%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%83%86%E3%82%A3%E3%83%B3%E3%82%B0 "並列コンピューティング")できる。
![[Merge-sort-example-300px.gif|Merge-sort-example-300px.gif 300×180 pixels]]
## 参考
[分割統治（Divide and Conquer）について | Ouobpo](https://ameblo.jp/ouobpo/entry-10052917344.html)
> 私の理解では、分割統治の考え方をプログラミングの世界に持ち込んだのは、かの有名なエドガー・ダイクストラ（構造化プログラミングの生みの親）だ。
> 古代ローマにおける分割統治とは、広大なローマ帝国を築き上げるために支配下の都市に対して行った政策のことだ。分割統治はまた、大航海時代の15世紀から20世紀にかけて、ヨーロッパ列強が植民地を支配するための基本的な戦略としても用いられた。
[デカルトは「困難を分割せよ」と言い、ビル・ゲイツは「問題を切り分けろ」と言った | ハフポスト NEWS](https://www.huffingtonpost.jp/satoshi-nakajima/difficulity_b_10325526.html)
