このブログは、旧・はてなダイアリー「檜山正幸のキマイラ飼育記 メモ編」（http://d.hatena.ne.jp/m-hiyama-memo/）のデータを移行・保存したものであり、今後（2019年1月以降）更新の予定はありません。

今後の更新は、新しいブログ http://m-hiyama-memo.hatenablog.com/ で行います。

整数式の操作 (A3P2)

RSS練習問題

※この記事は「記事3 問題集2」

ノード・ワイヤー図〈ストリング図〉の解説は：

これより前に行うべき練習は：

この練習では、整数とその足し算／掛け算について考える。足し算／掛け算を含む式をどう組み立てるかを、横棒記法とノード・ワイヤー図で表現する。

内容：

  1. 式の定義
  2. 式の操作
  3. 事例と入出力
  4. 練習問題

式の定義

ここで（あくまで「ここで」）考える式は、次の構成素から組み立てられるものに限る。

  1. 非負整数の定数。2, 10, 125, 0 など。
  2. 整数を表す変数。変数の文字（名前）は何を使ってもよい（自由）。
  3. 足し算記号 + と掛け算記号 × 。
  4. 符号の反転を表すマイナス - 。
  5. 演算の優先順を示す括弧。丸括弧のみ。

次の注意事項がある。

  1. 負の整数は、単一の基本記号ではなく、正整数と負号（マイナス記号）を組み合わせた複合記号として表す。
  2. 引き算は使えない。x - y ではなくて x + -y とする。
  3. x + y + z のような書き方は曖昧とみなして許さない。(x + y) + z か x + (y + z) のどちらかを使う。
  4. 掛け算の記号×は省略してよい。x×y は xy と書いてよい。しかし xyz は曖昧なので許さない。(xy)z か x(yz) とする。
  5. 累乗の記法を使ってよい。yy は y2 と書いてよい。しかし、y3 は使えない。y2y か yy2 とする。
  6. 「足し算より掛け算を優先する」というルールは使ってよい。xy + zw は (x×y) + (z×w) と解釈される。
  7. 掛け算と負号〈マイナス記号〉の優先順位は決めてないので、-xy は曖昧である。(-x)y または -(xy) と書く。

当然ながら、上記のルールはここだけのローカルなものである。

式の操作

前節で定義した式に対して、以下に述べるような操作を考える。操作の説明とともに、横棒記法も説明する。A, B などは式を表す文字（「メタ変数」と呼んだりする）。

足し算（和） sum

A, B が2つの式のとき、AとBを足し算した式を作る操作を sum と書く。

例：操作の前（2つの式を横に並べている）

(2x + -z) + 10    a + (2b + -1)

これらの式に対して、sum を行う。

例：操作の後

((2x + -z) + 10) + (a + (2b + -1))

これを、横棒記法を用いて、次のように書く。

  (2x + -z) + 10       a + (2b + -1)
 ------------------------------------ sum
  ((2x + -z) + 10) + (a + (2b + -1))

一般的には、

  A   B
 -------- sum
  A + B

式のルールを守るために、括弧を付ける必要があるかも知れない。以下、括弧の必要性をいちいち言わない。

掛け算（積） product

A, B が2つの式のとき、AとBを掛け算した式を作る操作を prod と書く。

  A   B
 -------- prod
  A×B
反数 opposite

反数という言葉は：

Aが式のとき、Aの反数を作る操作を opp と書く。

   A
 ----- opp
  -A
複製 duplication

Aが式のとき、同じAを2つにして横に並べる操作を dup と書く。

   A
 ------ dup
  A  A
入れ替え swap

A, B が2つの式のとき、AとBの並び順を入れ替える操作を swap と書く。

  A  B
 ------ swap
  B  A
何もしない identity

Aが式のとき、何もしないことを id と書く。

  A
 --- id
  A

事例と入出力

前節で導入した操作を組み合わせることが出来る。操作の過程全体は、横棒記法の図として表現できる。

    x
 ------ dup
  x  x         6 + a   t
 ------ prod  ----------- prod
   xx           (6 + a)t
 ------ opp   ----------- id
 -(xx)          (6 + a)t
 ------------------------ swap
  (6 + a)t  -(xx)
 -------------------- sum
  (6 + a)t + -(xx)

横棒記法の図の最上段を左から右に見て、出現した式を並べた列をここでは（その図の）入力列〈input sequence | input list〉と呼ぶ。同様に、図の最下段を左から右に見て、出現した式を並べた列を出力列〈output sequence | output list〉と呼ぶ。

上の事例では：

  • 入力列： x, 6 + a, t
  • 出力列： (6 + a)t + -(xx) （列とは言っても式がひとつだけ）

ある入力列からある出力例が得られたことを、ここだけの臨時の記法だが、

  • 入力列 |→| 出力列

と書くことにする。上の事例なら、

  • x, 6 + a, t |→| (6 + a)t + -(xx)

先に入出力が指定されて、そのような入出力となる図を描くことができる。例えば、

  • x, y |→| y2 + x2

に対して、入力列／出力列がこのようになる横棒記法の図は：

   x           y
 ----- dup   ----- dup
  x  x        y  y
 ------ prod ------ prod
   xx         yy
  --------------- swap
   yy    xx
  ---------- sum
   yy + xx

練習問題

次のような入力列／出力列を持つような横棒記法の図を描け。

  1. x |→| x + -x
  2. x, y, 2 |→| (x2 + 2(xy)) + y2
  3. a, b, c |→| (a + b) + c
  4. a, b, c |→| a + (b + c)
  5. c, b, a |→| ((a + b) + c)(a + (b + c))
  6. s, 2 |→| (2s2 + -(2s)) + -2
  7. y, x |→| x + y, x + -y
  8. s, t, 2 |→| (2s2 + -(2s)) + -2, (2t2 + -(2t)) + -2
  9. 概念や書き方に慣れるために、幾つか（必要なだけ）同様な作業を行え。

[追記]

練習問題の6と8を修正：

  • 練習問題の6
    • 誤： 2s2 + -(2s) + -2
    • 正： (2s2 + -(2s)) + -2
  • 練習問題の9
    • 誤： 2s2 + -(2s) + -2, 2t2 + -(2t) + -2
    • 正： (2s2 + -(2s)) + -2, (2t2 + -(2t)) + -2

[/追記]

さらに、ノード・ワイヤー図とテキスト表現も練習する。

  1. 上の問題で出来た横棒記法の図を、ノード・ワイヤー図として描け。ノードラベルは操作（sum, dup など）、ワイヤーラベルは式である。ラベルは省略せずに記入する。
  2. 前問のノード・ワイヤー図を、すべての描画方向（↑→, ↑←, ↓→, ↓←, →↑, →↓, ←↑, ←↓）で描いてみよ。
  3. 前問のノード・ワイヤー図をテキスト記法で表現せよ。例えば、x, y |→| y2 + x2 の事例なら、(dup\otimesdup);(prod\otimesprod);swap;sum となる。
  4. もし可能なら、自分以外の人に入力列と前問のテキスト表現だけを見せて、出力列に至る過程を再現できるか確認せよ。
  5. 同じ入出力となる図は一通りではない。違った図も考えよ。
  6. 概念や書き方に慣れるために、幾つか（必要なだけ）同様な作業を行え。