Return to Video

04-43 Writing Reductions Solution

  • 0:00 - 0:02
    1つのやり方を見ていきましょう
  • 0:02 - 0:08
    これはx->ab・ from jです
  • 0:08 - 0:13
    その元となるchart[j]に戻って見てみると
  • 0:13 - 0:19
    y->… ・ x …のような
    書き換え規則があるはずです
  • 0:19 - 0:21
    このxが重要な部分です
  • 0:21 - 0:27
    x->abを還元するのですから
    xを探す必要があります
  • 0:27 - 0:30
    xがあれば還元の1つとして使えます
  • 0:30 - 0:35
    もう一度Pythonのリスト内包表記という
    驚異的な宇宙の力を使います
  • 0:35 - 0:41
    chart[j]にあるすべてのステートを取ってきて
  • 0:41 - 0:43
    少し変更します
  • 0:43 - 0:47
    chart[j]に含まれる各ステートを
    jstateと呼びます
  • 0:47 - 0:51
    考え方としては赤点を1つ移動させるだけです
  • 0:51 - 0:58
    返り値である新しいステートは
    jstateと同じyを持ちます
  • 0:58 - 1:01
    それが何であれ左側はそのままです
  • 1:01 - 1:05
    jstateの赤点の前にあるものは全部取ります
  • 1:05 - 1:09
    jstate[1]が左にあるもの全部と対応します
  • 1:09 - 1:15
    還元によってできたxをシフトするため
    xを加えます
  • 1:15 - 1:20
    そしてjstateの赤点より後ろを
    xを除いて持ってきます
  • 1:20 - 1:23
    赤点をシフトしたからです
  • 1:23 - 1:26
    jstateの赤点の後ろはjstate[2]ですから
  • 1:26 - 1:30
    そこから最初の要素を取り除いて範囲選択します
  • 1:30 - 1:33
    このように複雑な記述が生まれます
  • 1:33 - 1:37
    kは何であってもそのまま残してください
  • 1:37 - 1:40
    jstate[3]がkに対応します
  • 1:40 - 1:45
    しかしこれらを返すのは
    特定の条件を満たす場合のみです
  • 1:45 - 1:51
    まず赤点が一番右に来るために
    cdが空でなくてはなりません
  • 1:51 - 1:56
    次に#の行にある2つのxが一致する必要があります
  • 1:56 - 2:03
    下のxはjstate[2]の最初の要素なので
    jstate[2]が空でないことを確認します
  • 2:03 - 2:07
    赤点が一番右にあれば確認は不要です
  • 2:07 - 2:13
    空でない場合
    最初の文字が上のxと一致することを確認します
  • 2:13 - 2:17
    これで還元によって得られる
    すべての状態を求められます
Title:
04-43 Writing Reductions Solution
Description:

dummy description

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
02:17

Japanese subtitles

Revisions