seegongsik
単語帳
アルゴリズム

半分に わって せいふくする

大きな せんたくものの 山を 一人で たたむのは 気が とおく なりますね。でも 半分に わけて、かた方を おとうとに まかせたら どう でしょう。二人とも へった 山だけを たたみ、さいごに 合わせれば おわりです。大きな もんだいも 同じです。半分に わって、それぞれ といて、また 合わせれば いいのです。

01

半分に わる

前に 大きな しごとは
小さな だんかいに わける と いいました。
ここでは もう 一歩 すすみます。
もんだいの かたまりを
半分に わります。
その 半分を また 半分に、
それを また 半分に。
だんだん 小さな かけらに なります。

8
一つの かたまりです。押して 半分に わって みましょう。

かたまりを 押して 半分に わります。押す ごとに 半分・半分に わかれ、だんだん 小さな かけらに なります。

わる ごとに
あつかう りょうが 半分に なります。
大きな 山は 気が とおかったのに、
小さな かけら 一つは
ずっと あつかいやすい。
まさに じしょを
半分ずつ わって さがした
あの かんじです。

02

かけらは かさならない

ここに とても 大切な ことが あります。
半分に わった 二つの かけらは
たがいに かさなりません。
ひだりの 山と みぎの 山は
おなじ ふくを 分けあいません。
だから かた方で した しごとを
もう かた方が また する ことは ありません。
二つは まったく べつべつです。

かさなり
0
二つの かけらを 一つずつ 押して てらして みましょう。

二つの かけらを 押して てらして みましょう。かさなる ところが 一つも ありません。べつべつ(どくりつ)だから、それぞれ といても ぶつかりません。

かさならない という この せいしつ、
かるく 見ないで ください。
かけらが かさならないから
かた方の こたえが もう かた方の こたえを
だめに しません。
あとで かさなる もんだいに
であうと はなしが かわります。
それは また べつの みちです。

03

小さな かけらを とく

ずっと 半分に わると
もう われない
とても 小さな かけらが でます。
ふく 一まい、
すうじ 一つ のように。
それは 小さすぎて
なやむ ことも なく
すぐに とけます。

いちばん 小さな かけらです。一つずつ 押して すぐ ときます。

いちばん 小さな かけら(そこ)を 押して すぐ とく。これ以上 われない ほど 小さいので、なやまず とけます(みどり)。

大きな もんだいを 一どに
とこうと くるしみません。
さいごまで わって、
ときやすい 小さな ものだけを
一つ一つ ときます。
むずかしい ことを
やさしい こと いくつもに
かえて しまったのです。

04

合わせて 上げる

小さな こたえが できたので
こんどは ぎゃくに のぼります。
小さな 二つの こたえを 合わせて
少し 大きな こたえを つくり、
その 二つを また 合わせて
もっと 大きな こたえを つくります。
わった ぶんだけ 合わせると
いちばん 上に ぜんたいの こたえが 立ちます。

1
1
1
1
1
1
1
1
といた 小さな かけらが 8つ。押して 二つずつ 上へ 合わせます。

といた かけらを 押して 上へ 合わせます。二つが 一つに、また 一つに。いちばん 上で ぜんたいの こたえが かんせい します。

わる ときは 下へ、
合わせる ときは 上へ。
かけらが かさならなかったので
合わせる ときも きれいです。
ひだりの こたえと みぎの こたえを
ただ ならべて つなげば いい。
これこそが
半分に わって せいふくする ことです。

05

わって、といて、合わせる

一すじに まとめると こうです。
半分に わって、
かさならない かけらを それぞれ といて、
また 合わせて 上げます。
じしょを 半分ずつ さがすのも、
カードを 半分ずつ 分けて ならべるのも
みな この 一つの わくぐみです。
大きな ものは わると 小さく なります。

さいしょの 一歩から 順に 押して 一しゅう たどります。

三あしを 順に 押して 一しゅう たどります。半分に わる → 小さな かけらを とく → 合わせて 上げる。かけらが かさならない ことが かなめでした。

ここでは かけらが
たがいに きれいに はなれて いました。
だから 一ど といた かけらを
また とく ことは ありませんでした。
でも もし かけらが
たがいに かさなって、おなじ ものを
なんども とき なおさねば ならないと したら?
つぎの かいで その わかれみちに であいます。

一言でいうと大きな もんだいは、半分に わって、それぞれ といて、また 合わせて せいふく します。かんじんなのは、わった 二つの かけらが たがいに かさならない ことです。かた方で した しごとを、もう かた方が やりなおさなくて いいから。これ以上 われない ほど 小さく なれば すぐ といて、といた かけらを 上へ 合わせれば、ぜんたいの こたえが でます。にぶん たんさくも マージソートも、みな この わくぐみです。かけらが かさならない ことが、この やり方の 力です。
アルゴリズム
このページがお役に立ったなら支援する