科目Bの基数変換問題の解き方｜n進数への変換を余りと商で追う

余りを並べるのは分かるけど、上から読むのか下から読むのか、毎回あやふやになる。

科目Bの問題で、10進数を別の進数に直すコードが出てきたとき、答えの桁の並びで迷ったことはありませんか？

2進数なら何とかなるのに、3進数や16進数になると急に自信がなくなる。そんな人は少なくないのではないでしょうか。

大丈夫です。基数変換の問題で必要なのは、余りと商を1回ずつ表に書くことと、できた桁をどちら向きに並べるかを確かめる手順だけです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、数字の連番を短い英数字の文字列に変えて、URL や注文番号に使う処理を何度か書いています。

そのとき、桁を逆向きに並べてしまい、別の番号を指すコードを作りかけたことがあります。気づけたのは、小さな値で余りと商を紙に書き出して、元の数に戻るかを確かめたからでした。

この記事では、基数変換の問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中でこうした問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

基数変換の問題は何を聞いているのか¶

最初に、基数変換とは何かを短く押さえておきましょう。言葉は難しそうですが、やっていることは身近な計算です。

基数とは、何進数かを表す数のことです。10進数の基数は10、2進数の基数は2、16進数の基数は16になります。

基数変換とは、ある数を別の基数の表し方に書き直すことです。中身の量は変わらず、見た目の書き方だけが変わります。

科目Bで問われる形¶

試験の擬似言語で基数変換が出るときは、変換の理屈そのものよりも、コードがどう動くかが問われます。どんな形で聞かれやすいのかを、表に整理しました。

どの形でも、中心にあるのは余りと商の2つです。この2つが1回ごとにどう変わるかを追えれば、問われ方が変わっても同じ手順で解けます。

2進数の変換との関係¶

2進数への変換は、基数変換のいちばん小さな例です。2で割った余りを集めていくと2進数になる、という話を聞いたことがある人も多いと思います。

3進数でも16進数でも、割る数が2から3や16に変わるだけで、手順はまったく同じです。基数が大きくなると、余りが10以上になる場合が出てくるので、それを文字で表す工夫が加わります。

2進数のまま、桁を取り出したり立てたりする問題については、こちらの記事で詳しく扱っています。

【関連記事】科目Bのビット演算問題の解き方｜論理積とシフトを2進数で追う

まず目を付ける場所¶

基数変換とは何かがつかめたら、次はコードのどこから読むかを決めます。基数変換の問題では、目を付ける場所が3つあります。

ひとつ目は mod で余りを取る行、ふたつ目は商で値を小さくする行、みっつ目は結果に桁を付け足す行です。この3行が見つかれば、コード全体の役割がほぼ決まります。

mod の行は一の位を取り出す¶

まず探すのは、q mod n のように基数で割った余りを求めている行です。この余りが、n進数で表したときのいちばん下の桁、つまり一の位になります。

10進数で考えると分かりやすいです。123 を10で割った余りは 3 で、これは123の一の位そのものです。

基数が3なら、3で割った余りが3進数の一の位になります。余りは必ず 0 から n − 1 までの値になる、という点も覚えておきましょう。

余りや割り算の書き方そのものに不安がある場合は、こちらの記事で先に整理しておくと読みやすくなります。

【関連記事】擬似言語の余り（剰余）と割り算がわからない人へ｜偶数判定と桁の取り出しを解説

商の行は一の位を捨てる¶

次に探すのは、q ← q ÷ n の商 のように、値を基数で割った商で置き換えている行です。これは、いま取り出した一の位を捨てて、残りを1桁右へずらす操作にあたります。

123 を10で割った商は 12 です。一の位の 3 が消えて、次は 12 の一の位である 2 を取り出せるようになります。

mod で取り出して、商で捨てる。この2つを交互に繰り返すと、下の桁から順に1つずつ桁が手に入ります。

桁を付け足す向きを確かめる¶

最後に見るのが、取り出した桁を結果にどう付け足しているかです。ここが、冒頭の上から読むか下から読むかの迷いに直結します。

余りは一の位から順に出てくるので、出てきた順に左から並べると、桁が逆さまになります。正しく並べるには、新しい桁を結果の前に付けるか、あとで全体を逆順にする必要があります。

コードの中で、新しい桁が左側に置かれているのか右側に置かれているのか。ここを確かめるだけで、選択肢の半分近くを絞れることもあります。

例題：10進数をn進数の文字列に直す¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のコードは、0 以上の整数 x と、2 以上 16 以下の基数 n を受け取り、x を n進数で表した文字列を返す関数です。

文字列の扱いは、問題ごとに説明が付くのが普通です。この例題では、s の k 文字目 で文字列 s の左から k 番目の1文字を表し、＋ で文字列をつなぐことにします。

○文字列型: toBase(整数型: x, 整数型: n)
  文字列型: digits ← "0123456789ABCDEF"
  文字列型: result ← ""
  整数型: q ← x
  整数型: r
  if (q が 0 と等しい)
    return "0"
  endif
  while (q が 0 より大きい)
    r ← q mod n
    result ← (digits の (r + 1) 文字目) ＋ result
    q ← q ÷ n の商
  endwhile
  return result

digits は、余りを文字に変えるための対応表です。余りが 0 なら1文字目の "0"、余りが 11 なら12文字目の "B" を取り出します。

新しい桁は、result の前に付けています。下の桁から順に出てくるので、前に付けていけば、最後には正しい並びになります。

では、x に 45、n に 3 を渡すと、戻り値は何になるでしょうか？

トレース表で余りと商を追う¶

頭の中だけで割り算を繰り返すと、何回目なのか、どの余りがどの桁なのかが分からなくなりがちです。そこで、ループ1回ごとの q、r、result をトレース表に書きます。

ポイントは、割る前の q と割ったあとの q を別の列に分けることです。こうしておくと、どの値から余りを取ったのかが一目で確かめられます。

4回目のあと q は 0 になり、q が 0 より大きいという条件が偽になってループを抜けます。戻り値は "1200" です。

答えが合っているか不安なときは、元の数に戻して確かめましょう。3進数の 1200 は、1 × 27 ＋ 2 × 9 ＋ 0 × 3 ＋ 0 × 1 で 45 になるので、正しく変換できています。

トレース表の書き方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

16進数で余りが10を超える場合¶

同じ関数に、x として 200、n として 16 を渡した場合も追ってみましょう。16進数では、余りが 10 以上になったときに文字の対応表が活躍します。

1回目は 200 mod 16 で余りが 8、商が 12 です。2回目は 12 mod 16 で余りが 12、商が 0 になってループを抜けます。

余りの 12 は、digits の13文字目なので "C" です。result は "8" の前に "C" が付いて "C8" になります。

確かめると、C は 12 を表すので、12 × 16 ＋ 8 で 200 です。2回のループで、きちんと元の数に戻りました。

逆変換は掛けて足すを繰り返す¶

科目Bでは、n進数の文字列を10進数に戻す向きのコードも出ます。こちらは、割って余りを取るのではなく、掛けて足すを繰り返すのが基本の形です。

左の桁から順に、value ← value × n ＋ その桁の値 と更新していきます。"1200" を3進数として読むなら、value は 1、5、15、45 と変わり、最後に 45 が残ります。

左から読むか右から読むかで迷ったら、この掛けて足すの形を思い出してください。左から読むなら、毎回いったん基数を掛けてから桁を足す、と覚えておくと迷いません。

間違いやすい選択肢の見分け方¶

基数変換の問題では、式を少しだけ変えた選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

よくある誤りを表にまとめました。

この中でも、特によく狙われるのが付け足す向きと、対応表の添字です。順番に見ていきましょう。

付け足す向きは小さな値で確かめる¶

付け足す向きで迷ったら、10進数のまま基数 10 で動かしてみてください。x に 123、n に 10 を渡せば、出てくる余りは 3、2、1 の順です。

前に付ける書き方なら "123" になり、後ろに付ける書き方なら "321" になります。元の数と同じ並びになるほうが正しい、とすぐに判断できます。

基数 10 なら、変換の結果が元の数と同じになるはずです。答えが分かっている入力で試すのは、選択肢を絞るときにとても強い方法です。

1始まりの添字に注意する¶

擬似言語の配列や文字列は、1文字目から数えることが多いです。余りは 0 から始まるので、対応表を引くときには r ＋ 1 番目を読む必要があります。

r 番目のまま読む選択肢は、余りが 0 のときに0文字目という存在しない位置を指してしまいます。余りが 1 なら "0" を、余りが 10 なら "9" を返すことになり、1つずつずれた答えになります。

添字が0始まりか1始まりかは、問題文の冒頭に書かれています。読み始める前に、必ずその一文を確かめておきましょう。

文字列から1文字ずつ取り出す処理そのものに慣れていない場合は、こちらの記事が参考になります。

【関連記事】科目Bの文字列問題の解き方｜1文字ずつ取り出す処理を追うコツ

ループの終わり方を境目で確かめる¶

ループ条件の誤りは、境目の値で試すと見つけやすくなります。x に 1 を渡したときに "1" が返るかどうかを確かめてみてください。

q が 1 より大きい間という条件だと、q が 1 の時点でループに入らず、空の文字列が返ってしまいます。q が 0 以上の間という条件だと、q が 0 のまま割り続けて終わらなくなります。

0 や 1 のような端の値は、コードの弱いところがいちばん表に出やすい入力です。時間が許す範囲で、選択肢ごとに1回だけ試してみる価値があります。

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。割り算を何度も繰り返す処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの回で予想とずれたのかがすぐに分かります。

試すときは、文字列の部分をいったん外して、余りと商だけを追う形にするのがおすすめです。q と r が 45、15、5、1 と変わっていく様子を見ると、商で一の位を捨てている感覚が自然に身につきます。

慣れてきたら、x を 255 にして n を 2、8、16 と変えてみてください。基数が大きいほどループの回数が少なくなることが、自分の目で確かめられます。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、値が1行ごとに変わっていく様子を確かめてみてください。

まとめ¶

科目Bの基数変換の問題は、難しい数学の知識を問うものではありません。余りと商を1回ごとに表に書き、桁をどちら向きに並べるかを確かめれば、落ち着いて解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、2桁か3桁で収まる小さな値で十分です。何度か表を書くうちに、mod を見ただけで一の位を取り出しているのだと分かるようになります。

答えが出たら、掛けて足すで元の数に戻るかを確かめる。この一手間を習慣にしておけば、本番でも自分の答えに自信を持てます。次に基数変換の問題に出会ったら、まずは余りと商の表を書くところから始めてみてください。