九州大学 2001年度 前期日程 第2次学力試験 整数・数列理系数学 第4問(c)

(1)

1周目の(b)では $(i,j,k)=(100,n,0)$ である。$100$ は偶数なので、次の周回では $(i,j,k)=(50,2n,0)$ となる。さらに $50$ も偶数なので、3周目の(b)では $(i,j,k)=(25,4n,0)$ である。ここで $25$ は奇数なので、(c)で $k=4n$ となり、その後 $i=[25\mathrm{/}2]=12$、$j=8n$ となる。したがって4周目の(b)では $(i,j,k)=(12,8n,4n)$ である。

(2)

ある周回の(b)での値を $(i,j,k)$ とする。$i$ が偶数のときは、次の周回で $$i^{\mathrm{\prime }}={\displaystyle \frac{i}{2}},j^{\mathrm{\prime }}=2j,k^{\mathrm{\prime }}=k$$ となるから $$i^{\mathrm{\prime }}{j}^{\mathrm{\prime }}+k^{\mathrm{\prime }}={\displaystyle \frac{i}{2}}\cdot 2j+k=ij+k$$ である。 $i$ が奇数のときは $i=2h+1$ とおける。(c)で $k$ は $k+j$ となり、その後 $$i^{\mathrm{\prime }}=h,j^{\mathrm{\prime }}=2j,k^{\mathrm{\prime }}=k+j$$ となる。したがって $$i^{\mathrm{\prime }}{j}^{\mathrm{\prime }}+k^{\mathrm{\prime }}=2hj+k+j=(2h+1)j+k=ij+k$$ である。

よって、どちらの場合も $ij+k$ は次の周回で変わらない。1周目では $ij+k=mn$ だから、最後まで一定値は $mn$ である。

(3)

終了時は(b)で $i=1$ となっており、$Ans=k+j$ と定められる。このとき $k+j=ij+k$ である。(2)より $ij+k=mn$ だから $Ans=mn$ である。

(4) $m=3\cdot 2^l$ から始める。$i$ が偶数である間は、(d)を1回行うごとに $i$ は半分になる。したがって(d)を $l$ 回行うと $i=3$ となる。次に $i=3$ は奇数なので、(c)を行った後、(d)で $i=[3\mathrm{/}2]=1$ となる。この次に(b)へ戻ると終了する。

したがって(d)を実行する回数は $l+1$ である。

算法を2進法の筆算とみなす。$i$ の最下位桁を1周ごとに読み、
その桁が1なら現在の $j=2^{s}n$ を $k$ へ加える。
終了回数も2進表示の桁移動として数える。

(1)
半減列は $100,50,25,12,\dots$、$j$ は $n,2n,4n,8n,\dots$
である。25が奇数のときだけ $4n$ を加えるので$$(25,4n,0),(12,8n,4n)$$となる。

(2) $$m=\sum _{\nu =0}^s{\epsilon }_{\nu }{2}^{\nu }$$$({\epsilon }_{\nu }=0,1)$ とする。$r$ 回処理した時点で$$i=\sum _{\nu =r}^s{\epsilon }_{\nu }{2}^{\nu -r},j=2^{r}n,k=\sum _{\nu =0}^{r-1}{\epsilon }_{\nu }{2}^{\nu }n\mathrm{.}$$したがって$$ij+k=mn$$で、全周回を通じて一定である。

(3)
終了時は $i=1$ だから$$Ans=k+j=ij+k=mn\mathrm{.}$$(4)
$m=3\cdot 2^l$ は $l$ 回の右桁移動で3になり、
さらに1回で $[3\mathrm{/}2]=1$ になる。したがって(d)の実行回数は$$l+1$$回である。