九州大学 2001年 理系 第6問 解説

方針・初手

与えられた手順（アルゴリズム）に従って変数の値がどのように変化するかを追跡する問題である。 (1) は具体例を用いたトレースであり、指示通りに計算を実行して規則性をつかむ。 (2) はループの各周回における状態の変化を一般化して立式する。手順(c)での分岐に着目し、$i$ が偶数の場合と奇数の場合で分けて、次の周の(b)における $ij+k$ の値がどうなるかを計算する。 (3) は(2)で示した「不変量」の性質を利用し、1周目の初期状態と終了状態の値を等号で結ぶ。 (4) は $m=3 \cdot 2^l$ のときの $i$ の推移を追い、終了条件 $i=1$ になるまでの手順(d)の実行回数をカウントする。

解法1

(1)

$m=100$ のとき、各周の(b)における $i, j, k$ の値をトレースする。

1周目の(b): $i=100, j=n, k=0$ $i \neq 1$ なので先へ進む。 (c) $i$ は偶数なので $k$ はそのまま。 (d) $i = [100/2] = 50$ (e) $j = 2n$

2周目の(b): $i=50, j=2n, k=0$ $i \neq 1$ なので先へ進む。 (c) $i$ は偶数なので $k$ はそのまま。 (d) $i = [50/2] = 25$ (e) $j = 2 \cdot 2n = 4n$

3周目の(b): $i=25, j=4n, k=0$ $i \neq 1$ なので先へ進む。 (c) $i$ は奇数なので $k = 0 + 4n = 4n$ (d) $i = [25/2] = 12$ (e) $j = 2 \cdot 4n = 8n$

4周目の(b): $i=12, j=8n, k=4n$

(2)

$p$ 周目の(b)における $i, j, k$ の値をそれぞれ $i_p, j_p, k_p$ とする。 手順(b)〜(e)を経た次の周（$p+1$ 周目）の(b)における値 $i_{p+1}, j_{p+1}, k_{p+1}$ がどのようになるかを調べる。 手順(e)により、常に $j_{p+1} = 2j_p$ である。

(i) $i_p$ が偶数のとき

$i_p = 2q$ （$q$ は自然数）とおける。 手順(c)により $k_{p+1} = k_p$。 手順(d)により $i_{p+1} = [2q/2] = q = \frac{i_p}{2}$。 このとき、

$$i_{p+1} j_{p+1} + k_{p+1} = \frac{i_p}{2} \cdot 2j_p + k_p = i_p j_p + k_p$$

(ii) $i_p$ が奇数のとき

$i_p = 2q+1$ （$q$ は $0$ 以上の整数）とおける。 手順(c)により $k_{p+1} = k_p + j_p$。 手順(d)により $i_{p+1} = [(2q+1)/2] = q = \frac{i_p - 1}{2}$。 このとき、

$$i_{p+1} j_{p+1} + k_{p+1} = \frac{i_p - 1}{2} \cdot 2j_p + (k_p + j_p) = (i_p - 1)j_p + k_p + j_p = i_p j_p - j_p + k_p + j_p = i_p j_p + k_p$$

(i), (ii) いずれの場合も $i_{p+1} j_{p+1} + k_{p+1} = i_p j_p + k_p$ が成り立つため、式 $i*j+k$ の値は1周目から最後まで一定である。

(3)

(2)の結果より、$i*j+k$ は常に一定であり、その値は1周目の(b)における値に等しい。 1周目の(b)では $i=m, j=n, k=0$ であるから、

$$i*j+k = m \cdot n + 0 = mn$$

終了するとき、手順(b)において $i=1$ となり、$Ans = k+j$ として終了する。 この終了時の(b)においても $i*j+k$ の値は $mn$ に等しいため、

$$1 \cdot j + k = mn$$

よって、$k+j = mn$ であり、$Ans = mn$ となる。

(4)

$i$ の値は手順(d)の $i = [i/2]$ によって更新される。 初期値（1周目の(a)の直後）は $i=3 \cdot 2^l$ である。 $l$ 回 (d) を実行する間、常に $i$ は偶数であり、値は半減していく。

1回実行後: $i = 3 \cdot 2^{l-1}$ 2回実行後: $i = 3 \cdot 2^{l-2}$ $\cdots$ $l$ 回実行後: $i = 3 \cdot 2^0 = 3$

この時点（$l+1$ 周目の(b)）で $i=3$ であり $i \neq 1$ であるため、アルゴリズムは終了せず次のステップへ進む。 $i=3$ は奇数であり、手順(d)の実行はこれで $l+1$ 回目となる。

$l+1$ 回実行後: $i = [3/2] = 1$

この時点（$l+2$ 周目の(b)）で $i=1$ となるため、アルゴリズムは終了する。 したがって、終了するまでに手順(d)を実行する回数は $l+1$ 回である。

解説

本問で扱われているアルゴリズムは、「エジプトの乗法」または「ロシアの乗法」として知られる、2数の積 $m \times n$ を求めるアルゴリズム（ビットシフトと加算による乗算）のモデルである。 (1)で具体例を通してアルゴリズムの挙動を把握させ、(2)でループ不変量（常に変わらない性質）を証明させ、(3)でその不変量を用いてアルゴリズムの目的を導き出すという、コンピュータ科学の基礎を題材とした非常に教育的で綺麗な誘導となっている。 (2)におけるループ不変量の証明では、偶奇による場合分けとガウス記号の処理を正確に記述することがポイントとなる。

答え

(1) 3周目: $i=25, j=4n, k=0$ 4周目: $i=12, j=8n, k=4n$

(2) $p$ 周目の(b)における $i, j, k$ の値をそれぞれ $i_p, j_p, k_p$ とすると、 $i_p$ が偶数のとき、$i_{p+1} j_{p+1} + k_{p+1} = \frac{i_p}{2} \cdot 2j_p + k_p = i_p j_p + k_p$ $i_p$ が奇数のとき、$i_{p+1} j_{p+1} + k_{p+1} = \frac{i_p-1}{2} \cdot 2j_p + k_p + j_p = i_p j_p + k_p$ いずれの場合も値が等しくなるため、一定であることが示された。

(3) $Ans = mn$

(4) $l+1$ 回