土用ウナギの日

土用の丑の日に限らないが，よく食の老舗で「江戸時代から継ぎ足し継ぎ足ししてきたタレ」とかいう話があり，そのたびに，「ばかか」と思う

まあ，ウナギのタレがどういう単位で存在するのかはさておき，たとえば単位不明で n = 1000000 としよう。毎日毎日そのうちの千分の1である m = 1000 を使い，そのぶんだけ新しいものを補充するとしよう。

当初，n 個の要素は全て 1 を持っている。a = rep(1, n)

毎日毎日そのうちの r = sample(n, m, replace=TRUE) の要素が新しいものに置き換えられる。

つまり，使われた要素は 1 から 0 に変えられる。a[r] = 0

一日が終わったとき，当初の要素が幾つあるかは sum(a) でわかる。

というようなシミュレーションプログラムが以下のようになるであろう。

n = 1000000
m = 1000
a = rep(1, n)
day = 9999
conc = integer(day)
for (i in seq_len(day)) {
    r = sample(n, m, replace=TRUE)
    a[r] = 0
    t = sum(a)
    conc[i] = t
    cat(sprintf("day %3i, parts = %i\n", i, t))
}
plot(1:day, conc, type="l", xlab="day")

day   1, parts = 999000
day   2, parts = 998000
day   3, parts = 997003
day   4, parts = 996006
day   5, parts = 995011
　　：
day 1101, parts = 332353
day 1102, parts = 332005
day 1103, parts = 331680
day 1104, parts = 331357
day 1105, parts = 331023
　　：
day 9995, parts = 50
day 9996, parts = 50
day 9997, parts = 50
day 9998, parts = 50
day 9999, parts = 50

図にすると，以下のよう。見事に指数関数的減衰。

27年ほど経つと濃度は 0.00005 になる。

もし，一日に 1/100 を入れ替えるとすると，1000日（約2年9ヶ月）で 0.00005 になる。

江戸時代からだと，ほとんど1個の分子すら残っていまい。

まあ，「一晩の内に，古いタレが，新しいタレを教育して昔ながらの味になる」なんて，おとぎ話があるのかもしれないけど。

トリボナッチ数列

「再帰関数と非再帰関数」，「事象が連続発生するまでの試行回数」にも出てきたトリボナッチ数列だが，

「n 階段があるとき，1段昇る，2段昇る，3段昇るのどれかを選択して昇るとき何通りの昇り方があるか」という設問がされることもある。

よく，「アルゴリズムをわかりやすく表現できる再帰プログラム」の例としても出てくるのが以下のプログラム。フィボナッチ数列の拡張ということだ。

def step(n):
    if n == 0:
        return 1
    if n < 0:
        return 0
    return step(n-1) + step(n-2) + step(n-3)

でも，これは相当スタックも喰うし，実行時間も馬鹿にならない。

import time
s = time.time()
for i in range(30):
    print(i, step(i))
print(time.time()-s)

30 項計算するのに 46秒も掛かる。

これを再帰ではないプログラムにすると，（これもフィボナッチ数列の非再帰的求め方のプログラムだが）

s = time.time()
a, b, c, = 1, 1, 2
for i in range(3, 30):
    a , b, c = b, c, a + b + c
    print(i, c)
print(time.time()-s)

当たり前だが，わずか 0.0018 秒で終わる。