0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

株式会社ITPMAdvent Calendar 2018

Day 13

n進数の足し算をJavaで実装してみる

Last updated at Posted at 2018-12-12

西之園萌絵は、 両手を顔の横で広げてみせた。
人類は十進法を採用しました、というジェスチャではない。
(森博嗣の短編集『まどろみ消去』中の『誰もいなくなった Thirty Little Indians』より)

#1.はじめに

 先日、実家の本棚を整理中に見つけた上記のミステリィ本を、片付けそっちのけで読み直していたのですが、せっかくなので$n$進法絡みでプログラムを作ってみたいな~と考えるようになりました。そこで今回は、$n$進法の例として4進数の足し算をJavaで実装してみます。なお、タイトルに$n$進法とあるように、2進法でも4進法でも16進法でも対応できそうなコーディングを目指します。

#2.問題設定

 どこかの国に、いつも4進法で計算している人たちがいると仮定します。彼らが使う数字は我々が使う数字とは異なっていて、どうやらアルファベットに似ているようです。調べたところ、次のような対応になっていることが分かりました。

4進数の人たち 我々 言い訳っぽい何か
P 0 丸みのあるのが0っぽい
I 1 見た目が1っぽい
T 2 画数が2なので……
M 3 3を左に90°回転させるとMっぽい

 もし彼らが「ITPM」と書いたら、それは我々の使う10進数では$1203_{(4)}$、つまり

1203_{(4)} = 1 × 4^3 + 2 × 4^2 + 0 × 4 + 3 × 1 = 64 + 32 + 0 + 3 = 99

であることを意味しています。
 2つの4進数が与えられると、それらを足し算した結果が上記のアルファベットを用いた4進数表記で出力されるプログラムを作ります。たとえば「I」と「TPM」だと、

1_{(4)} + 203_{(4)} = 1 + 35 = 36 = 210_{(4)}

なので、「TIP」と出力するものとします。
 なお、冒頭にも書いたように、今回は4進法の処理だけをつくるのではなく、ちょっと抽象的に$n$進法として書いてみたいと思います。

#3.実装

 $n$進数のまますべての計算処理をつくるのは大変ですので、一旦2つの数を10進数に直してから計算し、その後$n$進数に戻す、という方針でいきます。

###NAryNumberクラス

 まず、何進法なのかを表す$n$の値と、$n$進法の各桁で用いる数字または文字(たとえば、16進法では10進法の10, 11, 12, ……, 15の代わりにA, B, C, ……, Fを用います)を格納するクラスNAryNumberをつくります。なお、各位につき1つのアルファベット[A-Za-z]または数字[0-9]を割り当てるものとします。

class NAryNumber {
	private int N;									// N進数のNの値
	private char[] characters;						// 0~N-1に対応する文字
	private HashMap<Character, Integer> numbers;	// 0~N-1番目の文字に対応する数字

	public NAryNumber(int n, char[] c) {
		this.N = n;
		this.characters = c.clone();
		this.numbers = new HashMap<Character, Integer>();
		for (int i = 0; i < this.characters.length; i ++) {
			numbers.put(this.characters[i], i);
		}
	}
}

 10進法は0から9までの10個の数字を用いますが、同様に$n$進法は0から$n-1$までの$n$個の文字を用います。初めのメンバ変数Nにはこの$n$の値が入ります。char型配列charactersには各数に割り当てた文字が入りますが、入る順番は必ず0に対応する文字、1に対応する文字、2に対応する文字、……とします。そして0, 1, 2, ……の各値についてはnumbersという名の、配列ではなく連想配列と呼ばれるデータ型に格納しています。この連想配列こそが、本記事の良く分かってないのにイキっているキモとなる部分です。

 普通の配列は、必ず0番目、1番目、2番目というように0以上の整数で順番が決められています。このときの0, 1, 2, ……を__インデックス__とか__添え字__と呼びます。一方、連想配列はインデックスに整数だけでなく、文字列も用いることができるのです。このときのインデックスに使われる文字列を__キー__(key)と呼びます。

 そもそもなぜ連想配列を用いることにしたかと言うと、たとえば上記の4進法で4進数を10進数に変換しようとすると、char型配列charactersだけでは
   'T'が来た!
  ⇒ 'T'って何番目に格納された文字?
  ⇒ (配列の値を1つ1つ確かめながら)あ、3番目だ!
  ⇒ じゃあ2だね
みたいな処理になって、ちょっと書くのが面倒だと思ったからです(できなくはないですが)。一方、連想配列numbersを用いると、'T'というキーには2がくっつくようにできるので、numbers.get('T')と書くだけで2を得ることができます。

 NAryNumberクラスでは、与えられた$n$進数を10進数に変換するメソッドconvFromNAryToDecと、与えられた10進数を$n$進数に変換するメソッドconvFromDecToNAryをつくります。

###convFromNAryToDecメソッド

 $n$進数を10進数に変換するには、各位が何の位かを調べる必要があります。たとえば10進法なら、1の位から順に10の位、100の位、1000の位と続いていきます。2進法なら1の位から順に2の位、4の位、8の位と続いていきます。このように、$n$進法では1の位から順に$n$の位、$n^2$の位、$n^3$の位と続いていきますので、その数を各位の数にかけていって、最後にそれらの和を求めてやれば、$n$進数の出来上がりです。
 なお、入力された数が何桁かは決まっていないため、文字列の長さから桁数を求めることにします。先程、各位に1つの文字を割り当てると決めたのは、このためです。

public int convFromNAryToDec(String nAry) {
	int dec = 0;	// N進数を10進数に変換した値
	for (int i = 0; i < nAry.length(); i ++) {
		// 1の位から順に和を求める
		dec += numbers.get(nAry.charAt(nAry.length() - 1 - i)) * Math.pow(N, i);
	}
	return dec;
}

###convFromDecToNAryメソッド

 10進数から$n$進数に変換するのですが、今度は先程とは逆、つまりかけるのではなく割っていくことになります。$n$進法では$n$個数えるごとに次の位が増えていきますから、$n$個ずつのまとまりがいくつできるか、つまり何回繰り上がるかを知りたい訳です。ただし、$n$で割った余りが各位の数字になるのですが、__1の位から順に求まる__ことに注意してください。つまり、余りを求めた順につなげると答の逆順になる、ということです。ですから、最後に文字列の順番を逆転させる必要があります。

public String convFromDecToNAry(int dec) {
	String nAryRev = "";
	// 余りを求めた順(実際とは逆順)にN進数に変換する
	while (dec >= this.N) {
		int rem = dec % this.N;
		dec = (dec - rem) / N;
		nAryRev += this.characters[rem];
	}
	nAryRev += this.characters[dec];
	// 文字列を逆転させてから返す
	return new StringBuffer(nAryRev).reverse().toString();
}

 最後に入力部分をつくるのですが、毎回毎回コンソールから$n$の値や各位に使用する文字も入力するのは面倒なので、今回だけプログラム内に直接値を書き込んでしまうことにします。一応、続編を予定しているのですが、その際はテキストファイルに書いた設定を読み込むようにしますので、今回はご容赦ください。

#4.完成

 そんなこんなで、完成版のプログラムは下記となります。初めにお見せした4進法の設定で、I + TPMを計算するように入力部分を書いています。出力結果はTIPとなります。

2つの4進数の和を求めるプログラム(クリックすると開きます)
import java.util.HashMap;

class NAryNumberTest {
	public static void main(String args[]) {
		// 入力
		int N = 4;
		char[] characters = {'P', 'I', 'T', 'M'};
		String val1 = "I";
		String val2 = "TPM";
		
		// 処理
		NAryNumber nary = new NAryNumber(N, characters);
		String result = nary.convFromDecToNAry(
			nary.convFromNAryToDec(val1) + nary.convFromNAryToDec(val2)
		);
		System.out.println(result);
	}
}

class NAryNumber {
	private int N;									// N進数のNの値
	private char[] characters;						// 0~N-1に対応する文字
	private HashMap<Character, Integer> numbers;	// 0~N-1番目の文字に対応する数字

	public NAryNumber(int n, char[] c) {
		this.N = n;
		this.characters = c.clone();
		this.numbers = new HashMap<Character, Integer>();
		for (int i = 0; i < this.characters.length; i ++) {
			numbers.put(this.characters[i], i);
		}
	}
	public int convFromNAryToDec(String nAry) {
		int dec = 0;	// N進数を10進数に変換した値
		for (int i = 0; i < nAry.length(); i ++) {
			// 1の位から順に和を求める
			dec += numbers.get(nAry.charAt(nAry.length() - 1 - i)) * Math.pow(N, i);
		}
		return dec;
	}
	public String convFromDecToNAry(int dec) {
		String nAryRev = "";
		// 余りを求めた順(実際とは逆順)にN進数に変換する
		while (dec >= this.N) {
			int rem = dec % this.N;
			dec = (dec - rem) / N;
			nAryRev += this.characters[rem];
		}
		nAryRev += this.characters[dec];
		// 文字列を逆転させてから返す
		return new StringBuffer(nAryRev).reverse().toString();
	}
}

 ちなみに、冒頭の入力部分を次のように書き換えると、16進法の計算も可能です。出力結果はFFFFFとなります。

2つの16進数の和を求めるプログラム(クリックすると開きます)
import java.util.HashMap;

class NAryNumberTest {
	public static void main(String args[]) {
		// 入力
		int N = 16;
		char[] characters = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
				'A', 'B', 'C', 'D', 'E', 'F'};
		String val1 = "12345";
		String val2 = "EDCBA";
		
		// 処理
		NAryNumber nary = new NAryNumber(N, characters);
		String result = nary.convFromDecToNAry(
			nary.convFromNAryToDec(val1) + nary.convFromNAryToDec(val2)
		);
		System.out.println(result);
	}
}

class NAryNumber {
	private int N;									// N進数のNの値
	private char[] characters;						// 0~N-1に対応する文字
	private HashMap<Character, Integer> numbers;	// 0~N-1番目の文字に対応する数字

	public NAryNumber(int n, char[] c) {
		this.N = n;
		this.characters = c.clone();
		this.numbers = new HashMap<Character, Integer>();
		for (int i = 0; i < this.characters.length; i ++) {
			numbers.put(this.characters[i], i);
		}
	}
	public int convFromNAryToDec(String nAry) {
		int dec = 0;	// N進数を10進数に変換した値
		for (int i = 0; i < nAry.length(); i ++) {
			// 1の位から順に和を求める
			dec += numbers.get(nAry.charAt(nAry.length() - 1 - i)) * Math.pow(N, i);
		}
		return dec;
	}
	public String convFromDecToNAry(int dec) {
		String nAryRev = "";
		// 余りを求めた順(実際とは逆順)にN進数に変換する
		while (dec >= this.N) {
			int rem = dec % this.N;
			dec = (dec - rem) / N;
			nAryRev += this.characters[rem];
		}
		nAryRev += this.characters[dec];
		// 文字列を逆転させてから返す
		return new StringBuffer(nAryRev).reverse().toString();
	}
}

 と言うことで、今回は$n$進数 ⇔ 10進数の変換をメインに実装してみました。できれば、上記でも書いたようにテキストファイルに書かれた設定を読み込んだり、コンソールから入力された数式を計算できるような処理まで実装してみたいです。これらについては、今後の課題として取り組んでいきます。また機会がありましたら、お付き合いください。

 ここまでお読みいただき、ありがとうございました。

#余談 私にとってのクラスやカプセル化のイメージ

12月13日追記
下のコメントで、インタフェースについてのご指摘をいただいております。ぜひご確認ください。

 なが~~~い余談になりますが、ご容赦ください。

 この記事を書きながら、結局クラスやカプセル化って何なんだろうと考えていました。もちろん、書籍やネットで嫌と言うほどそれらの説明を調べることはできるのですが、何かこう、自分にしっくりくる考え方はないかな~と思っていたところ、個人的に納得できる例を思いつきました。

 小学生や中学生の頃、学校で〇〇委員って言う役割がありましたよね。学級委員とか、図書委員とか、保健委員とか。当然、〇〇委員という名の人間は存在しません。その正体は、ナントカ太郎さんとか、ナントカ花子さんとか、実在している人たちな訳です。で、図書委員のような__特定の役割を指すのがクラス__で、その__役割を実際に担う人や物が実体(インスタンス)__なのかな、と考えてみましょう。たとえば、いつも図書室で静かに本を読んでいて日によってメガネをかけたりかけなかったりしている無口なナントカ有希さんが、図書委員という名のクラスの実体という感じです。

 もう少し妄想すると、図書委員クラスの中には、本の貸し出しリストという変数があります。このリストはプライバシーの観点から許可のない人には見せられない物なので、__private__という修飾子をつけておきます。その代わり、先生や他の図書委員といった特別な人だけに本の貸し出しリストを見せるための、「貸し出しリストを見せる」という名のメソッドに__public__という修飾子をつけておくのです。そうすれば、図書委員の仕事を良く知らない人(他のプログラマ)が、許可されていない人が貸し出しリストを見てしまうような処理(本来想定されていない処理⇒バグの原因になりうる)を書いてしまう事態を避けることができます(書いたらエラーになる)。このように、クラス内の変数やメソッド(メンバ変数、メンバメソッドと言います)をクラスの外部から参照できなくしたり、参照の仕方を決めたりするのが__カプセル化__の考え方(の一部)です。

maruhi_gokuhibunsyo.png

 さらに妄想すると、図書委員の中には、その学校の中で図書委員のトップの座にいる図書委員__長__と呼ばれる人がいます。もし、図書委員__長__というクラスを1からつくるとしたら、図書委員のもつ変数やメソッドをコピペするなど非効率な面が出てきます(本の貸し出しリストの仕様が変わったら、図書委員クラスも図書委員__長__クラスも同様に書き換えなければならない!)。そこで、図書委員クラスを__継承__して図書委員__長__クラスをつくることにより、図書委員クラスのもつ変数やメソッドはわざわざ書かなくても使える状態になっていて、図書委員__長__ならではの役割(図書委員たちの勤怠を管理するとか)だけを追加すればOK、という感じです。

 最後になりますが、とある役割がクラスの正体だとすると、その役割が何なのかが__他のプログラマに分かりやすい名前__にしておくことが大事ですね。私はいつもカッコイイ英単語にしようと試みるのですが、大抵中途半端な結果に終わります。今回のNAryNumberクラスも、その産物です。ちなみに、メソッド名にあるconvはconvert(変換する)を、DecはDecimal(10進法)の省略なのですが、伝わらなければ意味がありません。このようなネーミングはあまり良くありませんので、ご注意ください。

 こんな所までお読みいただき、誠にありがとうございました。

0
0
5

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?