基本情報技術者 2011年 秋期 午後 問09
次のCプログラムの説明及びプログラムを読んで、設問1，2に答えよ。
〔プログラム1の説明〕
二つの整数x, y (0<x<y)を受け取り、x/yの値を10進小数として出力するプログラムである。
(1) 関数printRationalの引数は、次のとおりである。ここで、引数の値に誤りはないものとする。
x： 分子を表す正の整数
y： 分母を表す正の整数
ただし、x/yは有限小数（小数点以下の桁数が有限桁である小数）であり、循環小数（小数部のある桁以降で、同じ数字の列が無限に繰り返される小数）ではないものとする。
(2) 次の手順でx/yを10進小数として出力する。
① “0.”を出力する。
② xが0になるまで、次の③、④を繰り返す。
③ xを10倍した値をyで割った商を出力する。
④ xを10倍した値をyで割った余りを新たにxとする。
設問1：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
(1) プログラム1の行番号7では小数点以下の各桁の数字を出力している。この行を“putchar('0' + ( x / y * 10));”に変えるとa。
(2) printRational(3, 8)を実行した場合、行番号6の条件判定が2回目に行われるときのxの値はbであり、プログラムが終了するまでに、行番号6の条件判定はc回行われる。
aに関する解答群
ア：乗算が除算よりも先に実行されるが、正しい値が出力される
イ：乗算が除算よりも先に実行され、正しい値が出力されない
ウ：除算が乗算よりも先に実行されるが、正しい値が出力される
エ：除算が乗算よりも先に実行され、正しい値が出力されない
b, cに関する解答群
ア：0
イ：1
ウ：2
エ：3
オ：4
カ：5
キ：6
ク：7
ケ：8
コ：9
模範解答
a：エ、b：キ、c：オ
解説
解答の導き方
この設問では、式の計算順序と、プログラムが小数の各桁をどのように求めているかを確認します。
(1) 式を変更した場合
行番号7の元の式は、 の順に計算して、次の小数の桁を求めています。 と は整数なので、割り算の結果も整数になる整数除算（小数部分を切り捨てる割り算）です。
変更後の「putchar('0' + ( x / y * 10));」では、 と の優先順位は同じです。同じ優先順位の演算子は左から順に計算するため、式は の順に計算されます。
問題文には とあります。したがって、整数除算では です。その後に を計算しても結果は なので、出力される文字は「0」となり、正しい小数の桁にはなりません。よって、除算が乗算より先に実行され、正しい値が出力されない場合を選びます。
(2) printRational(3, 8) の実行
行番号7では、 の商を出力します。行番号8では、 の余りを次の計算に使うため、 に入れます。
ここで、 は割り算の余りを求める演算です。1回目の計算後に は6になるので、行番号6の条件判定が2回目に行われるときの値は6です。
また、 が0になった後も、繰返しを終えるために行番号6の条件をもう一度確認します。その確認では条件が偽になります。そのため、条件判定は合計4回です。
誤りやすいポイント
- と は、 の方が先に計算されるわけではありません。優先順位が同じなので、左から順に計算します。
- と が整数のとき、 は整数除算になります。たとえば は です。
- 行番号6の条件判定回数には、繰返しの最後に条件が偽になる判定も含めます。繰返しの処理が3回でも、条件判定は4回です。
- 行番号8で余りを次の に入れることで、次の小数の桁を計算できます。商だけでなく余りも追うことが大切です。
FAQ
Q: なぜ行番号8では余りを使うのですか？
A: 余りを次の にすることで、次の桁を計算できます。たとえば、最初に を計算すると商は3、余りは6です。この6を使って、次の桁を求めます。
A: 余りを次の にすることで、次の桁を計算できます。たとえば、最初に を計算すると商は3、余りは6です。この6を使って、次の桁を求めます。
Q: 条件判定が4回なのに、出力される桁が3桁なのはなぜですか？
A: 出力するのは、条件が真になった3回だけです。4回目は なので条件が偽になり、繰返しを終える判定だけを行います。
A: 出力するのは、条件が真になった3回だけです。4回目は なので条件が偽になり、繰返しを終える判定だけを行います。
Q: が0になった後、なぜ繰返しを終えるのですか？
A: が0なら、その後に求める桁がありません。問題文の手順では、 が0になるまで処理を繰り返します。
A: が0なら、その後に求める桁がありません。問題文の手順では、 が0になるまで処理を繰り返します。
関連キーワード: 演算子の優先順位、左結合、整数除算、剰余、繰返し条件
設問2：
問題文を見る 次の説明を読み、プログラム2中のに入れる正しい答えを、解答群の中から選べ。
x/yが循環小数となるxとyを引数に指定して関数printRationalを実行した場合、ある桁以降で同じ数字の列を無限に繰り返し出力し続け、プログラムは終了しない。この繰り返し出力される同じ数字の列を循環節と呼ぶ。最初に現れる循環節を “ [ ” と “ ] ” で囲んで出力するプログラムを作成した。
〔プログラム2の説明〕
(1) 関数recurringDecimalの引数は、次のとおりである。ここで、引数の値に誤りはないものとする。
x： 分子を表す正の整数
y： 分母を表す正の整数
(2) x/yの値によって次のように場合分けを行い、それぞれ別の様式の小数点数を出力する。
① 小数点以下100桁までに割り切れる場合
小数点数をそのまま出力する。例えば、recurringDecimal(1, 8)を実行した場合、次のように出力する。
0.125
② 小数点以下100桁までの間に循環節がある場合
最初の循環節の直前までの小数点数を出力し、その後に循環節の数字の列を“[”と“]”で囲んで出力する。例えば、recurringDecimal(3, 22)を実行した場合、次のように出力する。
0.1[36]
③ その他の場合
小数点以下100桁までの小数点数を出力し、その後に“...”を続けて出力する。例えば、recurringDecimal(19, 131)を実行した場合、次のように出力する。
0.1450381679389312977099236641221374045801526717557251908396946564885496183206106870229007633587786259...
(3) 関数recurringDecimalは、x/yの値によって出力様式を決める部分と小数点数を出力する部分の二つに分かれている。
(4) x/yの値によって出力様式を決める手順は、次のとおりである。
① 大きさ100の配列xHistoryと変数riを用意する。
② riを0とする。
③ xHistory[ri]にxを格納し、riを1増やす。
④ xを10倍した値をyで割った余りを新たにxとする。
⑤ xが0になった場合、出力様式は(2)の①とする。
⑥ xと同じ値をもつxHistory[i] (0≦i<ri) があるかどうかを調べる。
⑦ 同じ値をもつものがある場合、出力様式は(2)の②とする。このとき、x/yの値の小数点以下第i+1位から第ri位までの数字の列が最初の循環節となる。
⑧ 同じ値をもつものがない場合、riが100以上であれば出力様式は(2)の③とする。そうでなければ、③に戻る。
d, eに関する解答群
ア：i == 0
イ：i < DIGITMAX
ウ：i < ri
エ：i >= 0
オ：ri < DIGITMAX
カ：ri > 0
キ：startRepeat == -1
ク：startRepeat >= 0
ケ：startRepeat > i
fに関する解答群
ア：i == startRepeat
イ：i == startRepeat + 1
ウ：i == startRepeat - i
エ：i < startRepeat
オ：startRepeat < 0
カ：startRepeat >= 0
gに関する解答群
ア：x * 10 / y
イ：xHistory[i] * 10 / y
ウ：xHistory[ri] * 10 / y
エ：xHistory[startRepeat] * 10 / y
オ：'0' + x * 10 / y
カ：'0' + xHistory[i] * 10 / y
キ：'0' + xHistory[ri] * 10 / y
ク：'0' + xHistory[startRepeat] * 10 / y
模範解答
d：キ、e：ウ、f：ア、g：カ
解説
解答の導き方
この問題では、余りの並びを調べて循環節の開始位置を見つけ、その位置に「[」を出力します。順に考えていきます。
1. xHistoryには、各桁を求める前の余りを保存します
分数の小数部分は、現在の余りにを掛けて分母で割ると、次の桁と新しい余りが求まります。
たとえば、現在の余りが、分母がなら、次の桁はの商です。新しい余りはです。ここで「余り」は、割り算で割り切れずに残る値です。
xHistoryには、次の桁を求める前の余りを保存します。riは、これまでに保存した個数であり、同時に、これまでに求めた小数点以下の桁数でもあります。
2. dは、循環節が見つかっていない間だけ処理を続ける条件です
関数の最初ではstartRepeatが-1に設定されています。余りの重複が見つかると、startRepeatに重複した余りの位置を設定します。
そのため、循環節がまだ見つかっていない間だけwhile文を続ける条件は、startRepeat == -1です。dにはキが入ります。
3. eは、保存済みの余りだけを調べる条件です
余りをxHistory[ri]に保存してriを1増やした後、添字が0からri-1までの範囲にある値と、更新後のxを比べます。
配列（複数の値を順番に保存する場所）で、値の位置を示す番号を添字といいます。今回、すでに値が入っているのは添字0からri-1までです。まだ値を保存していない位置まで調べないようにする条件はi < riです。eにはウが入ります。
4. 余りが再び現れた位置から循環節が始まります
余りが以前と同じ値に戻ると、その余り以降の計算は同じ順番で繰り返されます。つまり、同じ余りになる直前から始まる数字の並びが循環節です。
例としてrecurringDecimal(3, 22)を考えます。
最後に余りが8になったとき、xHistory[1]に保存された余りと一致します。したがって循環節は小数点以下第2位から始まり、出力は0.1[36]になります。
このように、循環節が始まる位置はstartRepeatに保存されます。小数点以下の桁を出力するとき、iがその位置と一致したところで「[」を出力すればよいので、fにはi == startRepeatが入ります。選択肢はアです。
5. gは、保存した余りから各桁の文字を作ります
小数点数の出力部分では、すでに計算が終わっています。現在のxは最後の余りになっているため、そこから過去の各桁を求めることはできません。そのため、保存しておいたxHistory[i]を使います。
小数点以下の桁の値は、xHistory[i] * 10 / yで求まります。ただし、この値は数字の値であり、そのままでは数字の文字として出力できません。文字の「0」に桁の値を加えることで、「0」から「9」までの対応する数字の文字になります。
したがって、gには「'0' + xHistory[i] * 10 / y」に当たるカが入ります。
誤りやすいポイント
- dをx > 0だけで判断しないようにします。余りが0でなくても、以前と同じ余りが現れた時点で循環節が見つかっています。startRepeat == -1は、その循環節がまだ見つかっていないことを表します。
- eの範囲はi < riです。riは保存済みの個数なので、添字の範囲は0からri-1までです。
- 循環節の開始位置は、重複した余りが保存されていた位置です。重複が見つかった後に求めた桁からではありません。
- 出力時のxは計算途中の余りではなく、最後に更新された値です。各桁を出力するにはxHistory[i]を使います。
- 桁の値を出力するときは、数値に「'0'」を加えて数字の文字にします。数値の桁だけでは、文字としての数字を出力できません。
FAQ
Q: なぜ余りを保存しておくのですか？
A: 同じ余りが再び現れたかどうかを調べるためです。同じ余りからは同じ桁と次の余りが生まれるので、その後の数字が繰り返されると分かります。また、保存しておけば、出力時に各桁をもう一度求められます。
A: 同じ余りが再び現れたかどうかを調べるためです。同じ余りからは同じ桁と次の余りが生まれるので、その後の数字が繰り返されると分かります。また、保存しておけば、出力時に各桁をもう一度求められます。
Q: xが0になった場合も、循環節を探しますか？
A: 探しません。余りが0になれば、その後の桁はなく、小数は有限で終わります。while文の条件でx > 0を確認し、処理を終了します。
A: 探しません。余りが0になれば、その後の桁はなく、小数は有限で終わります。while文の条件でx > 0を確認し、処理を終了します。
Q: 小数点以下100桁までに循環節が見つからなかった場合はどうなりますか？
A: startRepeatが-1のままで、x > 0かつri >= DIGITMAXであれば、出力済みの小数点以下100桁の後に「...」を出力します。
A: startRepeatが-1のままで、x > 0かつri >= DIGITMAXであれば、出力済みの小数点以下100桁の後に「...」を出力します。
関連キーワード: 剰余、整数除算、配列、循環小数、循環節
