平成３１年度春期午後のC言語問題である問９の私の解き方・考え方について解説していきます。
問題
IPAの公式サイトで公開されています。このページでは問９についての解説を行います。
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2019h31_1/2019h31h_fe_pm_qs.pdf
問題の概要
ファイル中の各文字コードの出現回数を求め、それを表示するプログラムに関する問題です。設問２に関しては出現回数に基づいて降順にソートする処理が追加されます。
スポンサーリンク
設問１
まずは問題を読んでいきましょう。
ポイントは[プログラム]の説明（３）に記載されている下記の部分だと思います。
- 文字コードは、64行 x 4列の範囲に、上から下、左から右に文字コードの昇順となるように並べる
printf関数を使用したことある方は知っていると思いますが、基本的にprintf関数では改行してしまうと前の行に戻って文字を表示するようなことはできません。ですので、上から下方向に文字コード順に改行しながら表示してしまうと次の列の表示はその行以降にしか表示できなくなってしまいます。
なので、文字コードの順に表示するではなく、行単位で表示を行う必要があります。つまり、下の図のように文字コードを64（16進数で0x40）ずつ増やしながら右方向に表示していき、4列分表示したら改行して次の行の表示を開始するようなプログラムにする必要があります。
ここを理解していると[ b ]と[ c ]の回答がすんなりできると思います。
では[ a ]から具体的に解いていきましょう。[ a ]は❶の表示を行うprintf関数の引数を問う問題です。
これは単純に読み込んだファイルのバイト数になります。下記で１バイトずつファイルからデータを取得し、その度に cnt をカウントアップしていますので、この cnt が読み込んだファイルのバイト数です。
したがって[ a ]の答えはイの cnt となります。
cnt – 1 や cnt + 1 と迷った場合は、５文字くらいの少ない文字数のファイルを思い浮かべて実際に試してみると良いと思います。実際に試してみると５になるので答えを cnt で確定できます。
[ b ]と[ c ]は事前にポイントとして解説した表示に関する問題ですね。説明したように文字コードを行数である64ずつ増やしながら行単位で表示してやる必要があります。したがって[ c ]の答えはイの64となります。さらに列数は4なので、下記のループを4回実行するためには[ b ]に何を入れれば良いかを考えます。
実際に怪しい選択肢を全て入れて試してみると確実に解けると思います。例えばウの256を入れると i = 0 の時に5回実行されてしまうので間違いです。必ず4回実行されるのはカの i + 192 だけなので[ b ]の答えはカとなります。
設問２
設問２はソートに関する問題になります。問題文にバブルソートとか出てきてギョッとしてしまいますが、基本的にアルゴリズムやC言語問題は単語の意味を知らなくても十分解ける問題になっていますので安心してください。
まず[ d ]ですが、これは単純に下記のwhile文のブロックが何回繰り返されるかを回答する問題になります。 ih が 255 で while文が実行されるたびに1減り、これが ih が 0 よりも大きい間実行されることになりますので 255 回実行されることになります。従って[ d ]の答えはウの255です。
回答に不安な方は ih に小さい数字を入れてみて、その数字とwhile文のブロックの実行回数の関係性を見てみると、答えに確信が持てると思います。例えば ih = 5 にして頭の中でwhile文の中を実行してみれば、 while文の中は5回実行されること、つまりwhile文を実行する直前の ih の回数分 while文の中が実行されることが確認できると思います。
つまり、このソート処理ではとにかく捜査範囲内で一番 freq の小さい要素を要素番号 ih に配置することで、捜査範囲（捜査範囲は要素番号 0 〜 ih – 1）を１ずつ狭めていくソート処理になります。
図も用いて解説したいと思います。例えば ih が 4 から始まり、 freq が下記のような配列になっている場合、while文のブロックが１度実行されると下記のように一番 freq の値が小さい要素が要素番号 ih の位置に移動します。
これにより要素番号 ih に捜査範囲の中で一番小さい値の要素が移動することになります。なので、要素番号 ih の要素に関してはこれ以上ソートを行う捜査範囲に含める必要がありません。なのでソートの捜査範囲 は 0 〜 ih から 0 〜 ih – 1 に狭めることができます。
ih – 1（つまり ih = 3 ）に狭めた時の while文のブロックの実行によるソート結果は下記のようになります。
これを ih が 0 になるまで繰り返すことによって freq 配列が降順にソートされることになります。これがプログラムで記述されたソートになります。
ただし、これは一度の while文のブロック実行で１つの要素しか位置が確定しないことを前提した処理になります。しかし、例えば下記のように一度の while文のブロック実行で複数の要素の位置が確定する場合があります。具体的には最後にSwap を行なった i よりも１大きい要素以降の位置が確定する（整列ずみ）ことになります。
このような場合でも、プログラム通りに実行してしまうと、捜査範囲は１つずつしか狭まっていきません。そうなると次の while文のブロック実行では位置が確定した要素まで捜査範囲に含められてしまうので、この while文のブロック実行はソート処理においては意味のないものになってしまいます。
なので、下の図のように、位置が確定した要素まで一気に捜査範囲を狭めてやろうというのが、設問２で行おうとしている処理になります。
では実際に設問に回答していきましょう。[ e ]は一度のwhile文のブロックを実行するとどこまでの要素が整列済みになるかを問う問題です。前述の通り最後にSwapが行われた i よりも１大きい要素以降が整列済みとなります。さらに下記に記載の通り、Swap が行われた i の値が ix となりますので、[ e ]の答えはエの ix + 1 となります。
続いて、一旦[ f ]は置いといて、[ g ]について解説したいと思います。前述の通り、 ix + 1 以降の要素は整列済みになりますので、ix + 1 はソート処理を行う必要がありません。なので、次にソートを行う捜査範囲は 0 〜 ix のみで良いです。なので捜査範囲の終端を表す ih は ix まで狭めて問題ないです。従って[ g ]の答えは ih = ix のイとなります。
最後に[ f ]について考えていきましょう。これは消去法で解けます。③の直後に ix = 0 を入れてしまうと、Swapが一度も行われない場合に、前回の ix の値がそのまま ih に代入されてしまいます。つまり捜査範囲が狭まりません。従って無限ループになる可能性があります。なので③の直後に ix = 0 を入れるのは間違いです。
また⑤の直後に ix = 0 を入れてしまうと、最後（ i = ih – 1 の時）に Swap が行われないと ix が 0 のまま ih に代入されてしまうので、ソートが完了する前に while文が終了してしまいます。なので⑤の直後に ix = 0 を入れるのは間違いです。
従って、[ f ]の答えは行④の直後に ix = 0 を行うイとなります。
問題を解いた感想
うーん、どうも問８のアルゴリズム問題よりもこのC言語問題の方がアルゴリズム要素が強い気がしました。過去１０回くらい基本情報技術者試験んのC言語問題とアルゴリズム問題を解いてきましたが、この傾向がある回って多いんですよね…。アルゴリズムに自信がある方はC言語問題も合わせて選択しても良いかと思いました。
★オススメページ★
下記ページから他の回の解説もたどれます。他の回のC言語問題の解き方がわからない場合は是非読んでみてください！
基本情報技術者試験 午後問題「C言語」過去問の解き方 解説 まとめ
本ページの図・プログラム・問題文について
図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。
出典：平成３１年度 春期 基本情報技術者試験（FE）試験区分 午後 問９
