高校数学をプログラミングで解く（数学A編）「3-10 N進法」

マガジンリスト　＞　数学A編 3.整数の性質　＞　3-10 N進法

はじめに

今回は、数学Aで学ぶ「N進法」について、$${10}$$進法で表された数を$${N}$$進法で表すためのプログラムを作成します。

10進法の数をN進法に変換する

変換の例
$${10}$$進法の数を$${N}$$進法に変換する例として、「$${123}$$」を$${4}$$進法の数に変換することを考えてみます。答えは

$$
123 = 1323_{(4)}
$$

となります。

アルゴリズム設計「変換方法を考える」

$${10}$$進法の数を$${N}$$進法に変換する方法を考えるために、答えの表示方法を少し変えてみます。

$$
\begin{array}{}
123 = 1323_{(4)} &=& 3 \times 4^0+2 \times 4^1+3 \times 4^2 + 1 \times 4^3 \\ 
&=& 3+ 4 \times ( 2 \times 4^0+3 \times 4^1 + 1 \times 4^2 )
\end{array}
$$

この式から、$${4}$$進法で表したときの１桁目の数「$${3}$$」は、「$${123}$$」を「$${4}$$」で割ったときの余りとなっていることがわかります。さらに、「$${123}$$」を「$${4}$$」で割ったときの商は、

$$
2 \times 4^0+3 \times 4^1 + 1 \times 4^2
$$

となります。これを書き換えると、

$$
2 \times 4^0+3 \times 4^1 + 1 \times 4^2 = 2 + 4 \times ( 3 \times 4^0 + 1 \times 4^1 )
$$

となります。この式から、$${4}$$進法で表したときの2桁目の数「$${2}$$」は、商を「$${4}$$」で割ったときの余りとなっていることがわかります。
つまり、$${10}$$進法の数「$${123}$$」を$${4}$$進法で表す場合、「$${123}$$」を「$${4}$$」で割ったときの余り「$${3}$$」が1桁目の数となり、このときの商「$${30}$$」を「$${4}$$」で割ったときの余り「$${2}$$」が2桁目の数となり、さらに、このときの商「$${7}$$」を「$${4}$$」で割ったときの余り「$${3}$$」が3桁目の数となり、最後に、このときの商「$${1}$$」を「$${4}$$」で割ったときの余り「$${1}$$」が4桁目の数となります。最後の商は「$${0}$$」になるので、これ以上の桁はありません。これらをまとめると、$${1323_{(4)}}$$が得られます。

アルゴリズム設計「変換方法（一般化）」

上記で説明した変換方法を一般化してみます。
$${10}$$進法で表された整数を$${A}$$とし、$${A}$$を$${N}$$進法で表すことを考えます。結果として、

$$
A = {a_{n-1} \cdots a_1 a_0}_{(N)} = a_0 \times N^0 + a_1 \times N^1 + \cdots + a_{n-1} \times N^{n-1}
$$

という形で表すことができます。

① 割られる数を$${m}$$とし、割る数を$${N}$$とします。最初の段階では、$${m}$$に$${A}$$を代入します。
② $${m}$$を$${N}$$で割ったときの商$${q}$$と余り$${r}$$を計算し、余り$${r}$$を$${a_0}$$に代入します。
③ 商$${q}$$を$${m}$$に代入して、割られる数を更新します。
④ ②と③の処理（ただし、②の余り$${r}$$を代入する変数は$${a_1}$$、$${a_2}$$、$${\cdots}$$と繰り返すたびに指数が増えたものになります）を、$${q}$$が$${0}$$になるまで繰り返します。

プログラム

上記で解説した方法を利用して、10進法の数「$${123}$$」を4進法で表すプログラムを作成します。

// 10進数をN進数にする
void setup(){

  int A = 123; // 10進数の数
  int N = 4; // N進法
  
  // AをN進数で表したときの各桁の数を格納する可変配列
  ArrayList<Integer> a = new ArrayList<Integer>(); 

  int q, r; // 商と余り
  int m = A; // 割られる数を初期化
  q = 1; // qを初期化
  while( q > 0 ){
    q = m/N; // 商
    r = m%N; // 余り
    a.add(r); // 余りを可変配列に追加
    m = q; // 割られる数を更新
  }
  
  // AをN進数で表した時の数をコンソールに出力
  for(int i=a.size()-1; i>=0; i--){
    print(a.get(i));
  }
}

ソースコード1　10進数の数を$${N}$$進法で表すプログラム

ソースコード1を、Processingの開発環境ウィンドウを開いて（スケッチ名を「DecimalToN_ary」としています）、テキストエディタ部分に書いて実行すると、図1のように、コンソールに10進法の数「$${123}$$」を4進法で表したときの数「$${1323}$$」を出力します。

図1　スケッチ「DecimalToN_ary」の実行結果

プログラムの解説「可変配列の利用」

整数をN進数で表した場合の各桁を$${a_0, a_1, \cdots, a_{n-1}}$$で表しました。このときの桁数$${n}$$を事前に求めることは手間がかかるので、プログラム（ソースコード1）では整数型の可変配列aを利用しました。可変配列については記事『高校数学をプログラミングで解く（準備編）「2-4 配列」』をご覧ください。

プログラムの解説「N進数の表示」

整数をN進数で表した場合の各桁$${a_0, a_1, \cdots, a_{n-1}}$$を求めたら、そのN進数の整数をコンソールに出力しています。可変配列aにはそれらの要素が$${a_0}$$、$${a_1}$$、$${\cdots}$$の順に追加されていますが、コンソールへの出力時にはこれらの要素を$${a_{n-1}}$$、$${a_{n-2}}$$、$${\cdots}$$の順で出力することでN進数の$${{a_{n-1} \cdots a_1 a_0}_{(N)}}$$が表示できます。そこで、forループを降順に利用することで可変配列の出力順を調整しています。

  for(int i=a.size()-1; i>=0; i--){
    print(a.get(i));
  }

なお、「a.size()」は可変配列aの要素数を表し、「a.get(i)」は可変配列aのi番目の要素を取り出すときに利用します。

まとめ

今回は、数学Aで学ぶ「N進法」について、$${10}$$進法で表された数を$${N}$$進法で表すためのプログラムを作成してみました。
$${10}$$進法で表された整数を$${N}$$進法に変換するプログラムは、$${10}$$進法で表された数を$${N}$$で割っていき、その余りが$${N}$$進数の各桁の値と関連していくことを利用して、比較的簡単にプログラミングすることができました。

$${10}$$進法で表された小数を$${N}$$進法に変換することもできます。その手順についてまとめておきます。
$${A}$$を$${0<A<1}$$の小数とします。この$${A}$$を$${N}$$進数で表したときの式を

$$
A = 0.a_1a_2 \cdots _{(N)} = a_1 N^{-1} + a_2 N^{-2} + \cdots
$$

とします。ここで、$${a_i}$$（$${i = 1, 2, \cdots}$$）は$${A}$$を$${N}$$進数で表したときの小数第$${i}$$位の値を表します。

① 上記の式の両辺を$${N}$$倍して、

$$
A_1 = NA = a_1  + a_2 N^{-1} + \cdots
$$

とします。この関係式から$${a_1}$$は、$${A_1}$$の整数部分を取り出すことでその値を得ることができます。

② $${A_1}$$から$${a_1}$$を引き、その結果を$${N}$$倍して、

$$
A_2 = N(A_1-a_1) = a_2  + a_3 N^{-1} + \cdots
$$

とします。この関係式から$${a_2}$$は、$${A_2}$$の整数部分を取り出すことでその値を得ることができます。

③ あとは、②の処理を繰り返していくことで$${A}$$を$${N}$$進数で表したときの結果がえられます。

$${10}$$進法で表された小数を$${N}$$進法に変換するプログラムについては、演習問題にしましたので、是非チャレンジしてみてください。

読んだ感想などをお寄せください

本記事を読んだ感想や質問などを以下のお問い合せフォームからお寄せください。感想、質問をいただいた方には本記事の演習問題の解答をプレゼントします。（お問合せフォームの本文に、本記事のタイトルを入れてください。）

お問い合わせ | note（ノート）

参考文献

改訂版 教科書傍用 スタンダード 数学A（数研出版、ISBN9784410209277）

演習問題

演習問題１
次の$${10}$$進数を[]内の数字の進法で表してください。

$$
\mathrm{(1)}  18  [2\mathrm{進法}],  
\mathrm{(2)}  248  [3\mathrm{進法}],  
\mathrm{(3)}  321  [7\mathrm{進法}] 
$$

演習問題２
$${10}$$進数で表された小数$${0.1}$$を$${2}$$から$${9}$$までの進数で表すとどうなるか、プログラムを作成して確認してみてください。

演習問題の解答例