読者です 読者をやめる 読者になる 読者になる

はたらく投資家

サラリーマン生活に疲れきっている投資家が奮闘する日記(ポロリはないよ)

アルゴリズムについて(ちょっとプログラミングを勉強したよ)

IT・プログラミング

こんにちは。

 

情報技術者試験の勉強をしていました。

そのなかでアルゴリズムの設問をやっていたのですが、X進数を整数に変換するためのアルゴリズムが面白かったのでそれを紹介します。

 

 

 

アルゴリズムのひな形

X進数の文字列「Num」があったとしましょう。

答えとなる整数の値をYとしましょう。

 

A←0・・・最初にAに0を代入します。

_________________________________

(繰り返し部分)

idx:1,1,idx≦Length(Num)   (初期値,増分,終値)とします。

Y←X×A+ToInt(substr(num,idx,1))

(繰り返し部分)

 ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄

return A

 

※LengthはNumの文字列長を返す関数

※ToIntはX進数の1文字を整数値(10進数)に直す関数

※SubstrはNumの先頭からidx番目の1文字を取り出す関数

※returnは(繰り返し部分)の計算終了毎に値が変わり(A←Yとなる)、繰り返しが始まる際に適用される

 

これでX進数を整数Yに変換することが可能なのです。

 

実例

 

実例でやってみましょうか。

例えば16進数の64を整数値10進数に変換することを考えましょう。

Y←X×A+ToInt(substr(num,idx,1))を考えると

一巡目が、

X=16(16進数)

A=0(初期値)

ToInt(substr(num,idx,1))で先頭の文字を抽出(6)

(16×0+6)=6

 

二巡目が

X=16(16進数)

A=6(returnによる返り値)

ToInt(substr(num,idx,1))で先頭から2番目の文字を抽出(4)

(16×6+4)=100

64は2文字なので二巡で終わりです。・・・あってますよね。

 

なぜそうなるのか

 

16進数の64を整数値に直すには、手計算では、

6×16^1+4×16^0=100と計算します。

 

ここで、6には16^1の荷重が、4には16^0の荷重がかかっています。

このアルゴリズムでは、ToInt(substr(num,idx,1))で一文字を抽出していますね。

これは次の段階の計算で荷重をかけるために抽出しているのです。

 

早く抽出すればするほど荷重(n回目-先頭からの距離)が重くかかってくるため、手計算と同様の数値となるのです。

 

分かりにくいので、2進数で5巡する計算を考えてみましょう。

例えば、二進数11011・・・整数値27(十進数)

一巡目、

0×2+1=1

二巡目

1×2+1=3

三巡目

3×2+0=6

四巡目

6×2+1=13

五巡目

13×2+1=27

 

これを合わせて計算すると

(((((0×2+1)×2+1)×2+0)×2+1)×2+1)

という計算をしています。つまり、(0×2+1)が2^4の荷重、次の(×2+1)が2^3の荷重、次の(×2+0)が2^2、次の(×2+1)が2^1の荷重、次の(×2+1)が2^0の荷重をかけられていることになります。

つまり5巡目には、手計算と同等の式が出来上がるのです。

 

アルゴリズムがなんとなくわかってきたのですが、理解するまでには今は少し時間がかかってしまいます。もっと慣れないといけませんね。いいプログラムがかける素養を身に着けたいです。