変数変換
をテンプレートにして作成
[
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
メニュー
]
開始行:
*変数変換 [#b8aa7784]
次のような短縮は,ある程度Herbertをプレイした方なら(?)...
a(X):XrXra(sX)
a()
b(Y):YYb(sY)
b(r)
今回は,このような感じの短縮について整理しましょう.~
上記のパターンは比較的簡単ですね.「a(X):****a(pX)」とい...
初項としてa(q)と与えておくと,Xの部分が「ppppppq」という...
同じように,「a(X):****a(Xp)」という成長をさせると, 初項...
Xの部分が「qpppppp」というように,繰り返しの手前にqがつい...
----
もう少し複雑な書き変えをしてみましょう.例えば
a(X):XrXrXrXra(XrXlX)
a(s)
というコードがあったとします.実行部分はXrばかりなので,...
さっと間違わずにできますか??上記のコードを正しく変換す...
b(Y):YYYYb(YYllY)
b(sr)
合計3B縮みました.こういう変数変換を理解しておくと役に立...
再帰のn段階目のXやYをX[n],Y[n]などと表すことにします.~
「Y[n]=X[n]r」という変換をすればいいわけです.~
次のような式変形は数列の漸化式などで習ったことがあるかも...
Y[1]=X[1]r=sr,
Y[n+1]=X[n+1]r=X[n]rX[n]lX[n]r=(Y[n]l)r(Y[n]l)l(Y[n]l)r=...
特に細部の説明は不要ですよね?いくつか演習としてみるので...
全部実行を「XXXX」の形にしてみましょう.
a(X):XrXrXrXra(XXX)
a(s)
a(X):XrXrXrXra(XXl)
a(s)
a(X):XlXlXlXla(XXl)
a(s)
a(X):XlXlXlXla(srslXss)
a(ll)
答えは一番下にでも.
----
「変数変換」に該当するかは微妙ですが,「方向転換をどこに...
短縮出来る例をいくつか紹介しましょう.まず覚えておいた方...
a(X):l **** ra(**)
a(**)
Xの変化規則など全く関係なく,「l****r」となっている時点で...
再帰の1段階目,2段階目,…という境目の部分を考えると
>[l*****r][l******r][l******r][l******r]…
となっていて毎回「rl」が挟まるのがいかにも無駄な感じです...
a(X):****a(**)
la(**)
と最初にlを避けておくことで1Bの短縮ができます.逆に
a(X):****a(**)
la(**)
を
a(X):l****ra(**)
a(**)
と書き直すことで短縮につながることもあります.例えば
a(X):l****la(**)
la(**)
とかなっていると1B縮みますね.
----
もうちょっと複雑な例を扱ってみましょう.例えば次のコード...
a(X):rXXXXa(XlX)
ra(sr)
答えに至るまでの考え方と共に丁寧に説明してみることにしま...
まず,このコードの経路は「長さ1,長さ2,長さ4,……」という...
長さが2倍ずつになっているので,「a(X):****a(XX), a(s)」と...
方向転換を組み込んだ形で変数を置いています.これで十分上...
損をしている部分があるのです.~
「このまま見ても縮まないけど…」というときは,一旦~
「変数を方向転換を含まない形に戻して」考えるとよいです....
a(X):rXrXrXrXra(XX)
ra(s)
と戻すことが出来ます.さらに最初のrを中に入れると
a(X):rrXrXrXrXrla(XX)
a(s)
つまり
a(X):rrXrXrXrXa(XX)
a(s)
となりますね.すると,Xrは3度,rXは4度現れており,「Xrを...
「rXを新しい変数と思う」という変換で短縮をする方が賢いと...
あとはY=rXとおいて変数変換して
b(Y):rYYYYa(YlY)
b(rs)
と書き直すことで最初のコードよりも1Bの短縮に成功しました!
----
ある程度慣れてくるとこの手の書き換えは割と感覚的に出来る...
でも複雑な状況になってくると間違えやすくなってきたり,最...
ちゃんと原理を理解しているとどんな場面でもかなり自信を持...
----
さて,途中に挙げた問題の解答を載せておきます:
b(Y):YYYYb(YlYlY)
b(sr)
b(Y):YYYYb(YlYl)
b(sr)
b(Y):YYYYb(YrYl)
b(sl)
b(Y):YYYYb(lsrsYllssll)
b(r)
4つめのは辛うじて得をした感じですが,「育てる向きと反対向...
いるので上手なコードには見えないですねぇ….あまり上手く書...
こういう変数変換のが理解できてくると,
-XXとXlXとXllXとXrXは似ている
-XXlとXlXlとXrXlとXrXrは似ている
みたいな現象も説明することが出来そうですね.
終了行:
*変数変換 [#b8aa7784]
次のような短縮は,ある程度Herbertをプレイした方なら(?)...
a(X):XrXra(sX)
a()
b(Y):YYb(sY)
b(r)
今回は,このような感じの短縮について整理しましょう.~
上記のパターンは比較的簡単ですね.「a(X):****a(pX)」とい...
初項としてa(q)と与えておくと,Xの部分が「ppppppq」という...
同じように,「a(X):****a(Xp)」という成長をさせると, 初項...
Xの部分が「qpppppp」というように,繰り返しの手前にqがつい...
----
もう少し複雑な書き変えをしてみましょう.例えば
a(X):XrXrXrXra(XrXlX)
a(s)
というコードがあったとします.実行部分はXrばかりなので,...
さっと間違わずにできますか??上記のコードを正しく変換す...
b(Y):YYYYb(YYllY)
b(sr)
合計3B縮みました.こういう変数変換を理解しておくと役に立...
再帰のn段階目のXやYをX[n],Y[n]などと表すことにします.~
「Y[n]=X[n]r」という変換をすればいいわけです.~
次のような式変形は数列の漸化式などで習ったことがあるかも...
Y[1]=X[1]r=sr,
Y[n+1]=X[n+1]r=X[n]rX[n]lX[n]r=(Y[n]l)r(Y[n]l)l(Y[n]l)r=...
特に細部の説明は不要ですよね?いくつか演習としてみるので...
全部実行を「XXXX」の形にしてみましょう.
a(X):XrXrXrXra(XXX)
a(s)
a(X):XrXrXrXra(XXl)
a(s)
a(X):XlXlXlXla(XXl)
a(s)
a(X):XlXlXlXla(srslXss)
a(ll)
答えは一番下にでも.
----
「変数変換」に該当するかは微妙ですが,「方向転換をどこに...
短縮出来る例をいくつか紹介しましょう.まず覚えておいた方...
a(X):l **** ra(**)
a(**)
Xの変化規則など全く関係なく,「l****r」となっている時点で...
再帰の1段階目,2段階目,…という境目の部分を考えると
>[l*****r][l******r][l******r][l******r]…
となっていて毎回「rl」が挟まるのがいかにも無駄な感じです...
a(X):****a(**)
la(**)
と最初にlを避けておくことで1Bの短縮ができます.逆に
a(X):****a(**)
la(**)
を
a(X):l****ra(**)
a(**)
と書き直すことで短縮につながることもあります.例えば
a(X):l****la(**)
la(**)
とかなっていると1B縮みますね.
----
もうちょっと複雑な例を扱ってみましょう.例えば次のコード...
a(X):rXXXXa(XlX)
ra(sr)
答えに至るまでの考え方と共に丁寧に説明してみることにしま...
まず,このコードの経路は「長さ1,長さ2,長さ4,……」という...
長さが2倍ずつになっているので,「a(X):****a(XX), a(s)」と...
方向転換を組み込んだ形で変数を置いています.これで十分上...
損をしている部分があるのです.~
「このまま見ても縮まないけど…」というときは,一旦~
「変数を方向転換を含まない形に戻して」考えるとよいです....
a(X):rXrXrXrXra(XX)
ra(s)
と戻すことが出来ます.さらに最初のrを中に入れると
a(X):rrXrXrXrXrla(XX)
a(s)
つまり
a(X):rrXrXrXrXa(XX)
a(s)
となりますね.すると,Xrは3度,rXは4度現れており,「Xrを...
「rXを新しい変数と思う」という変換で短縮をする方が賢いと...
あとはY=rXとおいて変数変換して
b(Y):rYYYYa(YlY)
b(rs)
と書き直すことで最初のコードよりも1Bの短縮に成功しました!
----
ある程度慣れてくるとこの手の書き換えは割と感覚的に出来る...
でも複雑な状況になってくると間違えやすくなってきたり,最...
ちゃんと原理を理解しているとどんな場面でもかなり自信を持...
----
さて,途中に挙げた問題の解答を載せておきます:
b(Y):YYYYb(YlYlY)
b(sr)
b(Y):YYYYb(YlYl)
b(sr)
b(Y):YYYYb(YrYl)
b(sl)
b(Y):YYYYb(lsrsYllssll)
b(r)
4つめのは辛うじて得をした感じですが,「育てる向きと反対向...
いるので上手なコードには見えないですねぇ….あまり上手く書...
こういう変数変換のが理解できてくると,
-XXとXlXとXllXとXrXは似ている
-XXlとXlXlとXrXlとXrXrは似ている
みたいな現象も説明することが出来そうですね.
ページ名: