[C++]基数変換関数をアップグレードする
こんばんは、はまー０１です。今回は、競技プログラミングの心強いお供、基数変換関数をアップグレードして柔軟にするお話です。
完成したコード
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string ntom(string str, const string S, const string T){
const int n = S.size(), m = T.size();
vector<int> ns(130);
for(int i = 0; i < n; ++i)ns[S[i]] = i;
long long sum = 0;
for(char c : str)sum = sum * n + ns[c];
string res;
do{
res = T[sum % m] + res;
sum /= m;
}while(sum);
return res;
}
string ntom(string str, const int n, const int m){
string S, T;
for(int i = 0; i < n; ++i)S.push_back((i >= 10 ? 'A' - 10 : '0') + i);
for(int i = 0; i < m; ++i)T.push_back((i >= 10 ? 'A' - 10 : '0') + i);
return ntom(str, S, T);
}こんな感じになります。こちらのコードの解説をしていきます。
基数変換関数の基本の仕組み
10進数から2進数、2進数から10進数に基数変換する、というのは皆さんもやったことがあるかもしれません。これと似たようなことをしていきます。
2進数⇔10進数
2進数から10進数にするとき、右の桁からi番目の数を2^(i - 1)して足していく、としたはずです。
また、10進数から2進数にするとき、2で割って、そのあまりを順に読んでいく、としたはずです。
n進数からm進数でもやること自体はあまり変わりません。具体的には、
n進数→10進数→m進数
といった感じで、一度10進数に変換してからm進数に変換します。
n進数→10進数
2進数→10進数と同様に、i桁目の数をn^(i - 1)して足していきます。
ただ、毎回pow関数などを使う必要はなく、ちょっとしたテクニックでこの処理をシンプルに実装できます。
#include <iostream>
#include <string>
using namespace std;
string ntom(string str, const int n, const int m){
long long sum = 0;
for(char c : str)sum = sum * n + (c - '0');
}こんな感じに、毎回n倍していきながら桁の数を足すことで、i桁目をn^(i - 1)する処理を簡潔にすることができます。
10進数→m進数
次に、足し合わせた値sumをmで割り、その余りをとります。この処理をsumが0になるまで繰り返します。余りを文字列に加えていき、最後にその文字列を返せば完了です。
コード
#include <iostream>
#include <string>
using namespace std;
string ntom(string str, const int n, const int m){
long long sum = 0;
for(char c : str)sum = sum * n + (c - '0');
string res;
do{
res = char(sum % m + '0') + res;
sum /= m;
}while(sum);
return res;
}実際に動かすとこんな感じです。
#include <iostream>
#include <string>
using namespace std;
string ntom(string str, const int n, const int m){
long long sum = 0;
for(char c : str)sum = sum * n + (c - '0');
string res;
do{
res = char(sum % m + '0') + res;
sum /= m;
}while(sum);
return res;
}
int main(){
cout << ntom("1101", 2, 10) << endl;//13
}11進数以上にも対応させる
これで基数変換関数が完成しました…
が、これだと10進数までしか対応していません。今度はこの問題を解決していきます。
対応表を作る
実は、基本的な仕組みは先ほどのものとほとんど変わりません。ここにちょっとだけ付け加えればいいのです。
では何を付け加えるのかというと、対応表です。
16進数を例にとると、
0~9(10)→0~9(16)
10(10)→A(16)
11(10)→B(16)
12(10)→C(16)
13(10)→D(16)
14(10)→E(16)
15(10)→F(16)
この対応表を関数に渡してあげようということです。実際に表を渡すことはできないので、文字列として渡してあげます。どういうことかというと、文字列をSとおくと、
S[i] = 10進数のiに対応する文字
というふうにします。例としては、
"01" …2進数の対応表
"0123456789" …10進数の対応表
"0123456789ABCDEF" …16進数の対応表
となります。これを関数に渡して11進数以上にも対応させます。
まずは対応表を作ります。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string ntom(string str, const string S, const string T){
const int n = S.size(), m = T.size();
vector<int> ns(130);
for(int i = 0; i < n; ++i)ns[S[i]] = i;
}ns[i] = n進数の文字S[i]に対応する10進数の数
このようにvectorを使って対応表を作ります。nsのサイズが130なのは、char型として普段使う文字をint型にキャストしたとき、最大で127になったからです。なのでこの値は環境などに合わせて変えてください。
対応表を元に基数変換する
後はこの対応表に合わせて基数変換をするだけです。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string ntom(string str, const string S, const string T){
const int n = S.size(), m = T.size();
vector<int> ns(130);
for(int i = 0; i < n; ++i)ns[S[i]] = i;
long long sum = 0;
for(char c : str)sum = sum * n + ns[c];//n進数を10進数にする
string res;
do{
res = T[sum % m] + res;//10進数をm進数にする
sum /= m;
}while(sum);
return res;
}コード
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string ntom(string str, const string S, const string T){
const int n = S.size(), m = T.size();
vector<int> ns(130);
for(int i = 0; i < n; ++i)ns[S[i]] = i;
long long sum = 0;
for(char c : str)sum = sum * n + ns[c];
string res;
do{
res = T[sum % m] + res;
sum /= m;
}while(sum);
return res;
}実際に動かすとこんな感じです。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string ntom(string str, const string S, const string T){
const int n = S.size(), m = T.size();
vector<int> ns(130);
for(int i = 0; i < n; ++i)ns[S[i]] = i;
long long sum = 0;
for(char c : str)sum = sum * n + ns[c];
string res;
do{
res = T[sum % m] + res;
sum /= m;
}while(sum);
return res;
}
int main(){
cout << ntom("ABC", "0123456789ABCDEF", "0123456789") << endl;//2748
}さらに使いやすくする
これで11進数以上の基数変換もできるようになりました。ですが、これだと例えば9進数→10進数という操作をする場合に
ntom("876", "012345678", "0123456789")としなければなりません。これだと毎回対応表を打つのがめんどくさいですよね。
というわけで、0~9、A~Zの文字で表されたn進数をm進数に基数変換する関数を付け加えていきます。
といっても、やること自体は単純で、
S[i] = '0' + i (i <= 9)
S[i] = 'A' + i - 10(i > 9)
とするだけです。
コード
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string ntom(string str, const string S, const string T){
const int n = S.size(), m = T.size();
vector<int> ns(130);
for(int i = 0; i < n; ++i)ns[S[i]] = i;
long long sum = 0;
for(char c : str)sum = sum * n + ns[c];
string res;
do{
res = T[sum % m] + res;
sum /= m;
}while(sum);
return res;
}
string ntom(string str, const int n, const int m){
string S, T;
for(int i = 0; i < n; ++i)S.push_back((i >= 10 ? 'A' - 10 : '0') + i);
for(int i = 0; i < m; ++i)T.push_back((i >= 10 ? 'A' - 10 : '0') + i);
return ntom(str, S, T);
}このように、文字列SとTをそれぞれn進数、m進数に対応させた文字列にし、それを先ほど作った関数に渡してあげることで、書く量を少なくできます。
実際に動かすとこんな感じです。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string ntom(string str, const string S, const string T){
const int n = S.size(), m = T.size();
vector<int> ns(130);
for(int i = 0; i < n; ++i)ns[S[i]] = i;
long long sum = 0;
for(char c : str)sum = sum * n + ns[c];
string res;
do{
res = T[sum % m] + res;
sum /= m;
}while(sum);
return res;
}
string ntom(string str, const int n, const int m){
string S, T;
for(int i = 0; i < n; ++i)S.push_back((i >= 10 ? 'A' - 10 : '0') + i);
for(int i = 0; i < m; ++i)T.push_back((i >= 10 ? 'A' - 10 : '0') + i);
return ntom(str, S, T);
}
int main(){
cout << ntom("ARC", 28, 10) << endl;//8608
cout << ntom("120", 3, 10) << endl;//15
}これで、n進数からm進数への基数変換を行う関数ができました。
注意点
この関数に渡す数列や、関数から返ってくる数列は、どちらも文字列です。整数型で渡しても機能しません。
また、0~9、A~Zという前提で作っているため、37進数以上、またはそれ以外の表し方での基数変換をする際は、変換表を文字列として渡す方の関数(上の関数)を使ってください。
そしてここが一番重要なのですが、僕はプログラミング初心者なので、このコードが正しく動くかは分かりません。使う場合は自己責任でお願いします。誰も使わないと思うけど。
おわりに
最後まで長ったらしい記事にお付き合いいただきありがとうございました。今回が初の真面目な(?)記事になります。何か間違った点があれば教えてくださると幸いです。
追記
2025/1/9更新:コードを一部修正しました
ms配列が不必要だったため削除
num変数が不必要だったため削除