シェアする

  • このエントリーをはてなブックマークに追加

実装例もあるよ!10進数の数字をk進数に変換する

シェアする

  • このエントリーをはてなブックマークに追加

今回も競プロネタです。

与えられた数値を\(k\)(\(k\)は整数)進数に変換する必要に迫られることが多々ある。例えば、与えられた数値を10進法と8進法で書いたときに7が含まれていないかとか求めさせられることがある。
忘れんぼさんで毎回毎回何だったけなぁとなって、その度に調べていていい加減めんどくさくなってきたので、
自分の理解を一度アウトプットしておいて理解の定着を図ることにした。
未来の自分と、このブログにたまたまたどり着いた幸運な(?)読者の方に参考になれば幸いです。

また、競プロ関連の記事は他にも書いています。今後必要なことを拡充していきたいと思いますので参考にしてみて下さい!

おさらい~\(k\)進法表記

まず、\(k\)進法での表記についておさらいする。
任意の自然数\(N\)を\(k\)進法で\({a_{l}a_{l-1}\cdots a_{0}}_{\left(k\right)}\)と表記したとき、

\(\begin{eqnarray} N &=& \sum_{i = 0}^{l}a_{i}k^{i} \\ &=& a_{0}\times k^0+a_{1}\times k+a_{2}\times k^{2}+\cdots +a_{l}\times k^{l} \end{eqnarray}\)

ということを意味している。2進数を例として出せば、10進数での11

\(\begin{eqnarray} 11 = 1\times 10^0+1\times 10 \end{eqnarray}\)

は2進数での\(1011_{\left(2\right)}\)であって

\(\begin{eqnarray} 11 = 1\times 2^0+1\times 2+0\times 2^2+1\times 2^3 \end{eqnarray}\)

を意味する。さらに3進数で表記すると\(102_{\left(3\right)}\)であって

\(\begin{eqnarray} 11 = 2\times 3^0+0\times 3^{1}+1\times 3^{2} \end{eqnarray}\)

である。

以上より、\(k\)進法で\({a_{l}a_{l-1}\cdots a_{0}}_{\left(k\right)}\)と書いたときの各\(a_{i}\)は、自然数\(N\)を\(k\)進法で足し算にばらしたときの係数が書いてあることが分かる、というよりそういう定義。

\(k\)進法表記に変換するときの考え方

与えられた10進数の入力を\(k\)進法表記に変換するとき、重要になるのは以下の等式である。

\(\begin{eqnarray} N &=& \sum_{i = 0}^{l}a_{i}k^{i} \\ &=& a_{0}\times k^0+a_{1}\times k+a_{2}\times k^{2}+\cdots +a_{l}\times k^{l} \end{eqnarray}\)

c++において、整数同士の割り算では端数は切り捨てられる
従ってこの式から分かるように、各\(a_{i}\)を求めるには、\(k^{i}\)で割った後に\(k\)で割ったあまりを取ればよい
最初の\(k^{i}\)で割ったときに\(k^{i-1}\)までの項が全て0になり、後に\(k\)の剰余を考えることで\(k^{i+1}\)以降も全て消え去るからである。
こうして、\(a_{i}\)のみを取り出すことが出来る。

実装例

以上の考え方に基づき、10進数表記を\(k\)進数表記に直す実装例は以下のようになるであろう。1

string ten2k(int n, int k){
 string s = "";
 if(n == 0) return "0";
 if(k == 1){
  for(int i = 0;i < n;i++) s += '1';
  return s;
 }
 while(n > 0){
  s += to_string(n % k);
  n /= k;
 }
 reverse(s.begin(),s.end());

 return s;
}

whileループの中で各桁を取り出しているが、それをそのまま返してしまうと表記が冪の小さい順に並んでしまうのでreverseでひっくり返している。
また、あまり使わないかもしれないが1進数表記に直そうとするとwhileループが無限に回ってしまうので、例外として処理した。
計算量は\(O\left(N\right)\)。
自分の環境でうまく動くことは一応確認してある。
(2021.10.12 追記)
\(n = 0\)の時に空文字を返してしまうので別途処理した。

まとめ

いかがだったでしょうか。

今回は今後の自分のためと、同じような悩みを抱えている方向けに10進数から\(k\)進数表記への変換方法をまとめてみました!
誰かのお役に立てれば幸いです。

もっとこんなことを記事にしてほしいなどのご要望がありましたら、このページ上部のお問い合わせフォームまたは下部のコメント欄からご連絡いただくか、以下のメールアドレスでもお待ちしております。

tsunetthi(at)gmail.com

(at)の部分を@に変えてメールをお送りください。

または、twitter(@warotan3)もやってますのでそちらに連絡していただいても良きです。

サムネイル画像はpixabayさんからダウンロードさせていただきました!
ありがとうございます!

  1. ソースコードの表示がうまくいかなかったのでコードのスクショを貼り付けました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする