基本情報技術者 2019年 春期 午後 問09
次のCプログラムの説明及びプログラムを読んで、設問1，2に答えよ。
入力ファイルを読み込んで、文字コードごとの出現回数を印字するプログラムである。
〔プログラムの説明〕
(1) 入力ファイルは、バイナリファイルとして読み込む。入力ファイル中の各バイトの内容（ビット構成）に制約はない。入力ファイル名は、#defineで指定する。
(2) 入力ファイル中の各バイトについて、文字コード（16進数00〜FFで表示する）ごとの出現回数を求めて印字する。印字例を、図1に示す。
(3) 印字様式を次に示す（記号❶、❷、❸は、図1中の記号を指している）。
・1行目に、処理したバイト数を❶の形式で印字する。
・3行目以降に、出現回数とその文字コードを❷の形式で印字する。ただし、文字コードが20〜7Eの場合は、文字コードの後にそれが表す文字（文字は、この冊子の末尾にあるアセンブラ言語の仕様の1.3で規定するもの）を❸の形式で印字する。文字コードは、64行×4列の範囲に、上から下、左から右に文字コードの昇順となるように並べる。
(4) プログラム中で使用している関数fgetc(s)は、ストリームsから1文字を読み込んで返す。ストリームが入力ファイルの終わりに達しているときはEOFを返す。
(5) 入力ファイルのサイズは、long型（32ビットとする）で表現できる数値の範囲を超えないものとする。
設問1：
問題文を見る プログラム中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：cnt - 1
イ：cnt
ウ：cnt + 1
b, cに関する解答群
ア：4
イ：64
ウ：256
エ：i + 4
オ：i + 64
カ：i + 192
模範解答
a：イ、b：カ、c：イ
解説
解答の導き方
この問題では、ファイルを読み込んだバイト数を印字する値と、文字コードを4列に並べるためのループ条件を求めます。
まず、変数cntは、読み込んだバイト数を数えるために使われています。ファイルを読む処理では、1バイト読み込むたびにcntを1増やしています。
読み込みを続けるwhile文は、fgetc(infile) がEOFでない間だけ実行されます。EOF（End Of File：ファイルの終わりを示す値）になったときは、while文の中に入らないため、cntは実際に読み込んだバイト数になります。したがって、処理したバイト数を印字する a にはcntを入れます。選択肢ではイです。
次に、文字コードを印字するループを考えます。問題文には、文字コードを「64行×4列」の範囲に並べるとあります。文字コードは00〜FFなので、全部で256種類あります。 となるため、1行に4種類ずつ印字すれば、すべての文字コードを表示できます。
外側のループではiが0から63まで変わります。各行の最初の文字コードはchr=iです。内側のループではchrを一定間隔で増やし、同じ行の残りの列に印字します。
1行目は、iが0なので、文字コードは0、64、128、192となります。16進数で表すと00、40、80、C0です。次の行ではiが1になり、01、41、81、C1が印字されます。つまり、隣の列へ進むたびに文字コードを64増やします。よって c は64で、選択肢ではイです。
最後の列の文字コードは、最初の文字コードiに192を足した値です。したがって、内側のループが続く条件の上限である b はi + 192となり、選択肢ではカです。条件がchr <= b なので、この上限の値も印字されます。
誤りやすいポイント
- EOFになったときはwhile文の中の処理を行いません。そのため、EOFの分までcntを増やす必要はありません。
- 文字コードを1ずつ増やすと、1行に4列ではなく、連続した文字コードが並びます。隣の列へ進む間隔は64です。
- b は最終列の文字コードです。内側のループでは、iから始めて64ずつ増やすので、最後の値はi + 192です。
- 文字コードは00〜FFの256種類です。64行すべてに4種類ずつ並べると、 種類になります。
FAQ
Q: ファイルが空の場合、cntはどうなりますか？
A: 最初のfgetc(infile) でEOFが返り、while文の中に入りません。そのため、cntは初期値の0のままです。
A: 最初のfgetc(infile) でEOFが返り、while文の中に入りません。そのため、cntは初期値の0のままです。
Q: なぜ文字コードを64ずつ増やすのですか？
A: 1行に4列を作り、各列に00〜3F、40〜7F、80〜BF、C0〜FFの範囲を配置するためです。隣の列へ移ると、文字コードが64ずつ増えます。
A: 1行に4列を作り、各列に00〜3F、40〜7F、80〜BF、C0〜FFの範囲を配置するためです。隣の列へ移ると、文字コードが64ずつ増えます。
Q: 文字コードが20〜7Eのときだけ文字も印字するのはなぜですか？
A: プログラムの条件が、その範囲の文字コードについてだけ文字を印字するようにしているためです。それ以外の文字コードでは、出現回数と文字コードを印字します。
A: プログラムの条件が、その範囲の文字コードについてだけ文字を印字するようにしているためです。それ以外の文字コードでは、出現回数と文字コードを印字します。
関連キーワード: バイナリファイル、EOF、文字コード、配列、ループ、16進数
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。ここで、記述中のbとcには、設問1の正しい答えが入っているものとする。
文字コードを出現回数の降順に並べて印字する処理を追加する。追加した処理による印字例を、図2に示す。印字の様式は、文字コードの並び順を除いて、図1の3行目以降の様式と同じである。同じ出現回数の文字コードは、それらを文字コードの昇順に並べる。
この処理のために、プログラムの行①の直後に、次の宣言を追加する。
int ih, ix, code[256];
さらに、プログラムの行②の位置に、次の整列処理部を追加する。
ここで、整列処理部で使用するSwap(x, y)は、xとyの内容を入れ替えるために用意したマクロである。
整列処理部では、整列対象のデータ数が比較的少なく、また同じ出現回数の文字コードは元の並び順が維持されるので、バブルソートを使用している。
行④のwhile文のブロックを1回実行すると、配列の走査範囲（要素番号0〜ih）中の出現回数の最小値とその文字コードが、要素番号ihの位置に置かれ、配列の走査範囲が1だけ狭められる。これを繰り返して整列を行う。この処理ではwhile文のブロックの実行回数は常にd回となる。
ここで、while文のブロックの1回の繰返しにおいて、行⑥のif文のブロック内の処理が最後に実行されたときのiの値をixとすると、行⑤のfor文のブロックの実行が終了した時点で、配列freqの要素番号e以降の要素の値は整列済みとなっている。これを利用して、整列処理部を表1に示すように変更すれば、while文のブロックの実行回数を減らせる可能性がある。
dに関する解答群
ア：253
イ：254
ウ：255
エ：256
eに関する解答群
ア：256 - ix
イ：ix - 1
ウ：ix
エ：ix + 1
fに関する解答群
ア：行③
イ：行④
ウ：行⑤
gに関する解答群
ア：ih = ix - 1
イ：ih = ix
ウ：ih = ix + 1
エ：ix = ih
模範解答
d：ウ、e：エ、f：イ、g：イ
解説
解答の導き方
この設問では、出現回数の多い順に並べる処理を、途中で整列済みになった範囲を利用して短くする方法を考えます。
まず、配列codeには文字コードが入り、配列freqにはその文字コードの出現回数が入ります。最初にcode[i] = iとするので、文字コードは小さい順に並んでいます。整列中にfreqの値だけを入れ替えると文字コードとの対応が崩れるため、行⑥ではcodeとfreqの両方を入れ替えます。
行⑥の条件は、左側の出現回数が右側より小さいときに入れ替えるというものです。つまり、出現回数の大きい値が左側へ移り、最終的に出現回数の降順になります。
- d：while文のブロックが実行される回数
変更前の処理では、ihを255にしてから、while文のブロックを実行するたびにihを1減らします。ブロックが実行されるときのihの値は、255、254、…、1です。ihが0になると条件ih > 0が成り立たず、繰返しが終わります。
したがって、ブロックの実行回数は255回です。配列の要素数が256でも、ihが0のときにはブロックが実行されない点に注意してください。よって、dは選択肢ウです。
- e：最後に入れ替えた位置から分かる整列済みの範囲
ixには、行⑥の入れ替えが最後に行われたときのiが入ります。最後の入れ替えの後、行⑤のfor文では、iがixより大きい位置について順に比較します。そこでは入れ替えが起きていません。
入れ替えが起きないということは、その範囲では左側の出現回数が右側以上です。したがって、要素番号ix+1から後ろは、出現回数の降順に並んだ状態になっています。
設問文の「要素番号e以降」という表現に当てはめると、eはix+1です。よって、eは選択肢エです。
- f：ixを繰返しごとに初期化する位置
ixは「今回のwhile文の繰返しで、最後に入れ替えた位置」を記録する変数です。そのため、while文の繰返しが始まるたびに、ixを初期値の0に戻す必要があります。
行④はwhile文の開始位置です。行④の直後にix = 0; を置けば、ブロックの実行ごとに初期化できます。一方、行③の直後に置くと初期化は最初の1回だけになり、前の繰返しで記録したixが残ることがあります。また、行⑤の直後に置くと、for文の繰返しのたびに初期化されてしまい、最後の入れ替え位置を正しく記録できません。
したがって、fは行④で、選択肢イです。
- g：次の走査範囲を決める方法
行⑤の処理が終わると、要素番号ix+1以降は整列済みです。次の繰返しでは、その整列済みの範囲をもう一度調べる必要はありません。走査範囲の終端であるihをixにすれば、次のfor文では要素番号0からixより前までを比較します。
したがって、行⑧をih = ix; に置き換えます。gは選択肢イです。
なお、今回の繰返しで入れ替えが一度もなければ、初期化されたixは0のままです。その場合はihも0になり、while文が終了します。入れ替えがないことは、調べた範囲がすでに整列済みであることを示します。
誤りやすいポイント
- 配列の要素数が256だから、while文も256回実行されると考えてしまうことがあります。条件はih > 0なので、ihが0のときには実行されません。
- ixは配列全体で最後に入れ替えた位置ではなく、while文の各繰返しで最後に入れ替えた位置です。そのため、毎回の繰返しの開始時に初期化します。
- 整列済みの範囲はixからではなく、ix+1からです。最後に入れ替えた位置そのものと、その後ろの範囲を混同しないようにしましょう。
- 出現回数だけを入れ替えると、文字コードと回数の対応が崩れます。codeとfreqは必ず一緒に入れ替えます。
FAQ
Q: なぜixを0に戻す必要があるのですか？
A: ixは今回の繰返しで最後に入れ替えた位置を記録するためです。前回の値を残すと、今回の走査範囲を誤って決めるおそれがあります。
A: ixは今回の繰返しで最後に入れ替えた位置を記録するためです。前回の値を残すと、今回の走査範囲を誤って決めるおそれがあります。
Q: 同じ出現回数の文字コードが昇順になるのはなぜですか？
A: codeは最初に0から255の順に設定されます。また、出現回数が等しい場合は入れ替えません。そのため、同じ出現回数の文字コードどうしは最初の順序を保ち、昇順になります。
A: codeは最初に0から255の順に設定されます。また、出現回数が等しい場合は入れ替えません。そのため、同じ出現回数の文字コードどうしは最初の順序を保ち、昇順になります。
Q: 入れ替えがなかった場合に、ihが0になってよいのですか？
A: はい。今回の走査で入れ替えがなければ、走査した範囲はすでに降順です。残りの範囲も前の繰返しまでに整列済みなので、次の繰返しは不要です。
A: はい。今回の走査で入れ替えがなければ、走査した範囲はすでに降順です。残りの範囲も前の繰返しまでに整列済みなので、次の繰返しは不要です。
関連キーワード: バブルソート、安定ソート、配列、整列済み範囲
