12B構文の周辺

メニュー

• English Page
• イベント情報
• 問題
• 用語集
• HOJ講座
• 便利ツール
• 雑記
• リンク集
   

更新履歴

最新の10件

カウンター

今日：2 合計：1143

メニューを編集

12B構文の周辺

有理数の成長速度2で紹介した12B構文を少し一般化すると,
（原理の理解しやすさは劣るものの）もっと色んな応用ができます.
今回はいろんな応用例を紹介しましょう. 基本構文は

a(T):[1]a(AT+B)[2]a(CT+D)

です. ABCDは適当な数値だと思ってください.

直接の変形

まずは12B定跡の直接的な変形を考えてみます．

a(T):sa(T-A)ra(T+B)

のうちsやrの部分を別のものにしてみるというのが簡単な変形でしょう.
例えばsをsrslにしてみるということも考えられますし, あるいはsをssに変えると
「4,4,6」などの繰り返しも実現できますね.

次にrの部分です. 例えばここをsrなどとすると，ちょうど曲がる前にs1つ分
水増しされる形になります. これはT+BのところをT+A+Bと書きかえるのと基本的には
等価なので, あまり役に立ちませんが, 数値の大きさを抑えられるので
こうしないと255以下に抑えられないときなどに使えるでしょうか…？
またa(T):ssa(T-A)sra(T+B)などとすると, 「3,3,5」などの数列を作ることもできそうです.
これも実はもっと短い書き方があるのですが….

もう少し偏った数列の実現

今度は「T+B」のところに「T+T+B」などと2倍要素をくみこんでみましょう！例えば

a(T):sa(T-11)ra(T+T+50)
a(1)

としてEditで実行してみましょう.

かなり複雑な動きですが, 結果的に次の周期10の数列が実現できていることが分かります.

[5,4,5,6,5,5,6,4,6,5]

このように3種の数値が出てくるのは普通の12B構文では不可能でした.
原理は…いやぁ…あまりよい説明ができません. 「計算するとそうなる」とね.
あまり直感的に分かりやすい数学的現象と直接は対応しないと思います.

ただ言えることとしては「T+T+B」と2倍が含まれた書き方では, 最大値と最小値の差が2以下.
同じように3倍を使うと3の差まで作り出せる可能性があります.
周期は, 今回の場合「2^n mod 11」の周期と同じになっています.
これも一般的に似たことが言えます. 一般にはr倍を使うと周期は

（r^n mod Aの周期）×（r-1）

の約数であるといえます. 自分は手動で探すときは, （r^nの周期）を気にしてAを選んで調べるようにしています.

---

ちょっと具体的に色々つくってみましょう. 例えば

[3,3,5]

という数列の繰り返しを実現したいとします. 最大値5と最小値3では差が2なので,

a(T):sa(T-A)ra(T+T+B)

という構文を考えます. 周期が3になってほしいので, 2^nが3周期になるように, 2^3=1 mod AというAを考えて,

a(T):sa(T-7)ra(T+T+B)

という構文を考えます. Bを1以上7以下まで色々試してみましょう.
「T+T+1」とすると「1,1,3」が実現できることが分かりますね.
そこでこれに2ずつ水増しすればよいので, 「T+T+1+7+7=T+T+15」つまり

a(T):sa(T-7)ra(T+T+15)

というコードで適当に初期値を与えればよいと分かりました！！初期値を調整して

a(T):sa(T-7)ra(T+T+15)
a(17)

で

[3,3,5]

の繰り返しが実現されます.

なお「色々試してみましょう」と書いたけど, これは現段階のmasの理解ではそうとしか説明しようがないです….
手計算やEditで総当たりしてもよいですし, プログラム組んでもよいでしょう.
ただ「2倍」「mod 7」というのはある程度理論的な裏付けがある数値なので,
これを理解していると手計算での調べ上げもかなり楽ですね.

---

もう一例ほど. 例えば

[5,7,6,8]

という周期4での繰り返しを作ってみましょう. 最大と最小の差が3なので

a(T):sa(T-A)ra(T+T+T+B)

という形を考えます. 周期4なので, 3^n mod Aが4周期になるようにAは80の約数.
2周期にはならないので8の約数ではない. mod 5,10,16,20など色々考えられますね.
大きければ大きいほど多様なパターンを作り出せる可能性がありますが,
255を超える心配も出てきます. 適当なものを色々試しましょう. 今回は

a(T):sa(T-20)ra(T+T+T+87)
a(90)

で上手くいきました.

他にも同じ数列を実現する数値設定があると思います.

---

結局どんな数列が作れるかって言うと…よくわかりません！
小さい周期のものはかなり色々作れますね. 最大と最小の差が大きくなるほどバイト数はかさみます.
あと，結局使ったことがないので省略しましたが

a(T):sa(T-7)ra(100-T-T)

のように，引き算を使っても周期的な数列が実現されます.
結局正の係数の場合と似たような数列しか作れないと思いますが, どうなんでしょうか.

小数展開

定数項を含めずに単純に2倍した

a(T):sa(T-5)ra(T+T)

などのコードは, 数学的にもうちょっと分かりやすい解釈があります.
a(1)と実行すると, ちょうどこれは1/5を2進法に直していることになっています．
2進法はなじみにくいと思うので, 10進法で考えてみましょう.

a(T):sa(T-7)ra(T+T+T+T+T+T+T+T+T+T)
a(1)

10個足してます. a(1)からはじめて, 数値の上では

「7を引けるだけ引いて，10倍に取り換えて，…」

という繰り返しが起きますね. これは「1割る7」の筆算と全く同じです！！
ということは, 1/7=0.142857...にあわせて

[0,1,4,2,8,5,7,1,4,2,...]

という数列が実現..というと少し違いますｗ
「（7が引ける回数）+1」回のsが実行されてしまうので, 実際には1ずつ多い

[1,2,5,3,9,6,8,2,5,3,...]

という数列が実現されてしまいます.

これを修正して, 「ちょうど少数展開に対応する数列」を実現するには,

a(X,T):a(sX,T-7)Xra(,T+T+T+T+T+T+T+T+T+T)
a(,1)

のように, 7を引いた回数を変数に格納してあげるとちょうど上手くいきます.

計算結果を変数に格納してあげるテクは大事なのでおさえておきましょう （特に計算結果の長さを複数回使う場合などには必須）.
これで1/7の小数展開が出来ましたが，実は割り切れる場合の処理はズレますｗ
「7割る7」のような状況はHOJでは「7はもう引けない」となってしまうからです.
0が生き残らないことに起因する計算ミスはありがちなので気をつけましょう.
何はともあれ, a(T+T)のようにすると，有理数の2進法小数展開のようなことをしている ことが分かりました.
実はa(T+T+1)などもその変形と見なせますが, その変形ルールは結構難しそうです.
良い理解の仕方が分かったら教えてくれると助かります.

乱歩的な動き

今度は少し符号などを変えてみて例えば

a(T):sa(T-29)ra(T-11)
a(255)

などとしてみましょう. a(255)を実行するとどうなるでしょうか？

結構変態な動きをしますね.

「a(T+B)」のような部位があると，展開時に全ての数値が0になることはなく,
繰り返しにはまってくれるのですが, 今度は全然繰り返しにはならなくて
「わけのわからないもの」になります. 乱歩を作る目的でこのような構文を
使える可能性はあると思います. 実際のところ実績として再帰乱歩よりも短い解を作れたことはほとんどないですがｗ

ただ「s,rを並べる」ではなく「srslとrを並べる」「srsとlslを並べる」なども可能なので,
パーツがわかっててそれを「ランダムに」並べたいときなどは簡単に探索できるかもしれませんね？
自分も十分な経験がないのでどのくらい有用なのかよく分かりませんｗ
もちろんTの係数を2にしたり符号を変えたりしてもわけのわからないものはたくさん作れそうです.
役に立つコードがどのくらいあるのかは…よく分からないですね.
色々試したりしてみると新しい発見につながるかも？？

より複雑な構文

今度は

a(T):sa(T-4)ra(T-1)a(11)
a(11)

などと2つの引き算の奥に定数を置いて繰り返してみましょう．

[s/s/sr/sr/sr]

という繰り返しの後でa(11)に戻ります.

a(T):sa(T-4)ra(T-1)a(T+10)
a(11)

としても同じですね. これをさらにちょっとズラして…イメージとしては

a(T):sa(T-4)ra(T-1)a(T+10.25)

などとしてみると, 4回に1回「sr」の回数が変わって不思議な形になります．HOJ的には

a(T):sa(T-16)ra(T-4)a(T+41)
a(44)

で実行できますね.

「a/a/a/a/ab/ab/ab」のような形の繰り返しを回数を調整しながら動かせる構文なんだと思います.
まだあまり研究が進んでいない構文だと思うので, 是非色々試して面白い形を見つけてみてください♪