たらい回し関数(4) - エレファント・ビジュアライザー調査記録

たらい回し関数(以下の $t$ または tarai)の呼び出しが重なっている(呼び出しが終了する前に呼び出しが行われる)回数の最大値を「呼び出しの深さ」と呼ぶことにします(以下の depth)。

        public static string Test()
        {
            int count = 0;
            int depth = 0;
            float tarai(float x, float y, float z, int d)
            {
                count++;
                depth = d + 1 > depth ? d + 1 : depth;
                if (x <= y)
                {
                    return y;
                }
                else
                {
                    return tarai(tarai(x - 1, y, z, d + 1), tarai(y - 1, z, x, d + 1), tarai(z - 1, x, y, d + 1), d + 1);
                }
            }
            return $"{tarai(12, 6, 0, 0)}, count = {count}, depth = {depth}";
        }

$\mathbb{R}$ を実数全体の集合、 $\mathbb{N}$ を自然数(負ではない整数)全体の集合)とします。 $x, y \in \mathbb{R}$ に対して $x \setminus y = \min\{m \in \mathbb{N} \mid x-m \leq y\}$ とおきます。 $x, y, z \in \mathbb{R}$ に対して $x, y, z$ の「幅」 $\delta(x, y, z)$ を $\delta(x, y, z) = (x \setminus \min \{ x, y, z \}) + (y \setminus \min \{ x, y, z \}) + (z \setminus \min \{ x, y, z \})$ と定義します。 $x, y, z$ の「幅」と「呼び出し深さ」(depth)、「呼び出しの回数」(count)の関係を考えます。

上記の C# のコードを while を使って書き直します。

        public static string Test()
        {
            int count = 0;
            int depth = 0;
            float tarai(float x, float y, float z, int d)
            {
                count++;
                d++;
                depth = d > depth ? d : depth;
                while (x > y)
                {
                    float a = tarai(x - 1, y, z, d);
                    float b = tarai(y - 1, z, x, d);
                    float c = tarai(z - 1, x, y, d);
                    (x, y, z) = (a, b, c);
                    count++;
                    d++;
                    depth = d > depth ? d : depth;
                }
                return y;
            }
            return $"{tarai(12, 6, 0, 0)}, count = {count}, depth = {depth}";
        }

while の中の繰り返しの回数を考えます。

$x > y$ とします。

「幅」が $\delta(x, y, z) - 1$ 以下のときの「呼び出しの深さ」は $d$ 以下、「呼び出しの回数」は $c$ 以下であるとします。

「幅」が $\delta(x, y, z) - 1$ 以下である $x', y', z'$ に対して
$\begin{eqnarray*} t(x', y', z') & = & \begin{cases} y' & (x' \leq y') \\ z' & (x' > y', & y' \leq z') & \cdots (*)\\ x' & (x' > y', & y' > z') \\ \end{cases} \\ \end{eqnarray*}$
が成り立っているとします。

(1) $t(x-1, y, z) = x - 1$ のとき

(*)より $t(x-1, y, z) = x-1, y, \operatorname{or} z$ で、 $t(x-1, y, z) = x - 1$ となるのは $x -1 > y > z$ の場合となります。このとき
$\begin{eqnarray*} t(y-1, z, x) & = & \begin{cases} z & (y-1 \leq z) \\ x & (y-1 > z, & z \leq x) \\ y-1 & (y-1 > z, & z > x) \\ \end{cases} \\ & = & \begin{cases} z & (y-1 \leq z) \\ x & (y-1 > z) \\ \end{cases} \\ \end{eqnarray*}$
$\begin{eqnarray*} t(z-1, x, y) & = & \begin{cases} x & (z-1 \leq x) \\ y & (z-1 > x, & x \leq y) \\ z-1 & (z-1 > x, & x > y) \\ \end{cases} \\ & = & x \end{eqnarray*}$
となります。よって $t(x-1, y, z) = x - 1$ のとき $t(y-1, z, x)$ 、 $t(z-1, x, y)$ は $x, z$ のどれかとなります。(*)より $t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y))$ の引数の「呼び出しの深さ」は $d$ 以下、「呼び出しの回数」は $3c$ 以下となります。

(2) $t(y-1, z, x) = y - 1$ のとき

(*)より $t(y-1, z, x) = y-1, z, \operatorname{or} x$ で、 $t(y-1, z, x) = y - 1$ となるのは $y -1 > z > x$ の場合となりますが、 $x > y$ なのでこれは起こりません。

(3) $t(z-1, x, y) = z - 1$ のとき

(*)より $t(z-1, x, y) = z-1, x, \operatorname{or} y$ で、 $t(z-1, x, y) = z - 1$ となるのは $z -1 > x > y$ の場合となります。このとき
$\begin{eqnarray*} t(x-1, y, z) & = & \begin{cases} y & (x-1 \leq y) \\ z & (x-1 > y, & y \leq z) \\ x-1 & (x-1 > y, & y > z) \\ \end{cases} \\ & = & \begin{cases} y & (x-1 \leq y) \\ z & (x-1 > y, & y \leq z) \\ \end{cases} \\ \end{eqnarray*}$
$\begin{eqnarray*} t(y-1, z, x) & = & \begin{cases} z & (y-1 \leq z) \\ x & (y-1 > z, & z \leq x) \\ y-1 & (y-1 > z, & z > x) \\ \end{cases} \\ & = & \begin{cases} z & (y-1 \leq z) \\ x & (y-1 > z, & z \leq x) \\ \end{cases} \\ \end{eqnarray*}$
となります。よって $t(z-1, x, y) = z - 1$ のとき $t(y-1, z, x)$ 、 $t(z-1, x, y)$ は $x, y, z$ のどれかとなります。(*)より $t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y))$ の引数の「呼び出しの深さ」は $d$ 以下、「呼び出しの回数」は $3c$ 以下となります。

(4) それ以外のとき

(1)(2)(3)以外のとき、 $t(x-1, y, z)$ 、 $t(y-1, z, x)$ 、 $t(z-1, x, y)$ は $x, y, z$ のどれかとなります。
$\begin{eqnarray*} a = t(x-1, y, z) & = & \begin{cases} y & (x-1 \leq y, & x > y) \\ z & (x-1 > y, & y \leq z, & x > y) \\ \end{cases} \\ \end{eqnarray*}$
$\begin{eqnarray*} b = t(y-1, z, x) & = & \begin{cases} z & (y-1 \leq z, & x > y) \\ x & (y-1 > z, & z \leq x, & x > y) \\ \end{cases} \\ \end{eqnarray*}$
$\begin{eqnarray*} c = t(z-1, x, y) & = & \begin{cases} x & (z-1 \leq x, & x > y) \\ \end{cases} \\ \end{eqnarray*}$