慶應SFC　環境情報学部　情報入試　2016年　大問Ⅳ　過去問解説

(ア)
nに1から何個か代入してみて探る。

f(1)=f(0)+1=0+1=1
f(2)=f(1)=1
f(3)=f(2)+1=2
f(4)=f(2)=1
f(5)=f(2)+1=2
f(6)=f(3)=2
f(7)=f(3)+1=3
f(8)=f(4)=1

ここまで代入すると
1→0001
2→0010
3→0011
4→0100
5→0101
6→0110
7→0111
8→1000
だから、nを2進数で表したときの1の個数だと分かる。

(イ)
fをアルゴリズムにすればいいのだから、(ア)の式をそのままアルゴリズムにする。

まずaは、出力値だと見当がつく。
aを初期化し、最後に出力するものだとしないとaの存在の意味が見つからない。
よって
f(0)=0
より、初めに変数aの値を0にする。

条件n=0が成り立たない間、帰納的に処理Aを繰り返す。(ア)の計算方法で分かる通り、nの値を始め入力値として、どんどん小さくしていき、遡ればいい。

もしnが奇数なら処理Bを実行する。
nの値をにする。
aの値を1増やす。

もしnが奇数でないなら処理Cを実行する。
nの値をにする。

そしてn=0になるまでnを小さくして遡っていき、結果としてaの値を出力するのである。

(ウ)
任意のnについて、有限回の繰り返しで終了するということは、数列の値がだんだん小さくなり、必ず0になるということ。
このことを念頭において必要な文章を選択していけばいい。
つまりという数列が(9)が成り立たせることを示せばいい。

0以上の整数からなる数列であることは(2)と(4)から示せる。
(2)が成り立つことは自明。
(4)は、(イ)の処理をみれば成り立つことが分かる。

がだんだん小さくなるということは(6)から示せる。
(6)は、(イ)の処理を見れば成り立つことが分かる。