9B分類
をテンプレートにして作成
[
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
メニュー
]
開始行:
HOJを始めた人にとって, まず取り組みやすいのが, 制限バイト...
しかし, 例えば10Bや11B程度でも, 複雑な挙動をする再帰(''...
なかなか全部理解しきれないのが現状です.
しかし, ''9Bの1変数再帰''は人間の手でも全て分類できる程度...
以下に分類表を挙げることにしましょう.
なお, ここに挙げたコードで, Best解が9B以下の問題は全て解...
ここのコードで解けないものについては, 再帰以外の方法, 特...
また, 1変数再帰のうちでも, [[多重再帰構文!]]を利用したも...
*Z字 [#lc166a8e]
本質的には8Bで書けるもの
a(X):Xsa(lX)
a()
の向きを変えたり大きくした場合になります.
**小さい [#h0e4c26a]
-a(X):Xsla(lX),a()
-a(X):Xsra(rX),a()
-a(X):Xsla(rX),a()
-a(X):Xsra(lX),a()
-a(X):sXla(lX),a()
-a(X):sXra(rX),a()
-a(X):sXla(rX),a()
-a(X):sXra(lX),a()
-a(X):Xlsa(lX),a()
-a(X):Xrsa(rX),a()
-a(X):Xlsa(rX),a()
-a(X):Xrsa(lX),a()
**大きい [#t18a194d]
-a(X):Xssa(lX),a()
-a(X):Xssa(rX),a()
-a(X):sXsa(lX),a()
-a(X):sXsa(rX),a()
-a(X):ssXa(lX),a()
-a(X):ssXa(rX),a()
**太い [#t6aed260]
-a(X):sXa(srX),a()
-a(X):sXa(slX),a()
-a(X):lXa(srX),a()
-a(X):rXa(slX),a()
-a(X):rXa(srX),a()
-a(X):lXa(slX),a()
-a(X):Xsa(srX),a()
-a(X):Xsa(slX),a()
-a(X):Xla(srX),a()
-a(X):Xra(slX),a()
-a(X):Xra(srX),a()
-a(X):Xla(slX),a()
-a(X):sXa(rsX),a()
-a(X):sXa(lsX),a()
-a(X):lXa(rsX),a()
-a(X):rXa(lsX),a()
-a(X):rXa(rsX),a()
-a(X):lXa(lsX),a()
-a(X):Xsa(rsX),a()
-a(X):Xsa(lsX),a()
-a(X):Xra(rsX),a()
-a(X):Xla(lsX),a()
-a(X):Xla(rsX),a()
-a(X):Xra(lsX),a()
*成長Z字 [#u07ba788]
方向転換はZ字と同じ規則だが, sの個数が増えていくもの.
-a(X):Xa(lXss),a()
-a(X):Xa(rXss),a()
-a(X):Xa(ssXl),a()
-a(X):Xa(ssXr),a()
-a(X):Xa(sXl),a(s)
-a(X):Xa(sXr),a(s)
-a(X):Xa(sXl),a(l)
-a(X):Xa(sXr),a(r)
-a(X):Xa(sXl),a(r)
-a(X):Xa(sXr),a(l)
-a(X):Xa(lXs),a(s)
-a(X):Xa(rXs),a(s)
-a(X):Xa(lXs),a(l)
-a(X):Xa(rXs),a(r)
-a(X):Xa(lXs),a(r)
-a(X):Xa(rXs),a(l)
-a(X):Xsa(sXl),a()
-a(X):Xsa(sXr),a()
-a(X):sXa(lXs),a()
-a(X):sXa(rXs),a()
-a(X):Xla(lXs),a()
-a(X):Xra(rXs),a()
-a(X):Xla(rXs),a()
-a(X):Xra(lXs),a()
-a(X):lXa(sXl),a()
-a(X):rXa(sXr),a()
-a(X):lXa(sXr),a()
-a(X):rXa(sXl),a()
**太く [#haf900a6]
-a(X):Xa(sXsl),a()
-a(X):Xa(sXsr),a()
-a(X):Xa(sXls),a()
-a(X):Xa(sXrs),a()
-a(X):Xa(slXs),a()
-a(X):Xa(srXs),a()
-a(X):Xa(lsXs),a()
-a(X):Xa(rsXs),a()
*P字 [#kc0337bd]
原理的には, [[特殊な初項]]で紹介した, 最初の2項に特殊な方...
ある段階以降はただの繰り返しになります.
-a(X):sXa(XXr),a()
-a(X):sXa(XXl),a()
-a(X):Xsa(XXr),a()
-a(X):Xsa(XXl),a()
でも通常再帰せずに書いた方が短いです. sの部分が巨大だと再...
その場合も逆回りで書けば[[多重再帰構文!]]で書いた方が短...
*田4つ [#d26fc03c]
-a(X):Xa(XlX),a(s)
-a(X):Xa(XrX),a(s)
なお, Y=Xl, Xrと変数変換することで
-a(Y):Yra(YY),a(sl)
-a(Y):Yla(YY),a(sr)
などと変形できて, 田の字を描くのは明白になります.
*直線 [#y9502b69]
**ただの直線 [#re81f5f4]
sをたくさんつけても180度方向転換しかしないため, 直線を往...
-a(X):Xlla(sX),a()
-a(X):lXla(sX),a()
-a(X):rXra(sX),a()
-a(X):llXa(sX),a()
-a(X):Xa(sXll),a()
-a(X):Xa(llXs),a()
*2列直線 [#uc4bd38f]
[[特殊な2倍関数]]を理解するとこのような形になる理由がよく...
「正方形を何周もしたあげく最後のsが足りない」ようなXに収...
-a(X):Xa(XsX),a(l)
-a(X):Xa(XsX),a(r)
**3列直線 [#w704916f]
-a(X):Xa(lXsl),a()
-a(X):Xa(rXsr),a()
-a(X):Xa(lXls),a()
-a(X):Xa(rXrs),a()
-a(X):Xa(slXl),a()
-a(X):Xa(srXr),a()
-a(X):Xa(lsXl),a()
-a(X):Xa(rsXr),a()
**斜め [#rbefb45b]
-a(X):XXa(rX),a(s)
-a(X):XXa(lX),a(s)
-a(X):XXa(Xr),a(s)
-a(X):XXa(Xl),a(s)
-a(X):Xa(lXsr),a()
-a(X):Xa(rXsl),a()
-a(X):Xa(lXrs),a()
-a(X):Xa(rXls),a()
-a(X):Xa(slXr),a()
-a(X):Xa(srXl),a()
-a(X):Xa(lsXr),a()
-a(X):Xa(rsXl),a()
*うず [#l4c5da22]
再帰の基本.
-a(X):XXla(sX),a()【0,2,4,6,8】
-a(X):XXra(sX),a()【0,2,4,6,8】
-a(X):XlXa(sX),a()【1,3,5,7,9】
-a(X):XrXa(sX),a()【1,3,5,7,9】
-a(X):lXXa(sX),a()【0,2,4,6,8】
-a(X):rXXa(sX),a()【0,2,4,6,8】
-a(X):sXla(sX),a()【1,2,3,4,5】
-a(X):sXra(sX),a()【1,2,3,4,5】
-a(X):slXa(sX),a()【1,1,2,3,4】
-a(X):srXa(sX),a()【1,1,2,3,4】
-a(X):lsXa(sX),a()【1,2,3,4,5】
-a(X):rsXa(sX),a()【1,2,3,4,5】
-a(X):Xla(XXs),a()【0,1,3,7,15】
-a(X):Xra(XXs),a()【0,1,3,7,15】
-a(X):lXa(XXs),a()【0,1,3,7,15】
-a(X):rXa(XXs),a()【0,1,3,7,15】
-a(X):XXa(sX),a(l)【0,0,1,1,2,2】
-a(X):XXa(sX),a(r)【0,0,1,1,2,2】
-a(X):XXa(Xs),a(l)【0,0,1,1,2,2】
-a(X):XXa(Xs),a(r)【0,0,1,1,2,2】
-a(X):Xra(XX),a(s)【1,2,4,8,16】
-a(X):Xla(XX),a(s)【1,2,4,8,16】
-a(X):rXa(XX),a(s)【1,2,4,8,16】
-a(X):lXa(XX),a(s)【1,2,4,8,16】
-a(X):Xa(Xss),a(l)【0,2,4,6,8】
-a(X):Xa(Xss),a(r)【0,2,4,6,8】
**うず変種 [#b19123bc]
-a(X):Xa(sXlX),a()
-a(X):Xa(sXrX),a()
-a(X):Xa(XlXs),a()
-a(X):Xa(XrXs),a()
最初の例を変数変換すると
-a(Y):Yra(sYY),a(l)
となること見ると少しは理解しやすいかもしれません.
*ジグザグ [#g9c631d4]
Z字を作る独特な方向転換手順を, 2倍ずつすると片側に進んで...
sを増やすことで, どんどん歩幅が増えていますね.
-a(X):XXa(sXl),a()
-a(X):XXa(sXr),a()
-a(X):XXa(lXs),a()
-a(X):XXa(rXs),a()
*乱歩 [#z203acf8]
なお, 慣例上乱歩と呼ばれることが多いというだけで, 実際に...
巨大なフラクタルを描くのですが, 壁で位置が矯正されるため,...
次の6種は, 互いにミラー形や変数変換で説明できて, 似た形に...
-a(X):Xa(XsXl),a()
-a(X):Xa(XsXr),a()
-a(X):Xa(XXl),a(s)
-a(X):Xa(XXr),a(s)
-a(X):Xa(lXX),a(s)
-a(X):Xa(rXX),a(s)
その他の乱歩.
-a(X):Xa(sXXl),a()
-a(X):Xa(sXXr),a()
-a(X):Xa(lXXs),a()
-a(X):Xa(rXXs),a()
-a(X):Xa(lXsX),a()
-a(X):Xa(rXsX),a()
終了行:
HOJを始めた人にとって, まず取り組みやすいのが, 制限バイト...
しかし, 例えば10Bや11B程度でも, 複雑な挙動をする再帰(''...
なかなか全部理解しきれないのが現状です.
しかし, ''9Bの1変数再帰''は人間の手でも全て分類できる程度...
以下に分類表を挙げることにしましょう.
なお, ここに挙げたコードで, Best解が9B以下の問題は全て解...
ここのコードで解けないものについては, 再帰以外の方法, 特...
また, 1変数再帰のうちでも, [[多重再帰構文!]]を利用したも...
*Z字 [#lc166a8e]
本質的には8Bで書けるもの
a(X):Xsa(lX)
a()
の向きを変えたり大きくした場合になります.
**小さい [#h0e4c26a]
-a(X):Xsla(lX),a()
-a(X):Xsra(rX),a()
-a(X):Xsla(rX),a()
-a(X):Xsra(lX),a()
-a(X):sXla(lX),a()
-a(X):sXra(rX),a()
-a(X):sXla(rX),a()
-a(X):sXra(lX),a()
-a(X):Xlsa(lX),a()
-a(X):Xrsa(rX),a()
-a(X):Xlsa(rX),a()
-a(X):Xrsa(lX),a()
**大きい [#t18a194d]
-a(X):Xssa(lX),a()
-a(X):Xssa(rX),a()
-a(X):sXsa(lX),a()
-a(X):sXsa(rX),a()
-a(X):ssXa(lX),a()
-a(X):ssXa(rX),a()
**太い [#t6aed260]
-a(X):sXa(srX),a()
-a(X):sXa(slX),a()
-a(X):lXa(srX),a()
-a(X):rXa(slX),a()
-a(X):rXa(srX),a()
-a(X):lXa(slX),a()
-a(X):Xsa(srX),a()
-a(X):Xsa(slX),a()
-a(X):Xla(srX),a()
-a(X):Xra(slX),a()
-a(X):Xra(srX),a()
-a(X):Xla(slX),a()
-a(X):sXa(rsX),a()
-a(X):sXa(lsX),a()
-a(X):lXa(rsX),a()
-a(X):rXa(lsX),a()
-a(X):rXa(rsX),a()
-a(X):lXa(lsX),a()
-a(X):Xsa(rsX),a()
-a(X):Xsa(lsX),a()
-a(X):Xra(rsX),a()
-a(X):Xla(lsX),a()
-a(X):Xla(rsX),a()
-a(X):Xra(lsX),a()
*成長Z字 [#u07ba788]
方向転換はZ字と同じ規則だが, sの個数が増えていくもの.
-a(X):Xa(lXss),a()
-a(X):Xa(rXss),a()
-a(X):Xa(ssXl),a()
-a(X):Xa(ssXr),a()
-a(X):Xa(sXl),a(s)
-a(X):Xa(sXr),a(s)
-a(X):Xa(sXl),a(l)
-a(X):Xa(sXr),a(r)
-a(X):Xa(sXl),a(r)
-a(X):Xa(sXr),a(l)
-a(X):Xa(lXs),a(s)
-a(X):Xa(rXs),a(s)
-a(X):Xa(lXs),a(l)
-a(X):Xa(rXs),a(r)
-a(X):Xa(lXs),a(r)
-a(X):Xa(rXs),a(l)
-a(X):Xsa(sXl),a()
-a(X):Xsa(sXr),a()
-a(X):sXa(lXs),a()
-a(X):sXa(rXs),a()
-a(X):Xla(lXs),a()
-a(X):Xra(rXs),a()
-a(X):Xla(rXs),a()
-a(X):Xra(lXs),a()
-a(X):lXa(sXl),a()
-a(X):rXa(sXr),a()
-a(X):lXa(sXr),a()
-a(X):rXa(sXl),a()
**太く [#haf900a6]
-a(X):Xa(sXsl),a()
-a(X):Xa(sXsr),a()
-a(X):Xa(sXls),a()
-a(X):Xa(sXrs),a()
-a(X):Xa(slXs),a()
-a(X):Xa(srXs),a()
-a(X):Xa(lsXs),a()
-a(X):Xa(rsXs),a()
*P字 [#kc0337bd]
原理的には, [[特殊な初項]]で紹介した, 最初の2項に特殊な方...
ある段階以降はただの繰り返しになります.
-a(X):sXa(XXr),a()
-a(X):sXa(XXl),a()
-a(X):Xsa(XXr),a()
-a(X):Xsa(XXl),a()
でも通常再帰せずに書いた方が短いです. sの部分が巨大だと再...
その場合も逆回りで書けば[[多重再帰構文!]]で書いた方が短...
*田4つ [#d26fc03c]
-a(X):Xa(XlX),a(s)
-a(X):Xa(XrX),a(s)
なお, Y=Xl, Xrと変数変換することで
-a(Y):Yra(YY),a(sl)
-a(Y):Yla(YY),a(sr)
などと変形できて, 田の字を描くのは明白になります.
*直線 [#y9502b69]
**ただの直線 [#re81f5f4]
sをたくさんつけても180度方向転換しかしないため, 直線を往...
-a(X):Xlla(sX),a()
-a(X):lXla(sX),a()
-a(X):rXra(sX),a()
-a(X):llXa(sX),a()
-a(X):Xa(sXll),a()
-a(X):Xa(llXs),a()
*2列直線 [#uc4bd38f]
[[特殊な2倍関数]]を理解するとこのような形になる理由がよく...
「正方形を何周もしたあげく最後のsが足りない」ようなXに収...
-a(X):Xa(XsX),a(l)
-a(X):Xa(XsX),a(r)
**3列直線 [#w704916f]
-a(X):Xa(lXsl),a()
-a(X):Xa(rXsr),a()
-a(X):Xa(lXls),a()
-a(X):Xa(rXrs),a()
-a(X):Xa(slXl),a()
-a(X):Xa(srXr),a()
-a(X):Xa(lsXl),a()
-a(X):Xa(rsXr),a()
**斜め [#rbefb45b]
-a(X):XXa(rX),a(s)
-a(X):XXa(lX),a(s)
-a(X):XXa(Xr),a(s)
-a(X):XXa(Xl),a(s)
-a(X):Xa(lXsr),a()
-a(X):Xa(rXsl),a()
-a(X):Xa(lXrs),a()
-a(X):Xa(rXls),a()
-a(X):Xa(slXr),a()
-a(X):Xa(srXl),a()
-a(X):Xa(lsXr),a()
-a(X):Xa(rsXl),a()
*うず [#l4c5da22]
再帰の基本.
-a(X):XXla(sX),a()【0,2,4,6,8】
-a(X):XXra(sX),a()【0,2,4,6,8】
-a(X):XlXa(sX),a()【1,3,5,7,9】
-a(X):XrXa(sX),a()【1,3,5,7,9】
-a(X):lXXa(sX),a()【0,2,4,6,8】
-a(X):rXXa(sX),a()【0,2,4,6,8】
-a(X):sXla(sX),a()【1,2,3,4,5】
-a(X):sXra(sX),a()【1,2,3,4,5】
-a(X):slXa(sX),a()【1,1,2,3,4】
-a(X):srXa(sX),a()【1,1,2,3,4】
-a(X):lsXa(sX),a()【1,2,3,4,5】
-a(X):rsXa(sX),a()【1,2,3,4,5】
-a(X):Xla(XXs),a()【0,1,3,7,15】
-a(X):Xra(XXs),a()【0,1,3,7,15】
-a(X):lXa(XXs),a()【0,1,3,7,15】
-a(X):rXa(XXs),a()【0,1,3,7,15】
-a(X):XXa(sX),a(l)【0,0,1,1,2,2】
-a(X):XXa(sX),a(r)【0,0,1,1,2,2】
-a(X):XXa(Xs),a(l)【0,0,1,1,2,2】
-a(X):XXa(Xs),a(r)【0,0,1,1,2,2】
-a(X):Xra(XX),a(s)【1,2,4,8,16】
-a(X):Xla(XX),a(s)【1,2,4,8,16】
-a(X):rXa(XX),a(s)【1,2,4,8,16】
-a(X):lXa(XX),a(s)【1,2,4,8,16】
-a(X):Xa(Xss),a(l)【0,2,4,6,8】
-a(X):Xa(Xss),a(r)【0,2,4,6,8】
**うず変種 [#b19123bc]
-a(X):Xa(sXlX),a()
-a(X):Xa(sXrX),a()
-a(X):Xa(XlXs),a()
-a(X):Xa(XrXs),a()
最初の例を変数変換すると
-a(Y):Yra(sYY),a(l)
となること見ると少しは理解しやすいかもしれません.
*ジグザグ [#g9c631d4]
Z字を作る独特な方向転換手順を, 2倍ずつすると片側に進んで...
sを増やすことで, どんどん歩幅が増えていますね.
-a(X):XXa(sXl),a()
-a(X):XXa(sXr),a()
-a(X):XXa(lXs),a()
-a(X):XXa(rXs),a()
*乱歩 [#z203acf8]
なお, 慣例上乱歩と呼ばれることが多いというだけで, 実際に...
巨大なフラクタルを描くのですが, 壁で位置が矯正されるため,...
次の6種は, 互いにミラー形や変数変換で説明できて, 似た形に...
-a(X):Xa(XsXl),a()
-a(X):Xa(XsXr),a()
-a(X):Xa(XXl),a(s)
-a(X):Xa(XXr),a(s)
-a(X):Xa(lXX),a(s)
-a(X):Xa(rXX),a(s)
その他の乱歩.
-a(X):Xa(sXXl),a()
-a(X):Xa(sXXr),a()
-a(X):Xa(lXXs),a()
-a(X):Xa(rXXs),a()
-a(X):Xa(lXsX),a()
-a(X):Xa(rXsX),a()
ページ名: