トップ› 九州大学› 2001年› 文系第8問

九州大学 2001年文系第8問解説

方針・初手

与えられたアルゴリズム（算法）の変数の変化を順を追ってトレースし、規則性を数式で表すことが方針となる。 (1)は問題の指示通りに愚直に計算を進め、アルゴリズムの動作を把握する。(2)はこのアルゴリズムにおける「不変量」を数学的帰納法（あるいは漸化式的な関係）を用いて証明する問題であり、$i$ が偶数の場合と奇数の場合で分けて計算する。(3)は(2)で証明した不変量を利用して、最終的な出力値である $Ans$ を求める。

解法1

(1)

1周目の(b)における各値は $i=100, j=n, k=0$ である。

2周目への移行を考える。 $i=100$ は偶数であるため、(c)の条件を満たさず $k$ の値は変わらない。すなわち $k=0$。 (d)より、$i = [100/2] = 50$ となる。 (e)より、$j = 2 \times n = 2n$ となる。よって、2周目の(b)における値は $i=50, j=2n, k=0$ である。

3周目への移行を考える。 $i=50$ は偶数であるため、(c)の条件を満たさず $k=0$ のまま。 (d)より、$i = [50/2] = 25$ となる。 (e)より、$j = 2 \times 2n = 4n$ となる。よって、3周目の(b)における値は $i=25, j=4n, k=0$ である。

4周目への移行を考える。 $i=25$ は奇数であるため、(c)の条件を満たし、$k = k+j = 0+4n = 4n$ となる。 (d)より、$i = [25/2] = 12$ となる。 (e)より、$j = 2 \times 4n = 8n$ となる。よって、4周目の(b)における値は $i=12, j=8n, k=4n$ である。

(2)

ある周回（$x$周目とする）の(b)における $i, j, k$ の値をそれぞれ $i_x, j_x, k_x$ とし、次の周回（$x+1$周目）の(b)における値を $i_{x+1}, j_{x+1}, k_{x+1}$ とする。 $i_x$ が偶数の場合と奇数の場合に分けて、$i_{x+1} j_{x+1} + k_{x+1}$ の値を計算する。

(i) $i_x$ が偶数の場合 $i_x = 2q$（$q$ は自然数）とおける。 $i_x$ は偶数なので(c)の条件を満たさず、$k_{x+1} = k_x$ である。 (d)より、$i_{x+1} = [2q/2] = q = \frac{i_x}{2}$ である。 (e)より、$j_{x+1} = 2j_x$ である。これらを用いて計算すると、

$$\begin{aligned} i_{x+1} j_{x+1} + k_{x+1} &= \frac{i_x}{2} \cdot 2j_x + k_x \\ &= i_x j_x + k_x \end{aligned}$$

となる。

(ii) $i_x$ が奇数の場合 $i_x = 2q+1$（$q$ は0以上の整数）とおける。 $i_x$ は奇数なので(c)の条件を満たし、$k_{x+1} = k_x + j_x$ である。 (d)より、$i_{x+1} = [(2q+1)/2] = q = \frac{i_x - 1}{2}$ である。 (e)より、$j_{x+1} = 2j_x$ である。これらを用いて計算すると、

$$\begin{aligned} i_{x+1} j_{x+1} + k_{x+1} &= \frac{i_x - 1}{2} \cdot 2j_x + (k_x + j_x) \\ &= (i_x - 1)j_x + k_x + j_x \\ &= i_x j_x - j_x + k_x + j_x \\ &= i_x j_x + k_x \end{aligned}$$

となる。

(i), (ii)より、いずれの場合も $i_{x+1} j_{x+1} + k_{x+1} = i_x j_x + k_x$ が成り立つ。したがって、$i \times j + k$ の値は周回を経ても変化せず、1周目から最後まで一定である。（証明終）

(3)

1周目の(b)における各値は $i=m, j=n, k=0$ であるから、このときの $i \times j + k$ の値は、

$$m \times n + 0 = mn$$

である。

(2)で証明した通り、$i \times j + k$ の値は常に一定であるため、アルゴリズムが終了する時点でもこの値は保たれる。終了する条件は(b)より $i=1$ となったときであり、このときの $j, k$ の値をそれぞれ $j_f, k_f$ とすると、不変量について次が成り立つ。

$$1 \times j_f + k_f = mn$$

すなわち、

$$k_f + j_f = mn$$

である。アルゴリズムは $i=1$ のとき $Ans = k + j$ として終了するので、最終的に出力される値は、

$$Ans = k_f + j_f = mn$$

となる。

解説

プログラミングやアルゴリズムの基礎である「ループ不変量（Loop Invariant）」の概念を数学の問題に落とし込んだ出題である。このアルゴリズムは「ロシア農民の掛け算」として知られており、2進数展開を利用して掛け算を足し算と2倍・半分にする操作だけで実現する手法である。 (1)での具体的なトレースを通じて(b)から(f)の処理の流れを正確に掴むことができれば、(2)の場合分けも自然に立式できる。(3)は(2)の誘導に乗り、初期状態の値と終了時の状態を等値するだけで容易に求まる。