7筑波大学 2002年 数学 第7問解答・解説

流れ図で出力直前の値を $r_{i-1}$ とすると、 $$\displaystyle c_i= \begin{cases} 1 &(r_{i-1}\ge\frac12),\\ 0 &(r_{i-1}<\frac12), \end{cases} \qquad r_i=2r_{i-1}-c_i.$$ したがって $r_i$ は次の桁に進むための残りであり、$r_i=0$ になると次の反復の冒頭で終了する。

(1) $\displaystyle a=\frac14$ では $\displaystyle r_0=\frac14$ から $\displaystyle c_1=0,\ r_1=\frac12$、続いて $c_2=1,\ r_2=0$ となる。よって $(c_1,c_2)=(0,1)$。 $\displaystyle a=\frac38$ では $\displaystyle r_0=\frac38$ から $$\displaystyle (c_1,r_1)=\left(0,\frac34\right),\quad (c_2,r_2)=\left(1,\frac12\right),\quad (c_3,r_3)=(1,0).$$ となる。よって $(c_1,c_2,c_3)=(0,1,1)$。

(2) $\displaystyle a=\frac1{10}$ の残りは $$\displaystyle \frac1{10}\to\frac15\to\frac25\to\frac45\to\frac35\to\frac15\to\cdots$$ と進み、それぞれの状態で出る桁は $0,0,0,1,1,0,0,1,1,\ldots$ となる。残り $\displaystyle \frac15$ に戻るため終了せず、$c_2$ 以降で0011が繰り返される。

(3) 出力を $1,0,1,1$ として残りを0にする初期値は、逆向きに $$\displaystyle r_{i-1}=\frac{c_i+r_i}{2},\qquad r_4=0$$ を使うと $$\displaystyle r_3=\frac12,\quad r_2=\frac34,\quad r_1=\frac38,\quad r_0=\frac{1+\frac38}{2}=\frac{11}{16}.$$ 実際に順に $1,0,1,1$ が出て $r_4=0$ となる。

(4) $r_N=0$ から逆向きに $$\displaystyle r_{i-1}=\frac{c_i+r_i}{2}\quad(i=N,N-1,\ldots,1)$$ とすれば $$\displaystyle r_0=a=\sum\limits _{i=1}^{N}\frac{c_i}{2^i}$$ を計算できる。$C(N)=0$ なら $r_{N-1}=0$ となり、N番目を出す前に終了するので解はない。$C(N)=1$ なら $0<a<1$ であり、与えた全桁を出した直後に残りが0になる。次のBASICは桁が0または1であることも確認する。

10 IF N < 1 THEN GOTO 200
20 FOR I = 1 TO N
30 IF C(I) <> 0 AND C(I) <> 1 THEN GOTO 200
40 NEXT I
50 IF C(N) <> 1 THEN GOTO 200
60 A = 0
70 FOR I = N TO 1 STEP -1
80 A = (C(I) + A) / 2
90 NEXT I
100 PRINT A
110 END
200 PRINT "NO SOLUTION"
210 END