多重再帰の打ち切り
をテンプレートにして作成
[
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
メニュー
]
開始行:
*多重再帰の打ち切り [#u5188c30]
多重再帰構文を, 数値関数で打ち切ることを考えましょう. 例...
f(X,T):[1]X[2]f([3]f(sX,T-1),[4])
という関数定義ですね. 多重再帰が常に2段階読み込まれるよう...
f(X,T):[1]X[2]f([3]f(sX,T-1),10)
さて, この関数を適当な初項で実行することを考えます. する...
全ての数値が1以上である間は, 数値のない多重再帰
f(X):[1]X[2]f([3]f(sX))
と同じように振る舞います. そこで, 数値0が現れる瞬間を観察...
f(X,1) = [1]X[2]f([3]f(sX,0),10) = [1]X[2]f([3],10)
数値が0になり, 多重再帰にならなくなった瞬間, ''新たにf([3...
したがって, この構文は (特殊な初項のあと) ''無限ループに...
----
さて, より慎重に
f(X,T):[1]X[2]f([3]f(sX,T-1)[4],10)
という関数を見てみましょう. [4]は先ほどは付けていませんで...
すると
-''[1]X[2][1][3]''が, Xが育ちながら9回実行される.
-再帰の10段階目では''[1]X[2]''のみが実行される.
-[3][4]が初項として, f([3][4],10)が呼び出され, ループにな...
-[3][4]の部分にXが含まれていないならば無限ループに突入, X...
ということが分かります. 非常に非常に複雑でヤバイ構文なの...
どのくらい応用があるのか今でも未知数な部分もありますね.
----
特にすごいのは[3]の働きで,
-ループでXに与える初項
-1段階目から9段階目まで実行される部分
-10段階目では実行されない部分 (繰り返しの境界での規則変化)
という3つの役割を果たせています. つまり単純化した
f(X,T):Xf([1]f(sX,T-1),10)
という程度の構文でも, 不思議な短縮が可能となるのです. 試...
f(X,T):Xf(lf(sX,T-1),10)
f(,1)
などというコードを実行してみてください.
#ref(truncate_multiple_recursion.png,nolink)
180度回転および周期間の方向転換 (これは"l"が実行されない...
到底コード中に"l"が1つしかないとは思えませんね!
*問題例 [#z965ec23]
-[[Problem 1141]]:元祖.
-[[Problem 1226]]
-[[Problem 1692]]
終了行:
*多重再帰の打ち切り [#u5188c30]
多重再帰構文を, 数値関数で打ち切ることを考えましょう. 例...
f(X,T):[1]X[2]f([3]f(sX,T-1),[4])
という関数定義ですね. 多重再帰が常に2段階読み込まれるよう...
f(X,T):[1]X[2]f([3]f(sX,T-1),10)
さて, この関数を適当な初項で実行することを考えます. する...
全ての数値が1以上である間は, 数値のない多重再帰
f(X):[1]X[2]f([3]f(sX))
と同じように振る舞います. そこで, 数値0が現れる瞬間を観察...
f(X,1) = [1]X[2]f([3]f(sX,0),10) = [1]X[2]f([3],10)
数値が0になり, 多重再帰にならなくなった瞬間, ''新たにf([3...
したがって, この構文は (特殊な初項のあと) ''無限ループに...
----
さて, より慎重に
f(X,T):[1]X[2]f([3]f(sX,T-1)[4],10)
という関数を見てみましょう. [4]は先ほどは付けていませんで...
すると
-''[1]X[2][1][3]''が, Xが育ちながら9回実行される.
-再帰の10段階目では''[1]X[2]''のみが実行される.
-[3][4]が初項として, f([3][4],10)が呼び出され, ループにな...
-[3][4]の部分にXが含まれていないならば無限ループに突入, X...
ということが分かります. 非常に非常に複雑でヤバイ構文なの...
どのくらい応用があるのか今でも未知数な部分もありますね.
----
特にすごいのは[3]の働きで,
-ループでXに与える初項
-1段階目から9段階目まで実行される部分
-10段階目では実行されない部分 (繰り返しの境界での規則変化)
という3つの役割を果たせています. つまり単純化した
f(X,T):Xf([1]f(sX,T-1),10)
という程度の構文でも, 不思議な短縮が可能となるのです. 試...
f(X,T):Xf(lf(sX,T-1),10)
f(,1)
などというコードを実行してみてください.
#ref(truncate_multiple_recursion.png,nolink)
180度回転および周期間の方向転換 (これは"l"が実行されない...
到底コード中に"l"が1つしかないとは思えませんね!
*問題例 [#z965ec23]
-[[Problem 1141]]:元祖.
-[[Problem 1226]]
-[[Problem 1692]]
ページ名: