seegongsik
単語帳
アルゴリズム

サイコロを ふる ときかた

どんよくでは 目の前の さいぜんを えらびましたね。でも ある ときかたは いっそ サイコロを ふります。なにを えらぶかを むさくいに きめるのです。へんに きこえますが、これが はやくて かんたんな ときが あります。どうして うんに まかせるのが やくに 立つのでしょう?

01

サイコロで えらぶ

ある ときかたは
つぎに なにを するかを
サイコロを ふって きめます。
かんがえて えらぶのでは なく、
うんに まかせるのです。
ボタンを おすたびに
サイコロが 一かい ころがります。
どの めが でるか
まえもって わかりません。

おして ふってみる
これまでの め

おすと サイコロが ころがります。(つぎの めは わかりません)

なぜ わざと うんに まかせるの?
いつも おなじように えらぶと、
だれかが その くせを ねらって
わざと むずかしく できます。
むさくいに えらべば
そんな ねらいを さけられます。
つぎの だんかいで
ほんとうの やくだちを 見ます。

02

むさくいな きじゅんを つかう

はやい ならべかえの 中には
きじゅんを 一つ きめて、
それより 小さいのは ひだり、
大きいのは みぎに わける
やりかたが あります。
でも いつも いちばん さいごの あたいを
きじゅんに すると、
もう ならんだ にゅうりょくでは
わけが かたほうに ばかり かたよって
とても おそく なります。

いつも さいご きじゅん
むさくい きじゅん

いつも さいご きじゅん vs むさくい きじゅん、わける かいすうを くらべます。(かたより = おそい)

きじゅんを むさくいに えらべば
どんな にゅうりょくが きても
かたほうに ばかり かたよる ことが
ほとんど なくなります。
わるい にゅうりょくを ねらった
わなも きかなく なります。
だから へいきんてきに
わけが まんべんなく なって、
ならべかえが はやく なります。

03

たくさん なげて あらためる

むさくいは あらためにも つかいます。
せいほうけいの 中に
円を 一つ かきます。
その 中に てんを たくさん うちます。
円の 中に はいった てんと
ぜんぶの てんの わりあいを 見れば、
円が しめる ひろさを
あらためる ことが できます。
てんを 一つずつ うってみましょう。

円の中: 0ぜんぶ: 0わりあい: -しんち: 0.785
てんを うって わりあいを 見て

てんが ふえるほど わりあいが しんちに ちかづきます。(円の中 / ぜんぶ)

てんが すくない ときは
あらためが ばらつきます。
でも てんを たくさん うつほど
わりあいが しんちに ぴたりと つきます。
一かい 二かいの うんは しんよう できなくても、
かぞえきれない なげの へいきんは
しんよう できるからです。
これが たくさん なげて
こたえを あらためる ほうほうです。

04

かくじつさと はやさを とりかえる

むさくいな ときかたは ただでは ありません。
はやくて かんたんな かわりに、
まいかい おなじ こたえを
やくそく できません。
うんが わるいと
ときどき おそい ことも あります。
なにを えて
なにを わたすか、
りょうほうを おして くらべましょう。

りょうほうを おして くらべて

える ものと わたす ものを おして くらべます。(はやい・かんたん vs おなじ こたえ やくそくなし)

だから むさくいは
いつも よいのでは なく
ふさわしい ばしょが あります。
はやさと かんたんさが
すこしの ふかくじつより
ねうちが ある ときに つかいます。
かくじつさを すこし わたして
はやさと かんたんさを
かってくるのです。

05

ひとめで まとめる

むさくいな ときかたを
ひとめで まとめましょう。
サイコロで えらび、
むさくい きじゅんで わなを さけ、
たくさん なげて こたえを あらため、
かくじつさと はやさを とりかえる。
かなめを じゅんに おして
じぶんで まとめましょう。

かなめを じゅんに おして まとめます

かなめ 四つを じゅんに おして まとめます。(サイコロ · むさくい きじゅん · たくさん なげて あらため · とりかえ)

うんに まかせると いうと
たよりなく 見えますが、
うまく つかえば むさくいは
はやくて たよりに なる どうぐです。
これから データが ものすごく
おおく なる ところで、
たくさん なげて あらためる この かんがえは
もっと 大きく つかわれます。
その はなしは つぎに。

一言でいうとある ときかたは サイコロを ふって なにを するかを むさくいに えらびます。クイック ソートで いつも さいごの あたいを きじゅんに すると わるい にゅうりょくで おそく なりますが、きじゅんを むさくいに えらべば その わなを さけて へいきんてきに はやく なります。また せいほうけいの 中に てんを たくさん うって、円の 中に はいった わりあいを 見れば ひろさを あらためる ことが できます。たくさん なげるほど あらためが せいかくに なります。むさくいな ときかたは まいかい おなじ こたえを やくそく できませんが、その かわり はやくて かんたんです。かくじつさを すこし わたして はやさを えるのです。
アルゴリズム
このページがお役に立ったなら支援する