多重再帰構文!
をテンプレートにして作成
[
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
メニュー
]
開始行:
[[HOJ講座]]
*多重再帰構文! [#m8f29a28]
''多重再帰構文''とは、
a(X):αXa(a())
a()
上のコードの''a(a())''のように、再帰関数を2重(あるいはそ...
一見意味がなさそうに見えますが、この構文にはある効果があ...
とりあえず、下のコードを実際に展開してみましょう。(ギリシ...
a(X):αXa(a(β))
a()
a()を1つずつ展開していきます。
a()
= αa(a(β))
= ααa(β)a(a(β))
= αααβa(a(β))a(a(β))
.....
= αααβααβ...ααβa(a(β)) [ここより右は永久に実行されない]
要するに
α+[ααβ]×無限
となっています。~
さて、ここで単に
a(X):αXa(β)
a()
とした場合と比べてみましょう。上のコードを展開します。
a()
= αa(β)
= ααβa(β)
.....
= ααβαβ...αβa(β) [ここより右は永久に実行されない]
要するに
α+[αβ]×無限
です。二つを並べて比べてみると、
α+[ααβ]×無限
α+[αβ]×無限
違いは「繰り返し部分の先頭にαがくっついているかどうか」だ...
つまり、この構文には''「αをa()で置換できる」''という効果...
----
ピンと来ないかも知れないので、短縮例を見てみましょう。
a(X):ssXrsssslssa(r)
a()
ssが4回出てきているので、従来の手法なら、
b:ss
a(X):bXrbblba(r)
a()
などとして1B縮めるところです。~
しかし、多重再帰構文を使って短縮すると、
a(X):ssXra(a(la(a(r)))
a()
となり、3Bも縮みます!~
関数内の'ss'を'a('に置き換える要領です。
関数の中にXが複数入っている場合も同じように短縮できます。~
例えば、
a(X):ssXrssXsslssa(r)
a()
なら、
a(X):ssXra(Xa(la(a(r)))
a()
という感じです。~
このような場合でも、置換される対象は「最初に出てくるXより...
----
応用としては、引数のある再帰なので、
a(X):αXa(a(βX))
a()
のように成長させたり、
a(X):αXa(a(β))
a(γ)
のように特殊な初項を使ったりすることも出来ます。~
*問題例 [#j40c8a11]
-[[Problem 1687]] 元祖。
-[[Problem 0090]] 最もsimpleな応用例。
-[[Problem 0710]]
-[[Problem 1688]]
終了行:
[[HOJ講座]]
*多重再帰構文! [#m8f29a28]
''多重再帰構文''とは、
a(X):αXa(a())
a()
上のコードの''a(a())''のように、再帰関数を2重(あるいはそ...
一見意味がなさそうに見えますが、この構文にはある効果があ...
とりあえず、下のコードを実際に展開してみましょう。(ギリシ...
a(X):αXa(a(β))
a()
a()を1つずつ展開していきます。
a()
= αa(a(β))
= ααa(β)a(a(β))
= αααβa(a(β))a(a(β))
.....
= αααβααβ...ααβa(a(β)) [ここより右は永久に実行されない]
要するに
α+[ααβ]×無限
となっています。~
さて、ここで単に
a(X):αXa(β)
a()
とした場合と比べてみましょう。上のコードを展開します。
a()
= αa(β)
= ααβa(β)
.....
= ααβαβ...αβa(β) [ここより右は永久に実行されない]
要するに
α+[αβ]×無限
です。二つを並べて比べてみると、
α+[ααβ]×無限
α+[αβ]×無限
違いは「繰り返し部分の先頭にαがくっついているかどうか」だ...
つまり、この構文には''「αをa()で置換できる」''という効果...
----
ピンと来ないかも知れないので、短縮例を見てみましょう。
a(X):ssXrsssslssa(r)
a()
ssが4回出てきているので、従来の手法なら、
b:ss
a(X):bXrbblba(r)
a()
などとして1B縮めるところです。~
しかし、多重再帰構文を使って短縮すると、
a(X):ssXra(a(la(a(r)))
a()
となり、3Bも縮みます!~
関数内の'ss'を'a('に置き換える要領です。
関数の中にXが複数入っている場合も同じように短縮できます。~
例えば、
a(X):ssXrssXsslssa(r)
a()
なら、
a(X):ssXra(Xa(la(a(r)))
a()
という感じです。~
このような場合でも、置換される対象は「最初に出てくるXより...
----
応用としては、引数のある再帰なので、
a(X):αXa(a(βX))
a()
のように成長させたり、
a(X):αXa(a(β))
a(γ)
のように特殊な初項を使ったりすることも出来ます。~
*問題例 [#j40c8a11]
-[[Problem 1687]] 元祖。
-[[Problem 0090]] 最もsimpleな応用例。
-[[Problem 0710]]
-[[Problem 1688]]
ページ名: