平成21年度 春期 午前 問7
アルゴリズム
再帰に関する問題
文字列を引数とする関数 len, first, butfirst を用いて，関数 comp を再帰的に定義した。comp(“11”, “101”) を呼び出したとき，返されるものはどれか。
〔関数の定義〕
- len(S) ： 文字列 S の長さを返す。S が空文字列のときは 0 を返す。
- first(S) ： 文字列 S の先頭の 1 文字の ASCII コードを返す。S が空文字列のときはエラーを返す。
- butfirst(S) ： 文字列 S の先頭の 1 文字を除いた残りの文字列を返す。S が空文字列のときはエラーを返す。
comp(A, B)
begin
if len(A) ＝ 0 and len(B) ＝ 0 then return 0;
if len(A) ＝ 0 and len(B) ≠ 0 then return 1;
if len(A) ≠ 0 and len(B) ＝ 0 then return −1;
if first(A) ＜ first(B) then return 1;
if first(A) ＞ first(B) then return −1;
return comp(butfirst(A), butfirst(B));
end- ア−1
- イ0
- ウ1
- エエラー
答えと解説を見る
✓ これが正解ア−1
解説
最初に異なる文字を比べて、大きい側に −1 が返ります。
この再帰関数は、二つの文字列を先頭から 1 文字ずつ比べて大小を判定する仕組みです。両方の長さがゼロなら 0、片方だけが空なら空でないほうを判定に反映し、先頭の ASCII コードに差があればその向きに応じて 1 か −1 を返します。差がなければ先頭を 1 文字ずつ削って残りを同じ手順で比べ直します。この考え方で 11 と 101 を並べると、まず先頭の 1 と 1 が同じなので判定が持ち越され、先頭を落として 1 と 01 の比較に進みます。この段で先頭は 1 と 0 で、比べる相手のほうがコードの小さい文字になっています。関数の定義では、先頭が相手より大きいときに −1 を返すよう定めてあります。したがって、返される値は −1 になります。
ほかの選択肢はなぜ違うのか
- イ0：0 が返るのは、両方の文字列が同時に空になったときと定められています。今回の入力は空同士に到達する前に大小の判定が確定するため、この結末には至りません。
- ウ1：1 が返るのは、先頭のコードが相手より小さいと判定されたときか、片方だけが空でもう片方が残っているときです。ここでの比較では相手のほうがコードが小さくなっており、条件がそろっていません。
- エエラー：エラーが返るのは、空の文字列に対して先頭や先頭を除いた残りを取り出す操作を呼び出したときです。この関数は先に長さを確かめてから比較へ進む書き方になっており、その分岐には入りません。
出典：平成21年度 春期 応用情報技術者試験 午前 問7
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）