有理数の成長速度

いきなりですが次の規則を実装する方法を考えてみましょう.

[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などで実行して, 上記の数列が再現できていることを確かめてみてください.

rational_1.png

さて, 上記のコードを詳しく分析してみることにしましょう.
ポイントは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,…

となるという具合です.

rational_2.png

上で紹介した

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の値を調整することで「特殊な初項」のようなことも実現できますね.
このような数値引数を複数使った構文も, 上手く使えると意外な短縮につながったりします.
いろいろ試してみると面白いのではないかと思います.


執筆:mas


添付ファイル: filerational_2.png 109件 [詳細] filerational_1.png 114件 [詳細]

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