進数変換
目標
ある非負整数を進数で表す。()
また、進数で表された非負整数を進数で表す。
説明
前説明
以下、進数で表された整数をと表します。
まず、の各桁の数字について考えてみます。
の各数字、、、、、は、
それぞれの値が、、、、、であることを表していて、これらの和がとなっています。
これを式で表すと、次のようになります。
右辺の各項をの累乗を掛けた形に直すと、
このことから、右辺のある項がであるとき、は右端の数字から個離れた桁の数字であることがわかります。
つまり、一般にある非負整数を進数表記()で表したとき、右端の数字から個離れた桁の数字をとすると、は次のように表すことが出来ます。
・・・★
このことを元に、進数を変換することが出来ます。
ある非負整数を進数で表す。()
それでは、を進数で表してみます。
★式を見ると、右辺の中で唯一だけがの倍数ではないことがわかります。
よって、をで割った余りがであることがわかりました。
このことを、「」という書き方で表すと、次のようになります。
この式をよーく見てみると、★式の右辺と同じような構造の式があるのがわかりますね。
「」の部分です。
つまり、この部分についても同様にで割った余りを求めることで、今度はがわかります。
よって、
をで割った余り
「をで割った商」をで割った余り
「「をで割った商」をで割った商」をで割った余り
...
となることがわかりました。
進数で表された非負整数を進数で表す。()
こちらは上記のものより簡単です。
今、前提よりの各桁の数字がわかっているので、あとは★式に代入すればOKです。
具体例
を進数で表す
をで割っていけば良いので、
よって、であることがわかりました。
(上から見てではないことに注意!)
なお、紙に書いて計算するときは次のような書き方をすることが多いです。
3)70
3)23...1
3) 7...2
3) 2...1
0...2
を進数で表す
★式に代入し、右辺を計算するだけです。
よって、であることがわかりました。
を進数で表す
この場合は、進数に直してから進数にします。
まず、を進数で表します。
よって、です。
次に、を進数で表します。
よって、です。
以上より、であることがわかりました。
コード(C++)
以上の計算をC++のコードにしてみました。表記の都合上、進数のは以上以下の整数であるとしています。なお、細かい例外処理などは行っていないので、必要に応じて実装してください。
ある非負整数を進数で表す
//要ヘッダ:cmath long long int ConvBase10ToN(long long int m, int n){ if(n<2 || n>10) return m; long long int result=0; int basePos=0; do{ result += m%n * std::pow(10, basePos); m/=n; ++basePos; }while(m/n!=0 || m%n!=0); return result; }
進数で表された非負整数を進数で表す。
//要ヘッダ:cmath long long int ConvBaseNTo10(long long int m, int n){ if(n<2 || n>10) return m; long long int result=0; int basePos=0; while(m!=0){ result += m%10 * std::pow(n, basePos); m/=10; ++basePos; } return result; }
進数で表された非負整数を進数で表す。
以上の関数を組み合わせることで、このような関数を作ることも出来ます。
long long int ConvBase(long long int m, int from, int to){ return ConvBase10ToN(ConvBaseNTo10(m, from), to); }
あとがき
順を追って書いていたらなんだか結構長くなってしまいました。
あまり張り切りすぎても書くのが面倒くさくなってしまうと思うので、自分の負担にならず、かつ説明したい所は説明の出来ているちょうどいい記事を作っていけるように心がけます。
また、質問や、何か間違いなどあればコメントを頂けると嬉しいです。