アルゴリズム入門(基数変換)
私達人間は0〜9の10個の数字を使った10進数を使うことが一般的です。
それに対し、コンピュータは2進数で動いています。
2進数は0と1の2つの数字だけを使った表現する方法です。
つまり、0,1,10,11,100,101,110,111,1000,・・・のように桁が増えていきます。
そこで、10進数から2進数に変換する方法を考えてみましょう。
下記の方法がよく使われています。
18 ÷ 2 = 9 あまり 0
9 ÷ 2 = 4 あまり 1
4 ÷ 2 = 2 あまり 0
2 ÷ 2 = 1 あまり 0
1 ÷ 2 = 0 あまり 1
ここで、あまりを下から順に並べると10010となり、欲しい値が求められました。
これをプログラムで実装することが出来ます。
#!/usr/bin/awk -f BEGIN{ ARGC == 2 ? n = ARGV[1] : n = 10; result = ""; while (n > 0){ result = (n % 2) result; n = int(n / 2); } print result; }
もう少し汎用的にするために、基数を指定して変換出来る関数を作ってみましょう。
#!/usr/bin/awk -f BEGIN{ if(ARGC == 3){ n = ARGV[1];base = ARGV[2]; }else{ print "shinsu_change3.awk n base"; } result = ""; while (n > 0){ result = (n % base) result; n = int(n / base); } print result; }
さて、次は2進数から10進数に変換するプログラムです。
たとえば10010という2進数は
1 ×2 ^ 4 + 0 × 2 ^ 3 + 0 × 2 ^ 2 + 1 × 2 ^ 2 + 1 × 2 ^ 0であると考えられます。
実際に計算してみると
1 × 16 + 0 × 8 + 0 × 4 + 1 × 2 + 0 × 1 = 18というように求められます。
これをプログラムでも実装してみます。
#!/usr/bin/awk -f BEGIN{ if(ARGC == 2){ n = ARGV[1]; }else{ print "awk -f convert.awk num"; exit; } split(n,num,""); for(i = 1; i <= length(num); i++){ ans += num[i] * (2 ^ (length(num) - i)) } print ans; }
実際に実行してみます。
awk -f convert.awk 10010 18
これで基数変換もバッチリですね。