基本情報技術者 ミスノート 20180916

• 問題文読み落とし

問題文

次の規則に従って配列の要素A[0],A[1],…A[9]に正の整数kを格納する。

16, 43, 73, 24, 85を順に格納したとき、85が格納される場所はどれか。

ここで、x mod yはxをyで割った剰余を返す。

また、配列の要素は全て0に初期化されている。

→ここを見落とした。配列の要素はすべて0に初期化ということは、A[?]は最初はすべて0ということを示している。

[規則]

（１）A[k mod 10]=0ならば、k→A[k mod 10]とする。

→A[k mod 10]は数字を格納する箱のようなもの。

　それに対してkは数字そのもの。

　初見で勘違いしていたポイントは、A[k mod 10]=0という式の意味。

　自分は、kを10で割った余り(剰余)が0という意味かと思った。

　しかし、実際はkを10で割った剰余が要素番号の箱に格納されている数字が0という意味だった。

　大事なのは、箱の番号ではなく箱に格納されている数字を指している点。

　k→A[k mod 10]は数字kをA[k mod 10]という箱に格納する行為を指している。

（２）（１）で格納できないとき、A[(k+1) mod 10]=0ならば、

　k→A[(k+1) mod 10]とする。

→kを格納しようとした箱の中にすでに初期値の0以外が入っていたら、箱の番号を変更して入れる。

（３）（２）で格納できないとき、A[(k+4) mod 10]=0ならば、

　k→A[(k+4) mod 10]とする。

→同様に、kを格納しようとした箱の中にすでに初期値の0以外が入っていたら、箱の番号を変更して入れる。

解答

16は10で割ると剰余が6。A[6]の箱には初期値の0が入っているので、

16はA[6]に入る。

43は10で割ると剰余が3。A[3]の箱には初期値の0が入っているので、

43はA[3]に入る。

73は10で割ると剰余が3。A[3]の箱には43が入っているので、

（２）を検討。

73+1=74を10で割ると剰余が4。A[4]の箱には初期値の0が入っているので、

73はA[4]に入る。

24は10で割ると剰余が4。A[4]の箱には73が入っているので、

（２）を検討。

24+1=25を10で割ると剰余が5。A[5]の箱には初期値の0が入っているので、

25はA[5]に入る。

85は10で割ると剰余が5。A[5]の箱には25が入っているので、（２）を検討。

85+1=86を10で割ると剰余が6。A[6]の箱には16が入っているので、（３）を検討。

85+4=89を10で割ると剰余が9。A[9]の箱には初期値の0が入っているので、85はA[9]に入る。