Return to Video

プログラマーのように考える 第６話「谷間」

  • 0:22 - 0:27
    エシック、ヘッジ、オクタヴィアは
    底なしの谷の縁に立っています
  • 0:27 - 0:29
    塔と彼らを隔てる
    この谷さえ渡れば
  • 0:29 - 0:33
    ３つの強力なアイテムの
    ２つめが手に入るのです
  • 0:33 - 0:38
    警備ロボットが戻ってくるまでの
    短い時間に渡らなければなりません
  • 0:38 - 0:43
    ヘッジが燃料切れで
    エシックを連れて飛べないので
  • 0:43 - 0:46
    橋を作るしかありません
  • 0:46 - 0:51
    幸い 橋の部品となるブロックの山が
    近くに浮かんでいます
  • 0:51 - 0:55
    オクタヴィアが発明した
    浮遊ブロックです
  • 0:55 - 0:57
    エネルギーをかけて
    ブロックの山を起動させれば
  • 0:57 - 1:02
    エシックが歩いて渡れる橋が
    自動的に組み上がります
  • 1:02 - 1:06
    もちろん 問題もあります
  • 1:06 - 1:10
    浮遊ブロックが安定するのは
    完全な回文構造の時だけなのです
  • 1:10 - 1:14
    つまり 前から見ても
    後ろから見ても
  • 1:14 - 1:17
    並び順が同じでなければなりません
  • 1:17 - 1:19
    ブロックは最初ランダムに
    積み重なっていても
  • 1:19 - 1:24
    可能な限り
    回文構造を作ろうとします
  • 1:24 - 1:27
    回文構造が作れないときには
  • 1:27 - 1:28
    橋は崩れてしまい
  • 1:28 - 1:32
    上にいる人は
    谷底に落ちることになります
  • 1:32 - 1:33
    例を見てみましょう
  • 1:33 - 1:36
    このブロックの山は
    安定した構造を作れます
  • 1:36 - 1:39
    まずＡが両端につきます
  • 1:39 - 1:40
    それからＢがきて
  • 1:40 - 1:44
    最後にＣが
    Ｂの間に入ります
  • 1:44 - 1:47
    でもＡが
    もう１つあったとしたら？
  • 1:47 - 1:50
    まずはＡが２個
    次にＢが２個 入りますが
  • 1:50 - 1:54
    残ったＣとＡには
    行き場がないので
  • 1:54 - 1:56
    全体が崩れてしまいます
  • 1:56 - 2:01
    力の石を使ってヘッジは
    ブロックの山を１つだけ起動できます
  • 2:01 - 2:03
    エシックがどんな指示を
    ヘッジに与えれば
  • 2:03 - 2:08
    回文構造を作れる山を効率的に見つけ
    起動させられるでしょうか？
  • 2:08 - 2:18
    ［ビデオをいったん止めて
    自分で考えてみましょう］
  • 2:18 - 2:24
    回文の例としては ANNAや RACECARや
    MADAM IM ADAMなどがあります
  • 2:24 - 2:27
    回文の中に各文字が
    何度現れるかを数えると
  • 2:27 - 2:30
    役に立つ規則性が
    見えてくるでしょう
  • 2:30 - 2:35
    ［ビデオをいったん止めて
    自分で考えてみましょう］
  • 2:35 - 2:38
    まずは 素朴な解決法を
    考えてみましょう
  • 2:38 - 2:43
    素朴な方法とは 最適化されていない
    単純なしらみつぶしのやり方ですが
  • 2:43 - 2:45
    目的は果たせるような
    もののことです
  • 2:45 - 2:48
    素朴な方法は
    問題を分析する役に立ち
  • 2:48 - 2:52
    よりよい解決法を見つける
    糸口になります
  • 2:52 - 2:55
    この場合 素朴な方法は
    ブロックの山ごとに
  • 2:55 - 2:57
    すべての並び順を試し
  • 2:57 - 3:02
    前からも 後ろからも読んで
    回文構造か確かめるというものです
  • 3:02 - 3:03
    この方法の問題は
  • 3:03 - 3:06
    とても長い時間がかかることです
  • 3:06 - 3:09
    ヘッジが１つの並びを試すのに
    １秒かかるとすると
  • 3:09 - 3:14
    異なる10個のブロックからなる山を
    １つ調べるのに42日間もかかります
  • 3:14 - 3:18
    なぜなら かかる時間は
    ブロックの個数の
  • 3:18 - 3:20
    階乗に等しくなるからです
  • 3:20 - 3:23
    ブロックが10個なら
    ３百万以上の並び順があります
  • 3:23 - 3:27
    この素朴な方法から分かるのは
    もっと速い方法で
  • 3:27 - 3:31
    ブロックの山が回文構造になるか
    見分ける必要があるということです
  • 3:31 - 3:34
    まず 直観的に分かるのは
  • 3:34 - 3:37
    「ブロックが全部違っていたら不可」
    ということです
  • 3:37 - 3:43
    なぜなら 重複しているブロックがなければ
    両端のブロックが同じになり得ないからです
  • 3:43 - 3:49
    では 回文構造になり得るのは
    どのような場合なのでしょう？
  • 3:49 - 3:53
    いくつかの回文を分析することで
    答えを見つけることができます
  • 3:53 - 3:56
    ANNA には Ａが２個
    Ｎが２個あります
  • 3:56 - 4:01
    RACECAR には Ｒが２個
    Ａが２個、Ｃが２個、Ｅが１個
  • 4:01 - 4:08
    MADAM IM ADAM には Ｍが４個
    Ａが４個、Ｄが２個、Ｉが１個です
  • 4:08 - 4:09
    ここで見られるパターンは
  • 4:09 - 4:13
    ほとんどの文字が偶数回
    現れているということです
  • 4:13 - 4:16
    そして１回しか現れない文字は
    あっても１つだけです
  • 4:16 - 4:17
    それだけでしょうか？
  • 4:17 - 4:20
    RACECAR にＥが１個でなく
    ３個あったとしたら？
  • 4:20 - 4:24
    増えたＥを両端につければ
    また回文構造になるので
  • 4:24 - 4:26
    ３回現れてもOKです
  • 4:26 - 4:32
    でも Ｅが３個で Ｃも３個なら
    最後のＣの行き場がなくなります
  • 4:32 - 4:35
    ですから 一般化した考え方は
  • 4:35 - 4:39
    奇数回現れる文字は
    多くて１個で
  • 4:39 - 4:42
    残りの文字はすべて偶数回現れる
    ということです
  • 4:42 - 4:46
    ヘッジはブロックの山ごとに
    文字の出現回数を数えて辞書の形に整理でき
  • 4:46 - 4:49
    これは上手い情報格納法です
  • 4:49 - 4:54
    ここでループを使って
    奇数が何度現れるかを数えます
  • 4:54 - 4:59
    奇数回現れる文字が２個未満であれば
    そのブロックの山は回文構造にできます
  • 4:59 - 5:03
    このやり方は 素朴な方法よりも
    ずっと速く実行でき
  • 5:03 - 5:06
    文字数の階乗時間ではなく
    線形時間しか かかりません
  • 5:06 - 5:09
    つまり ブロックの数に
    比例した時間しか
  • 5:09 - 5:11
    かからないということです
  • 5:11 - 5:13
    ヘッジがそれぞれの山を分析して
  • 5:13 - 5:17
    回文になるものを見つけ次第
    やめるようなループを書いたら
  • 5:17 - 5:19
    準備は万端です
  • 5:19 - 5:20
    さて どうなるでしょう
  • 5:20 - 5:24
    ヘッジは素早いものの
    山がたくさんあって手間取り
  • 5:24 - 5:26
    時間がかかりすぎました
  • 6:18 - 6:20
    エシックとヘッジは無事でしたが
  • 6:20 - 6:22
    オクタヴィアは
    運が悪かったようです
Title:
プログラマーのように考える 第６話「谷間」
Speaker:
アレックス・ローゼンタール
Description:

アニメシリーズ『プログラマーのように考える』の第６話。全10話から成るこのシリーズは、エシックという女の子とロボットの相棒ヘッジが世界を救うために頑張るお話です。２人は３つのアイテムを集める冒険に出発しますが、その途中プログラミングのパズルを解きながら進まなければなりません。

講師：アレックス・ローゼンタール 監督：Kozmonot Animation Studio
＊このビデオの教材：https://ed.ted.com/lessons/the-chasm-think-like-a-coder-ep-6
more » « less
Video Language:
English
Team:
closed TED
Project:
TED-Ed
Duration:
06:24

Japanese subtitles

Revisions Compare revisions

Our website uses cookies for analysis purposes.