名古屋で数学するプログラマ(仮)

@antimon2 が趣味兼一部本職の数学で何かするときのブログ。

5進化10進数の話。

ご無沙汰してます。
前置きはばっさり省略して。
CodeIQ の大人気問題ダンジョンシリーズの「そろばんのダンジョン」という問題がありまして。


大人気ダンジョンシリーズ!そろばんのダンジョンLV1~LV2の解説+最短コード発表 #javascript|CodeIQ MAGAZINE

LV1の解答例として、私の投稿した解答も紹介されていたのですが。
「すごかったです。」としか書かれていなくて何の解説もされていないので。
別にすごくないよー、ちょこっと数学使ってるだけだよー、と言いたくて。
軽くぱぱーと解説記事を書きます*1

まず2進化10進数について。

まずは、タイトルの意味が全く分からない方のために。
割と有名な*2概念として、2進化10進数というものがあるので、そちらを先に軽く解説。

簡単に一言で言うと、「10進数の各桁を2進数4桁で表したもの」です。
詳しくは↓参照。
二進化十進表現 - Wikipedia

このWikipediaの記事にもある通り、2進化10進数で表された数値をそのまま16進表記すると、元の数値の10進表記と同じになります。
どういうことか。具体例で表しましょう。

10進表記の「51」という数値を考えます。
「5」を2進4桁表記すると「0101」。「1」は「0001」。
よって2進化10進表記は「01010001」となります。
これを4桁毎に区切って16進表記にすると、「0101」は「5」、「0001」は「1」です。
つまり、2進数値「01010001」を16進表記にすると、「51」になります。
ほら、元の10進表記と同じになりましたね。

逆に考えましょう。
16進数で「51」と書かれていた場合、これは10進数に直すと「81(=5×16+1)」です。
でも、この具体的な数値のことは考えないでください。
あくまで「16進表記の『51』という数値」とだけ捉えましょう。
これを2進表記にしてみましょう。「1010001」となります。
7桁で中途半端なので、桁数が4の倍数になるように頭をゼロ埋めしましょう。
「01010001」となりますね。

今、何をしたか分かりますか?
「数値 n を2進化10進表記にする」ということをしたことになります。
言葉でまとめると。↓これだけ。

  1. その数値の10進表記を16進表記と見做してその数値を考える。
  2. それを2進表記にしてゼロ埋めすれば2進化10進表記のできあがり。

これをコードに落とせば、割とシンプルな「数値を2進化10進表記にする」コードが書けます。
でも、ここでもう一工夫。

もう一度、10進表記の「51」という数値について考えます。
この先頭に数字の "1" を書き足した「151」という16進表記の数値を考えてみましょう。
これを2進表記(ゼロ埋めなし)にすると、「101010001」という9桁になります*3
この先頭の "1" を取り除けば、やはり求める2進化10進表記8桁「01010001」になります。

つまり。

  1. その数値の10進表記に、先頭に "1" を文字列連結して、それを16進表記と見做してその数値を考える。
  2. それを2進表記にして、先頭の "1" を取り除けば、2進化10進表記のできあがり。

これをコードに落としてみましょう。JavaScript の function 化した例です。

function toBCD(n) {
    return parseInt("1" + n, 16).toString(2).slice(1);
}
// console.log(toBCD(51))
// => "01010001"

提出コードの解説

前節を踏まえて、解説記事で紹介されている私のコードを見てみましょう。見やすいように、またお行儀良くするために、演算子前後の空白とか文末のセミコロンを追加します*4

// antimon2 様
r = parseInt("1" + i, 25).toString(5).slice(1);

ほら、前説で紹介したコードと同じ形をしていますね。
違うのは、関数ではなく代入文に直接記述していることと、変数名と、parseInt および toString メソッドに渡している数値。
つまり言葉に直すと。

  1. その数値の10進表記に、先頭に "1" を文字列連結して、それを25進表記と見做してその数値を考える。
  2. それを5進表記にして、先頭の "1" を取り除けば、5進化10進表記のできあがり。

「ちょっと待って。5進化10進表記って何なのさ?」

っていう根本的な問題が解決していませんね。

そもそもこの問題は、「数値をそろばんのような仕組みの数字列に変換する」というもの。
10進数の各桁の「0」〜「9」の数字を「00」「01」「02」「03」「04」「10」「11」「12」「13」「14」に直してつなげる。
例えば10進数の「48」は「0413」。

つまり。
10進数の各桁を、5進表記2桁(ゼロ埋め)で表していることになるわけです。
2進化10進数の考え方と同じなわけです。
それで「5進化10進数」、というわけです*5

で。
先ほどは10進数の各桁を表すのに「2進数4桁」だったので、2**4 = 16 だから「16進表記」を利用した。
今回は「5進数2桁」なので、5**2 = 25 だから「25進数」。
という結果、あの parseInt(○, 25).toString(5) というコードになる、というわけです。

ね。
別に奇をてらったわけではない、至ってシステマチックな解答だってお分かりいただけると思います。
文字数そのものも少なめですが、加えて既存の関数/メソッドを組み合わせた、コンパクトな解答になっています*6

ということでした*7

*1:タイトルの意味が分かるor類推できる方ならこの記事を読む必要はないですたぶん。

*2:個人の感想です

*3:この場合に限らず、先頭が1で始まる16進数は、2進表記に直すと必ず4n+1桁になります。

*4:ダンジョンシリーズ問題というのは所謂「コードゴルフ大会」のような一面を持っているので、省略できるものを省略しまくったコードになっているのです。

*5:今更ですが、『5進化10進数』というのは私の造語です。少なくとも一般に知られている呼び方かどうかを確認しないでこの記事を書いています。

*6:正直最近の「とにかく短く」とか「とにかく早く」という(CodeIQローカルの)風潮についていけてなくなりつつありまして…今回この解答が導出できなかったらこの問題に投稿していませんでした。

*7:結果的にあまり「軽くぱぱーと」な記事になってないかも(^-^;