分割統治 わかりやすく

半分に割る

前に、大きな仕事は小さな段階に分けると話しました。ここではもう一歩進みます。
問題のかたまりを半分に割り、その半分をまた半分に、それをまた半分に割ります。
するとかけらはどんどん小さくなります。

半分に割るを押すたびに、かたまりが半分ずつに分かれ、かけらはどんどん小さくなります。

割るたびに、扱う量は半分になります。
大きな山には途方に暮れましたが、小さなかけら一つならずっと気楽です。
辞書を半分ずつ開いて探したときと、同じ感覚です。

かけらは重ならない

ここにとても大切なことがあります。半分に割った二つのかけらは、互いに重なりません。
左の山と右の山は同じ服を分け合わないので、片方でした仕事をもう片方がくり返す必要はありません。
二つは完全に別々です。

二つのかけらを一つずつ押して照らすと、重なる部分は一つもありません。別々（独立）なので、それぞれ解いてもぶつかりません。

重ならないというこの性質は、思った以上に大切です。
かけらが重ならないので、片方の答えがもう片方の答えを台なしにしません。
重なる問題に出会うと話は変わりますが、それはまた別の道です。

小さなかけらを解く

半分に割り続けると、もうそれ以上割れない、とても小さなかけらが出てきます。
服一枚、数一つのようなものです。
そこまで小さければ、悩むまでもなくすぐ解けます。

いちばん小さなかけら（底）を一つずつ押すと、すぐ解けます。もう割れないほど小さいので、悩まずに解けて緑に変わります。

大きな問題を一度に解こうとして苦しむことはありません。
最後まで割ってから、解きやすい小さなかけらだけを一つずつ解きます。
難しい仕事一つを、やさしい仕事いくつかに変えてしまったのです。

合わせて上げる

小さな答えがそろったので、今度は逆に上がっていきます。
小さな答えを二つ合わせて少し大きな答えを作り、それをまた合わせてもっと大きな答えを作ります。
割った回数だけ合わせていくと、いちばん上に全体の答えができあがります。

合わせて上げるを押すたびに、解けたかけらが二つずつ一つに合わさります。いちばん上で全体の答えが完成します。

割るときは下へ、合わせるときは上へ。
かけらが重ならなかったので、合わせるときもすっきりしています。左の答えと右の答えを一つにまとめればよいのです。
これが半分に割って征服する方法、分割統治です。

割って、解いて、合わせる

一行にまとめるとこうなります。半分に割り、重ならないかけらをそれぞれ解き、また合わせて上げる。
カードを半分ずつに分けて並べ替えた方法はこの型そのままで、辞書を半分ずつ開いて探した方法は、探す値のない側を捨てて片方だけ解けばよい場合です。
大きなものも、割れば小さくなります。

三つの歩みを順に押して、一周たどります。半分に割る → 小さなかけらを解く → 合わせて上げる。かけらが重ならないことが肝心です。

ここでは、かけらどうしがきれいに離れていたので、一度解いたかけらをもう一度解くことはありませんでした。
でも、もしかけらが重なっていて、同じものを何度も解き直さなければならないとしたら？
次のレッスンではまず、割ることを自分でくり返す再帰を見て、その分かれ道にはそのすぐあとで出会います。