アルゴリズム (全79問中64問目)

No.64

0000〜4999のアドレスをもつハッシュ表があり,レコードのキー値からアドレスに変換するアルゴリズムとして基数変換法を用いる。キー値が55550のときのアドレスはどれか。ここで,基数変換法ではキー値を11進数と見なし,10進数に変換した後,下4けたに対して0.5を乗じた結果(小数点以下は切捨て)をレコードのアドレスとする。
  • 0260
  • 2525
  • 2775
  • 4405
  • [出題歴]
  • 基本情報技術者 H14春期 問2
  • 基本情報技術者 H21春期 問2
  • 基本情報技術者 H26秋期 問2

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

n進数で表された数を10進数に変換できるかがポイントです。
キー値 55550 が11進数だとすると、桁ごとに11の累乗になっているので、10進数に変換するには、

 5×114+5×113+5×112+5×111

という式の値を求めることになります。これを地道に計算してもよいのですが、ここでは速く解くために、まず式を変形(下線部分)してから解いています。

 5×114+5×113+5×112+5×111
(113+112+11+1)×55
=(1331+121+11+1)×55
80520

最後に 80520 の下4けた「0520」に0.5を乗じると参照すべきアドレス0260が求められます。

※補足 式の変形
 5×114+5×113+5×112+5×111
=(114+113+112+111)×5
=(113+112+11+1)×5×11
=(113+112+11+1)×55
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop