有理数の成長速度2

有理数の成長速度の原理の応用で, 通称12B構文と呼ばれる重要な構文を紹介しましょう.
今回も説明のため, 小数や分数の数値を用いることにします.
いきなりですが, 次のコードを見てみてください:

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

まず[s11個]が実行されたあと, a(T+10.25)の「おかわり」でa(11.25)が呼び出されますね.
さらに[s12個]が実行されたあとa(11.5)が呼び出されます. 続けていくと

a(11) → a(11.25) → a(10.50) → a(10.75) → a(11)

[s11個] r → [s12個] r → [s11個] r → [s11個] r

となり, ここでループに入ります. 結果として,

[11, 12, 11, 11]

という周期4の繰り返しを作ることに成功しました.
小数ではHOJで上手く動かないので, 実際のコードは全ての数値を4倍して

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

のようになります. 初めてこの構文を見る人はEditなどで動かしてみるとよいでしょう.

12B_1.png

今度は数値を変えてみましょう. やはり小数を使って説明します:

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

どういう数列が現れるか分かりますか??

11 11.4 10.8 11.2 10.6 11

となって周期5でもとに戻り, 結果として

[11,12,11,12,11]

の繰り返しが得られます. 当然HOJで動くコードは

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

ですね.

12B_2.png

さてさて, 上記で紹介した2つのコード

a(T):sa(T-4)ra(T+41)
a(44)
a(T):sa(T-5)ra(T+52)
a(55)

の数値設定の意味について理解を深めておくと, かなり自在に数列を作り出すことができます(もちろん制限はあります).
例えば

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

という周期7の繰り返しを実現するには?という状況で簡単に数値設定を見つけることができます.
まず上の具体例をよく観察してみましょう.
初期値a(44), a(55)などは「どのような繰り返しになるか」という点では実はあまり重要ではないです.
例えばa(1)にしても(ちょっと違う向きにはなるけど)同じ挙動をすることが分かるでしょう.
そこで他の数値に注目します:

T-4T+41[11,12,11,11]
T-5T+52[11,12,11,12,11]

規則は分かりますか?結論から言うと,

a(T):[x]a(T-A)[y]a(T+B)という数値設定をした場合, 周期はA, そのA回のあいだにA+B個の[x]が配置される.

というのが規則です. 例えば後者の例で考えると, T+52がちょうど5回呼び出されると,
結局数値を260足していることになり, それに応じて「数値を5消費しながら配置されるs」が52個(=B).
さらにもう引けなくなったときの「数値を消費しないのに配置されるs」が周期中に5個(=A)あり
結局周期中にA+B個のsが配置されるというわけです.


数値設定の原理が理解できると, 例えば上の[5,6,6,5,6,5,6]の例について,

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

のようなコードを書けば良いと分かるはずです.
あとは初期値の設定ですが...これはややこしいので色々試して見つけるのは速いのではないでしょうか(^^;
コードを実行すると, 初項に応じて適切な回数sを実行したあと, mod7での値に応じて 周期のどこかに突入します.
周期のどの部分が, mod 7でのどの値に対応するかを理論的に調整するのは,
masの理解では結構大変です(少なくとも自分の理解では).


もちろん作れる数列には制限があります. まず255を超える数値が出てくるとNGですね.~ 例えば

a(T):sa(T-100)ra(T+199)

などの数値設定であっても直接は255以上の数値設定が出てきていませんが,

これ以上100を引けなくなると199を足す

というルールなので, 最大で100+199=299の数値が出てきてしまいアウトです.

もう1つの制限として, ある程度偏りのない数列しか実現できないということがあります.
(数学的思考が苦手でない人は想像してもらえればよいですが,
等差数列の整数部分の差分を拾っていった数列なので大体平等になっちゃいます. )
例えば

[3,3,5], [3,3,5]

のように値が飛ぶものは(そのままでは)作れません. また,

[2,2,3,3], [2,2,3,3]

のように, 値が大きい地帯と小さい地帯の偏りがある分離するようなものも(そのままでは)作れません.

前者の例でいくと,周期3の中に11を均等に配分すると3,3,5ではなく

[3,4,4], [3,4,4]

のようになってしまいますし, 後者の例でいくと, 周期4の中に10を均等に配分すると,

[2,3,2,3], [2,3,2,3]

のようになってしまいます.
それぞれ12B構文の変形で実現する方法がありますが, それはまた別の講座で扱うことにします.


以上で構文の基本説明は終わりますが, 結局12B構文で描ける図形はどんな形でしょうか??
いろいろEditなどで試してみてください. 偏りの少ない長さを4方向にばら撒いていくので,
多くの場合,正方形にかなり近いものになります.
数値設定を上手くすると, 平均的なもの以上に派手な動きをしますので紹介しておきます.
これは無理やり4方向に偏りを強調することで, (同じ場所をうろうろするのではなく)
特定の方向に進んでいくというものです. 最初にあげた「12,11,11,11」もその一例です.

【画像?】


このように正方形が1方向に進行していくというものもありますが, これをさらに変形させてみましょう.
アイデアを分かりやすくするため,小数で説明します.

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

(このままだと数値が255を超えますが,説明のためということでご了承ください. )
もちろん,「約10.25」を意識した数値設定です.そのためこれを実行すると,

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

の場合とかなり近い挙動を示します. 「0.000001」の誤差が関係してくるのは
「T+10.250001」が1000000回呼び出された後で, そこで初めて1の誤差が生じます.
結果として, 基本的には正方形を描いて1方向に進むが, ''誤差が蓄積した瞬間
パターンが1つズレて進行方向が変わる''という現象が生じます.

実際にHOJ上で動くコードで確かめてみましょう.
ポイントは10.250001のように, 1/4に非常に近い有理数(あるいは3/4に近いものでもよい)を使うことです.
具体的には「A/(4A±1)」という有理数に整数を加えたものを用いるとよいです
例えば「83/37」という分数を利用して

a(T):sa(T-37)ra(T+83)

というコードを(適当な初項を与えて)実行してみてください.

12B_3.png

正方形から正方形を繰り抜いた形をぐるぐる回っていますね? この構文では最も特徴的で汎用性がある形だと思います. この形が使える問題も結構ありますので探してみてください!


以上で説明したのが, 通称12B構文と呼ばれる有名構文で, 定数A, B, Cについて

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

と書くのが基本構文です. どんな数値を入れても12Bであり, 他の方法では到底
12Bでは描けないような特徴的な形を描くため, 12B構文と呼ばれています.

もちろんsとrである必要はなく, 一般形は

a(T):[x]a(T-A)[y]a(T-B)

となります. [x]と[y]がs,rのように1バイトずつじゃない場合には,
12バイトにはなりませんが, この場合も12B構文と呼ぶことが多いです.

a(T):srsla(T-A)la(T-B)
a(T):ssa(T-A)ra(T-B)

などの変種ですっきり実装できる問題もあります.
どんどん応用して12B構文マスターを目指してください!


執筆:mas


添付ファイル: file12B_3.png 94件 [詳細] file12B_2.png 98件 [詳細] file12B_1.png 96件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-01-16 (水) 23:17:04 (2099d)