いきなりですが次の規則を実装する方法を考えてみましょう.
[s]r[ss]r[sss]r[sss]r [ssss]r[sssss]r[ssssss]r[ssssss]r …
数列でいうと,
[1,2,3,3], [4,5,6,6], [7,8,9,9].
という,「4回に3成長する」というものです.
成長速度の調整
の講座では,これを多変数の再帰で実現する方法を紹介しています.具体的には
a(A,B,C,D):Xra(ssB,sC,D,A), a(s,,,)
などとすれば良いですね.4回で一区切りとなっているので,4変数必要になっています.
さてさて,今回紹介するのは次のコードです:
a(T):sa(T-4)
b(T):a(T)rb(T+3)
b(3)
Editなどで実行して,上記の数列が再現できていることを確かめてみてください.
さて,上記のコードを詳しく分析してみることにしましょう.ポイントは「T-4,T+3」の部分です.
実はこれが「成長速度3/4」に対応しています.このことをよく理解するために,
HOJのルールを少し逸脱して,数値引数に分数・小数の計算を許容することにしましょう.
数値引数すべてを4で割ることで,上記のコードは次のようにも書くことができます(HOJ上では動きませんが):
a(T):sa(T-1)
b(T):a(T)rb(T+0.75)
b(0.75)
これを実行すると「a(0.75)ra(1.50)ra(2.25)ra(3.00)ra(3.75)ra(4.50)r」となって,
成長速度0.75が実現されていることがわかると思います.
これをさらに実行する「srssrsssrsssrssssrsssssr…」となりますね.
ちょうど数列の数値を切り上げた回数が実行されることに注意してください
(そのせいで,自分も手計算をよく失敗しますww)
同様に,一般の有理数の成長速度が実現できることがわかると思います.
中途半端な有理数でも使われますし,「成長速度1/4」として
「4連打するものを育てていく」ような方法でも用いられます.
「3,3,3,3,2,2,2,2,1,1,1,1」みたいなのは,普通に再帰して4連打とか思いがちだけど
数値の方法の方が自在に短くかけたりする…奥深いですね~.
なお,再帰と比べた利点としては,(バイト数が短くなる場合があるだけでなく)
「ある程度大きな初項からいきなり始められる」という点もあるでしょうね.
例えば上で紹介したコードで「b(20)」を実行すると,「5,6,7,7,8,9,10,10,…」となるという具合です.
なお,上で紹介した
a(T):sa(T-4)
b(T):a(T)rb(T+3)
b(3)
というコードを1行にしちゃうこともできます.
a(T,U):sa(T-4,U)ra(U,U+3)
Tを利用してsの繰り返しを実現していて,その回数をU側で覚えて増やしていますね.
最初のTの値を調整することで「特殊な初項」のようなことも実現できますね.
このような数値引数を複数使った構文も,上手く使えると意外な短縮につながったりします.
いろいろ試してみると面白いのではないかと思います.
戻る